Mathematics in Games, Part 3: Junior Arithmancer

In the past two months’ blog posts I’ve talked some about mathematics in games.  December‘s focused on the importance of embedding the mathematics in the game world rather than pulling the player out of the game to solve math problems unrelated to that world.  In January I wrote up some thoughts about my parser-based interactive fiction game A Beauty Cold and Austere, in which the player recreates the history of mathematics via a dream world.

I’ve written another parser-based math game in addition to ABCA: Junior Arithmancer.  While there are some similarities between the two games, JA is trying to do something different than ABCA does, and so I don’t view it as a sequel or even a follow-up to ABCA.

In Junior Arithmancer you are (as in ABCA) trying to pass an exam.  This one, though, is an entrance examination to an institution of higher learning.  You have to demonstrate competency in an area of magic, arithmancy; this is done by using various arithmetic-related spells to recreate the first several digits in the decimal expansions of some famous constants, such as \pi, e, \sqrt{2}, and \zeta(3).

For example, the first several digits of \zeta(3) are 1, 2, 0, 2, 0, 5.  Suppose you have spells that STA (start), PLU (plus), MIN (minus), TIM (times), DIV (divide), and INC (increment by 1).  You could start at 1 by using STA 1.  Then you could move from 1 to 2 via PLU 1.  Then you could go to from 2 to 0 with MIN 2.  But now you’re stuck.  You can’t use a valid arithmetic operation involving TIM, DIV, or INC (the unused spells) to get from 0 to 2.  So STA 1, PLU 1, and MIN 2 only gets you three digits into the sequence.

Let’s see whether we can do better.  We must begin with STA 1.  There are three options now to get from 1 to 2: We could PLU 1, TIM 2, or INC.  Let’s go with INC as the least likely to be needed again.  Then from 2 to 0 we could use MIN 2 or TIM 0.  Let’s try the latter.  From 0 to 2 our only option is PLU 2.  Then from 2 to 0 we can’t use TIM again since it’s already been used, but we can go with MIN 2.  This is already better than the last time, as we’ve used STA 1, INC, TIM 0, PLU 2, and MIN 2 to recreate 1, 2, 0, 2, and 0 and so get five digits into the sequence.  Unfortunately, the only spell remaining is DIV, and you can’t use a division operation starting with 0 to obtain the last digit, 5.  So we’re stuck once again.

This example doesn’t use all the arithmancy spells in the game, though; there are others.  As you make progress through the exam you earn additional spells.  You can also earn spell prefixes; these modify the operations of the other spells.  For example, if you earn an INV (invert operation) prefix you could effectively gain a second PLU in a single sequence by using the INV prefix to turn your MIN operation into a PLU operation.

Then, after you’ve completed the ten sequences in the game, you’re faced with other challenges: Completing the sequences using only five, four, or even three spells; using spells to reach a number larger than 2 billion; and figuring out the color/number association scheme in the game and using that to visit certain colored spaces, perhaps in a particular order.

From a gameplay standpoint perhaps Junior Arithmancer‘s greatest strength is the huge explosion in the possibility space: (1) There are multiple arithmetic operations that can be applied, (2) Applying them in different orders produces different sequences of digits, and (3) Each operation’s effect can be modified by one of several prefixes.  So, after STA 1 to begin recreating \zeta(3), you may have something like seven spells to choose from with five possible prefix modifiers (six counting the spell’s basic effect), for a total of 42 options for the next spell.  After using one of those you might have six spells left, again with those five possible prefix modifiers plus the spell’s basic effect, for a total of 36 options.  So now we have 42*36 = 1512 options for a two-spell sequence after STA.  The third spell after STA will have 30 options, bringing our total number of three-spell sequences after STA to 1512*30 = 45360.  And this continues growing, to 45360*24 = 1,088,640 four-spell sequences after STA and then to 1,088,640*18 = 19,595,520 five-spell sequences after STA.  Not all options are possible, and some duplicate each other, but this gives us a ballpark figure for how many five-spell sequences there are in the game.  You also have to be looking ahead, since once you use a spell you can’t use it again on a sequence.

Another feature of Junior Arithmancer is that it is “juicy” in the way I described in my January post: Once you understand the rules of how the spells function, every one of those many, many spell combinations actually does something meaningful in the game.  I was helped greatly in this respect when designing the game since I was able to use the same arithmetic operations we all already know: I did not have to create, ex nihilo, somewhere on the order of 20 million different sequences of spell effects.

How does Junior Arithmancer stack up in terms of embedding the mathematics in the game world?  Well, you’re taking an exam in the game, so it’s not as embedded as with the two examples I gave in my December post (the one with my real estate agent and the one with the Brazilian boys).  With that caveat, though, I think it does a good job of achieving embeddedness.  Your goal is to recreate several sequences of digits, and the only way to do so is to find creative ways to perform a set of arithmetic operations in a certain order.  You’re constantly having to think and rethink about arithmetic.  (Some of the other spells and modifiers make things more complex, so you’re not always working with single-digit numbers.)

Does Junior Arithmancer teach anything, though?  Not in the way that I tried to do with A Beauty Cold and Austere:  The arithmetic in JA is mostly elementary-school level.  The few exceptions don’t require anything more complicated than an understanding of how arithmetic works with negative numbers.  So the game is probably too complicated to be used to teach arithmetic to children effectively,  In addition, players interested enough to engage JA‘s number puzzles probably know arithmetic well enough that they don’t need the practice JA provides.

But I think there’s a place for math in games that don’t have an ulterior educational motive, too.  Mathematics has plenty of power as a tool to solve problems, but it’s also one of humanity’s great inventions in its own right.  Why not mine it for game ideas – for fun – and use it as a sandbox to play in?

Advertisements
Posted in games, teaching | 1 Comment

Mathematics in Games, Part 2: A Beauty Cold and Austere

Last month I wrote a post on the importance of context when teaching and learning mathematics, especially as it applies to games.  My primary point was that the mathematics needs to be embedded in the gaming experience in order for the math to stick in the player’s head.  Games that pull the player out of the primary gaming experience to solve math problems do not teach the mathematics as effectively as they could.  They also reinforce a sense that mathematics isn’t relevant.

As it turns out, I’ve written two games that feature a great deal of mathematics: A Beauty Cold and Austere and Junior Arithmancer.  In this post I’ll talk about how I wove math into these two games – what I think I did right as well as what I think I did wrong.

First, ABCA and JA are both parsed-based interactive fiction (IF).  This is an old genre of computer game, dating back to the 1970s.  The player’s experience with the game is mediated almost entirely through text, rather than graphics.  Playing parser-based IF is a lot like reading an interactive book, where you type in what you want the player to do.  For example, if you happen to find yourself in a room with, say, a battery-powered brass lamp, you could type

GET LAMP

and the game would transfer the lamp to your inventory, while giving you a response such as

Taken.

So, there’s one aspect of ABCA and JA that’s different from a lot of math edutainment games: They’re both text-based rather than graphics-based.  In the late 2010s, that will unfortunately limit the appeal of the games.  On the other hand, that also means that I can create the games myself and distribute them for free, without having to depend on and pay artists, graphic designers, and others.  (Not that I have anything against artists or graphic designers; it’s just that I don’t have the time or money to direct a major software project involving multiple people.)

In A Beauty Cold and Austere you play the role of a college student taking a survey course in conceptual mathematics.  You’ve blown off the course all semester and are now facing an oral final exam in the morning.  Tired of studying, you fall asleep – and you dream your way through the history of mathematical thought.  The gameplay involves solving a series of (mostly) mathematically-related puzzles.  By the time you’ve completed the game you’ve demonstrated an understanding of a variety of areas of mathematics – such as algebra, geometry, calculus, and probability – and are able to pass your final exam with ease.

(MAJOR SPOILERS FOR ABCA COMING UP.)

For example, at one point in the game you find yourself in the Library of Alexandria.

On the wall are carved numbers from 1 to 100, in ten rows of ten each.  It looks like you could push any of the numbers.  Next to the numbers is a switch, with two settings: “Remove Number” and “Remove Larger Multiples of the Number.”  The switch is currently set to “Remove Number,” although you could easily move it to the other setting by flipping the switch.  The numbers currently look like this:

1   2   3   4   5   6   7   8   9  10

11  12  13  14  15  16  17  18  19  20

21  22  23  24  25  26  27  28  29  30

31  32  33  34  35  36  37  38  39  40

41  42  43  44  45  46  47  48  49  50

51  52  53  54  55  56  57  58  59  60

61  62  63  64  65  66  67  68  69  70

71  72  73  74  75  76  77  78  79  80

81  82  83  84  85  86  87  88  89  90

91  92  93  94  95  96  97  98  99  100

At the bottom is a challenge from the librarian: “To access the map room, leave just the primes between 1 and 100 by pushing only five numbers.”

More mathematically-inclined players will recognize that you need to use the Sieve of Eratosthenes to proceed here.  But you don’t need to have seen the Sieve to solve the puzzle.  In fact, I’ve watched more than one player quickly realize that setting the switch to “Remove larger multiples” and then pushing 2 will remove almost half of the numbers.  From there, it’s not too hard to figure out what else needs to be done – especially since the game dynamically updates the puzzle to let you know what’s left.

Which is part of the point, really.  ABCA isn’t trying to give players arithmetic or algebra practice; it’s trying to get people to engage with and explore mathematical ideas.  So it needs to be accessible to people who haven’t seen a lot of advanced mathematics.

I guess that last paragraph was a bit of a digression from my theme of embedding mathematics in the game world.  But it gets at another aspect of designing a game that features mathematics: The mathematics in the game should itself be interactive – not static.  The player should be able to try things and have the game respond in ways that encourage the player to keep playing with the mathematical ideas.  It shouldn’t be about merely coming up with the right answer to a math question.

I think the number puzzle here is a pretty good example of embedding mathematics in a game.  Its weakness is that it is a “set puzzle”: While it doesn’t commit the error of pulling the player out of the game, it is mostly stand-alone in terms of the gameplay.  However, set puzzles are a common feature of parser-based interactive fiction, so the player is expecting them.  In addition, Eratosthenes was actually the head librarian at the Library of Alexandria, so it makes sense for the player, while standing in his office, to encounter a challenge that uses his Sieve.

In truth, several of the math puzzles in ABCA are set puzzles.  I tried to place them in spaces that made sense, though: The main probability set puzzle is in a casino, for example, and a graph theory puzzle is reinterpreted as riding a laser bike through a collection of roads and intersections.  And some of the puzzles, such as the calculus/roller coaster puzzle, require information or objects from elsewhere and so are not completely self-contained.  I think it’s fine to include several set puzzles in a math-heavy game, but the designer should try as much as possible to integrate them into the game world.

The most embedded puzzle – and thus arguably one of the best in the game – is the meta-puzzle at the very top level of the game’s geography.  When you first enter the dream you find yourself standing at a point.  Your actions very quickly turn this into a number line.  Then, as you progress further through the game and learn more mathematics, this region of the game adds more features – such as a zero, negative numbers, and a few more aspects that I’ll let the reader discover for herself.  This top level thus ends up mirroring the development of mathematics that the player is discovering throughout the game.  It’s also the source of some of the puzzles the player needs to solve.

There’s more to puzzle design than embeddedness, though.  There’s also interactivity and engagement.  I’ve heard some refer to this as “juicyness.”  The idea is that a puzzle should give some kind of interesting response to everything reasonable the player tries.  In other words, the game shouldn’t just spit back a generic failure message to everything except the expected right solution.  In addition to this kind of responsiveness, multiple solutions to a puzzle can also help achieve juicyness.

The puzzle where I think ABCA achieves juicyness the most is probably the sequences-and-series machine.  This one is very much a set puzzle in terms of the player’s first encounter with it.  However, the machine is attached to a path that responds to the different settings of the machine’s various dials and levers.  Each combination of settings reproduces a different sequence or infinite series of real numbers, and the path changes to lead to the limit of the sequence or the sum of the series.  Some of the sequences and series converge and some don’t, and those that don’t fail to do so in different ways.  All of these are modeled by the path.  There is a particular “right” path outcome in terms of advancing the game, but there are multiple setting combinations that produce it – corresponding, of course, to the sequences and series that actually lead to that right outcome.  But the player can fool around with the machine as much as he wants, seeing what the different settings do.  Thus this particular puzzle achieves juicyness by featuring both multiple solutions and plenty of responses to “failure” attempts.  And in terms of the mathematics, it’s a lot more interesting to think about convergence and divergence in the context of a game world that you’re exploring than it is when you’re manipulating symbols as part of your calculus homework.  (Well, more interesting for most people.)

There are several puzzles in ABCA that I think are weaker, though.  These generally involve fetching the right item for or answering questions posed by a particular character.  These include the scenes with Cauchy and Weierstrass, with Hypatia, and with Newton, as well as the puzzle involving logarithms.  The Hypatia one in particular could have been better, as at least for the others the player must make a connection between the mathematics they developed and either the objects in the game or the answers to their questions.

But, overall, I’m pleased with A Beauty Cold and Austere.  There are definitely things I could have done better, but I think it’s a good game in its genre of massive puzzlefest, parsed-based interactive fiction.

This post has already gotten long enough, so I suppose I’ll save my comments on Junior Arithmancer for next month.


(Update: June 19, 2019.)

This past weekend I gave a talk on mathematics through narrative at the NarraScope conference in Boston, and I made some of the same points in the talk as I do here.  One of the attendees at my talk was Graham Nelson.  Graham is a mathematician, the author of several IF games (including the classic Curses!), and the creator of Inform 7 – the programming language I used to write A Beauty Cold and Austere.  After the talk he expressed a more positive take on the set pieces in ABCA than I do in this post.  He said (I’m paraphrasing from memory) that a set piece helps to keep the mathematical concepts in the puzzle contained and thus easier for players to digest.

I still wish I had managed fewer set piece puzzles in ABCA, but I also think Graham is right that they have more pedagogical value than I had given them credit for.  And I imagine that a game whose puzzles mostly extend over multiple locations – a game whose puzzles generally aren’t set pieces – could easily get confusing for the player, mathematically-speaking.

Posted in games, teaching | 2 Comments

Mathematics in Games, Part 1

When my wife and I were buying our first house many years ago our real estate agent Rita quickly found out that I was a math professor.  She gave a response I have heard frequently over the years: “I’m not very good at math.”  At some point during the process it came time to calculate our monthly mortgage payment.  Rita handed me a calculator and said that I could come up with the answer better than she could.  I had been teaching the amortization formula for determining mortgage payments in a class that semester, so I took the calculator and gave it a try.  After several keystrokes I handed the calculator back to Rita with the answer.  She looked at it and said, “That’s not right!”

Question: Who should you believe here?  The math professor, or the real estate agent who said she wasn’t very good at math?

Well, the math professor knew who you should believe: the real estate agent.  Sure, I had been teaching the amortization formula, but it’s a complicated formula.  I might have forgotten a small detail when put on the spot like that, or I might have hit a couple of buttons in the wrong order, or I might have been unaware of how an unfamiliar calculator handles order of operations.  There are lots of little things that all had to go exactly right in order for me to produce the right answer.

What Rita had, on the other hand, was years of experience as a real estate agent.  She had a very good idea of what the payment should be for our loan amount and interest rate.  She needed the calculator to determine it exactly, but her domain knowledge was more than enough to realize that whatever answer I had come up with could not possibly be correct.  I, on the other hand, was a first-time home buyer who had never had to calculate a monthly payment on a loan of that size when the answer had a real impact on my life and finances.  I had no good way of knowing that my answer wasn’t right (at least, not without repeating the calculation multiple times as a check).

Let me drive home the point: Rita, the self-professed “not good at math” real-estate agent, was the more trustworthy expert on a math-heavy question concerning home buying than the math professor.

I think when people say “I’m not good at math” what they mean is that they are not good at the kinds of symbolic manipulation (mainly, arithmetic and algebra) that generally comprise a course in mathematics at the elementary school and junior high levels.  But mathematics isn’t just symbolic manipulation.  For example, it also includes estimation, as Rita displayed in my story here.  And I think that there are plenty of people – like Rita – who say they’re not good at math but who have, in certain domains, developed strong mathematical skills through experience.

Keith Devlin tells a story with a similar moral in his Mathematics Education for a New Era: Video Games as a Medium for Learning.  He talks about a research study undertaken with some young children (between 8 and 14 years of age) selling fruit in a street market in Brazil.  When asked, while working in the market, to do complicated arithmetic calculations to determine the price of several coconuts, the children got the answer correct 98% of the time.  (And they did this in their heads – often making use of some rather clever arithmetic shortcuts in the process!)  When presented, in their homes, with verbal word problems dealing with market stall sales transactions, the children got the answer correct 74% of the time.  However, when asked to solve written symbolic arithmetic problems that were mathematically identical to the market sales problems they only got the answer correct 37% of the time.

I tell these two stories as lead-ins to something I’ve been thinking about lately: Context often matters when it comes to doing mathematics.  And I think it matters with respect to teaching mathematics.

One thing I’ve been interested in the past couple of years is teaching mathematics through games.  My impression of most games that I’ve seen that really attempt to do this is that they repeatedly pull the player out of the context of the game in order to solve a series of math problems.  For example, the online game Prodigy (which my oldest son was really into during first grade) does this.  Prodigy is an RPG (role-playing game) aimed at elementary school kids.  As a player, you explore the game world and battle a series of monsters, earning experience and better equipment, as well as leveling up and acquiring new skills.  The math part appears in that every time you attempt an attack, the game throws a math problem at you.  In order to complete the attack successfully, you must solve the problem.  One thing the game does really well here is to ramp up the difficulty level with the player, so as you gain more experience you’re presented with harder and harder math problems.

However, having to solve a math problem has nothing internally to do with the game world you’re exploring in Prodigy.  As a result, you lose some of the sense of immersion in the game every time you attempt an attack.  In addition, the math problems are externally-imposed obstacles that you must overcome in order to get back to the real fun of the game.  I fear that an unintended side effect of games like Prodigy is to reinforce kids’ sense that math is an obstacle – a chore.  I also fear that they reinforce the impression that math is irrelevant to what really matters.

I also wonder how well the mathematics that a Prodigy player is supposedly learning is really sticking with him or her.  The questions are multiple-choice, for one.  (This is probably a good move from a gameplay standpoint, but this format doesn’t really require the player to think through the problems.)  Even more troubling is the fact that the mathematics is so separate from the rest of the game.  The more we can connect a new concept with things we already know (i.e., the more we can place new knowledge in a context, like with my real estate agent and those Brazilian kids), the more we retain it.  Contrariwise, new knowledge thrown at us that is not embedded in any larger context doesn’t tend to remain with us.

I really don’t mean to hit Prodigy too hard here.  I do think it’s one of the better kids’ math games I’ve seen.  Also, my son had a lot of fun playing it, and I’m glad he was spending time with it rather than some of the other games out there.  But I want to think about how we can do even better at embedding mathematics in games.

I have written a couple of my own games that feature mathematics – A Beauty Cold and Austere and Junior Arithmancer.  They’re text-based and feature no graphics, so that makes their appeal somewhat limited compared to a game like Prodigy.  Perhaps in my next post I’ll talk about what I think I did right in those games, mathematically-speaking.

Posted in games, teaching | 3 Comments

Proof of the Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states the following:

Every integer greater than 1 can be represented uniquely as the product of prime numbers.

Another way to put this is that every integer has a unique factorization.  For example, 60 factors into 2^2 \cdot 3 \cdot 5, and there is only one way to do this factorization using prime numbers.  (Rearranging the order of the numbers doesn’t count as a different factorization.)

In this post we’ll prove the Fundamental Theorem of Arithmetic.  There are two parts: (1) Proving that every integer greater than 1 can be represented as the product of prime numbers (i.e., existence), and (2) Proving that this representation is unique (i.e., uniqueness).

Reminder: A prime number is a positive integer that is divisible by exactly two positive integers: itself and 1.

First, Existence.  Suppose, by way of contradiction, that there is some positive integer that cannot be represented as the product of primes.  Then there is a smallest such number N.  If N cannot be represented as a product of primes then N cannot itself be prime.  Thus there exist two positive integers a and b, with 1 < a \leq b < N, such that N = ab.  Since a and b are both positive integers smaller than N they must each be the product of primes, where a = p_1 p_2 \cdots p_m, b = q_1 q_2 \cdots q_n, and p_i and q_j are primes for each i and j.  But then N = p_1 p_2 \cdots p_m q_1 q_2 \cdots q_n and thus also is the product of primes.

Second, Uniqueness.  For this we need a lemma that isn’t hard to prove:

Lemma: If a prime p divides an integer ab, then divides a or p divides b.

Now, let N be a positive integer.  Suppose there exist two ways to represent N as the product of primes,

N = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n,

where p_i and q_j are primes for each i and j.  Assume, without loss of generality, that these representations are ordered, so that p_i \leq p_{i+1} and q_i \leq q_{i+1} for all i for which these inequalities are defined.

Suppose p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_m and n > m.  Then  N = p_1 p_2 \cdots p_m < q_1 q_2 \cdots q_n = N, a contradiction.  Similarly, if  p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_n and m > n, we have a contradiction.

Now, let i be the first index for which p_i \neq q_i.  If i exists then i \leq \min\{m,n\}, by the argument in the previous paragraph.  We can assume, without loss of generality, that p_i < q_i.  We have that p_1 p_2 \cdots p_{i-1} = q_1 q_2 \cdots q_{i-1}.  Since p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n, we also have p_i \cdots p_m = q_i \cdots q_n.  By the lemma, p_i divides q_j for some j, i \leq j \leq n.  But each of the q_j values is prime and so is only divisible by 1 and itself.  Since p_i < q_i \leq q_j, we have a contradiction.

Thus there is no index i for which p_i \neq q_i.  Our argument two paragraphs above shows that we can’t have this and m < n or m > n.  Thus m = n, and so the two representations, p_1 p_2 \cdots p_m and q_1 q_2 \cdots q_n, are identical.

Posted in arithmetic | Leave a comment

Equivalence of Two Binomial Sums

This month’s post entails proving the following equivalence:

Identity 1: \displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k}.

Despite the fact that these two sums are over the same range and are equal for all values of n they are not equal term-by-term.

If you think about the two sides probabilistically, it’s not too hard to prove that they are equal.  For example, \binom{k-1}{r-1} p^r (1-p)^{k-r} is the probability of obtaining the rth head on the kth flip when repeatedly flipping a coin that has a probability p of being heads.  Thus the left side of Identity 1 is the probability of flipping a coin times and obtaining at least r heads.  Similarly, \binom{n}{k} p^k (1-p)^{n-k} is the probability of obtaining exactly k heads when flipping a coin n times (again, in which p is the probability of achieving heads on a single flip).  Thus the right side of Identity 1 is also the probability of flipping a coin times and obtaining at least r heads.  Therefore, the two sides must be equal.

A while back I was also interested in trying to prove algebraically that the two sides are equal.  This turned out to be harder than it looked, and I thought I would record my derivation here.  It’s a bit heavy on the algebra, I’m afraid.  The overall goal will be to isolate the coefficient of p^m on both sides of Identity 1, as each of the sides can be thought of as a polynomial in p.  If these are equal then the identities must be equal.

The left side first.  Expand (1-p)^{k-r} using the binomial theorem to get

\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} p^r (1-p)^{k-r} = p^r \sum_{k=r}^n \binom{k-1}{r-1} \sum_{j=0}^{k-r} \binom{k-r}{j} (-p)^j.

Now, which terms in this double sum contain a p^m term?  Those in which j = m-r.  Thus the coefficient of p^m in this double sum is

\displaystyle \sum_{k=r}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r} = \sum_{k=m}^n \binom{k-1}{r-1} \binom{k-r}{m-r} (-1)^{m-r}

\displaystyle = (-1)^{m-r} \sum_{k=m}^n \frac{r}{k} \binom{k}{r} \binom{k-r}{m-r}, \text{ by the absorption identity}

\displaystyle = (-1)^{m-r} r \sum_{k=m}^n \frac{1}{k} \binom{k}{m} \binom{m}{r}, \text{ by trinomial revision}

\displaystyle = (-1)^{m-r} r \binom{m}{r} \sum_{k=m}^n \binom{k}{m} \frac{1}{k}

\displaystyle = (-1)^{m-r} r \binom{m}{r} \sum_{k=m}^n \binom{k-1}{m-1} \frac{1}{m}, \text{ by the absorption identity (again)}

\displaystyle = (-1)^{m-r} \frac{r}{m} \binom{m}{r} \sum_{k=m-1}^{n-1} \binom{k}{m-1}

\displaystyle = (-1)^{m-r} \binom{m-1}{r-1} \binom{n}{m}, \text{ by, once more, the absorption identity, plus the hockey stick identity}.

Now for the right side of Identity 1.  Expand (1-p)^{n-k} using the binomial theorem to get

\displaystyle \sum_{k=r}^n \binom{n}{k} p^k (1-p)^{n-k} = \sum_{k=r}^n \binom{n}{k} p^k \sum_{j=0}^{n-k} \binom{n-k}{j} (-p)^j.

As before, which terms in this contain a p^m term?  Those in which j = m-k.  Thus the coefficient of p^m in this double sum is

\displaystyle \sum_{k=r}^n \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k} =  \sum_{k=r}^m \binom{n}{k} \binom{n-k}{m-k} (-1)^{m-k}

\displaystyle = \sum_{k=r}^m \binom{n}{m} \binom{m}{k} (-1)^{m-k}, \text{ by trinomial revision}

\displaystyle = \binom{n}{m} \sum_{k=0}^{m-r} \binom{m}{m-k} (-1)^k, \text{ reindexing the sum}

\displaystyle = \binom{n}{m} \sum_{k=0}^{m-r} \binom{m}{k} (-1)^k

\displaystyle = \binom{n}{m} (-1)^{m-r} \binom{m-1}{r-1},

where the last expression comes from the formula for the partial alternating row sum of the binomial coefficients.

Posted in binomial coefficients, probability | Leave a comment

A Sum of Ratios of Binomial Coefficients

In this post we evaluate the sum \displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}.  Then we’ll generalize it and evaluate \displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}}.

The key tools we need for the first sum are the trinomial revision identity, \binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}, and the parallel summation identity, \sum_{k=0}^m \binom{n+k}{k} = \binom{n+m+1}{m}.  Using trinomial revision, we have

\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \sum_{k=0}^m \frac{\binom{n-k}{m-k}}{\binom{n}{m}} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-k}{m-k}.

We can evaluate the remaining sum using parallel summation, but we need to pull a variable switch first.  Replace k with m-k and then apply parallel summation to obtain

\displaystyle \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{k} = \frac{\binom{n+1}{m}}{\binom{n}{m}}.

We thus have the identity

\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \frac{\binom{n+1}{m}}{\binom{n}{m}} = \frac{n+1}{n+1-m},

where the last step follows thanks to some algebra simplification with factorials.

To evaluate the second sum we’ll need an identity that’s like an upper-index version of Vandermonde’s convolution: \sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} = \binom{m+n+1}{r+s+1}.  Otherwise, the derivation for the second sum proceeds just as the first one does up through the point where we replace k with m-k.  Continuing from there and applying the upper Vandermonde identity, we have

\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{k} \binom{m-k}{r} = \frac{1}{\binom{n}{m}} \sum_{k=0}^m \binom{n-m+k}{n-m} \binom{m-k}{r} = \frac{1}{\binom{n}{m}} \binom{n+1}{n-m+r+1}.

We can rewrite this and perform some more algebra simplification to get our generalization:

\displaystyle \sum_{k=0}^m \frac{\binom{m}{k}\binom{k}{r}}{\binom{n}{k}} = \frac{\binom{n+1}{m-r}}{\binom{n}{m}} = \frac{n+1}{m^{\underline{r}} (n+1-m)^{\underline{r+1}}}.

 

Posted in binomial coefficients | Leave a comment

An Alternating Convolution Identity via Sign-Reversing Involutions

This month’s post is on the combinatorial proof technique of sign-reversing involutions.  It’s a really clever idea that can often be applied to identities that feature alternating sums.  We’ll illustrate the technique on the following identity.

\displaystyle \sum_{k=0}^m \binom{n}{k} \binom{n}{m-k} (-1)^k = (-1)^{m/2} \binom{n}{m/2} [ m \text{ is even}].

(Here, we use the Iverson bracket notation [A], where [A] is 1 if A is true and 0 if A is false.)

This identity is interesting because there’s a lot going on here.  For one, it’s an alternating version of the famous Vandermonde identity.  But what’s happening with the right side?  Why is it zero when m is odd, and why does the parity of m/2 matter?  The sign-reversing involution technique will help us make sense of all of that.

First, \binom{n}{k} \binom{n}{m-k} can be thought of in terms of counting ordered pairs (A,B), each of which is a subset of \{1, 2, \ldots, n\}.  However, the choice of (A,B) is subject to the restriction that |A| = k and |B| = m-k.  The alternating sum on the left side of the identity is taken over all such pairs such that |A| + |B| = m, where the parity of a particular (A,B) is the parity of |A|.

We now have a combinatorial interpretation of the left side.  Now, let’s define the sign-reversing involution.  Given (A,B), let x denote the largest element in the symmetric difference A \oplus B of A and B; i.e., A \oplus B = (A-B) \cup (B-A).  Let

\displaystyle \phi(A,B) = \begin{cases} (A-\{x\}, B \cup \{x\}), & x \in A; \\ (A \cup \{x\}, B - \{x\}, & x \in B.\end{cases}

Note that \phi takes an ordered pair (A,B) such that A, B \subseteq \{1, 2, \ldots, n\} and |A| + |B| = m and maps it to another such ordered pair.  Moving the largest element x in the symmetric difference of A and B to the other set changes the number of elements in A by one and thus the parity of |A|.  This means \phi is sign-reversing.  In addition, \phi(A,B) has the same largest element x in its symmetric difference that (A,B) does; thus applying \phi to \phi(A,B) just sends x back to its original set.  Thus \phi(\phi(A,B)) = (A,B), which makes \phi an involution.

These two properties mean that \phi associates an ordered pair (A,B) of the kind we’re examining with another ordered pair that has a different parity.  Each of these pairs cancels out its associated pair in terms of evaluating the alternating sum on the left side of the identity we’re trying to prove.  Since every pair (A,B) has an associated pair that cancels it out, we have that the right side of our identity is the number of pairs (A,B) for which \phi is not defined.  Let’s count those leftover pairs now.

The only way for \phi to be undefined is for the largest element x in A \oplus B to not exist.  But that can only happen if A-B = \emptyset = B-A; in other words, A = B.  In this case, though, since |A| + |B| = m, we have |A| = |B| = m/2.  Thus when m is odd, there are no pairs (A,B) on which \phi is undefined; hence the right side of the identity is 0 when m is odd.  When m is even, there are \binom{n}{m/2} ways to choose the elements of A, and since B = A, this choice also determines B.  Since for all of these pairs A has m/2 elements, the parity of these leftover elements is the parity of m/2.

In general, this is how a sign-reversing involution argument works: Find a combinatorial interpretation of the terms in the left side of the alternating sum, then find a sign-reversing involution that maps entities with odd parity to entities with even parity and vice versa.  Counting the entities that are left over – i.e., those not paired up by the involution – will yield the right side of the identity.

For more sign-reversing involution arguments, see this post and this post.  Chapter 6 of Benjamin and Quinn’s Proofs that Really Count [1] and Chapter 5 of Aigner’s A Course in Enumeration [2] have examples as well.

(For what it’s worth, the identity can be proved more easily using generating functions, but I don’t think that approach gives as much insight into why the identity is true.)

References

  1.  Arthur T. Benjamin and Jennifer J. Quinn.  Proofs that Really Count.  MAA, 2003.
  2. Martin Aigner.  A Course in Enumeration.  Springer, 2010.

 

Posted in binomial coefficients, combinatorics | Leave a comment