The Art of Proving Binomial Identities is Now Available

A couple of months ago I posted that my book, The Art of Proving Binomial Identities, would soon be finished.  Well, it’s out now, and you can buy it straight from the publisher (CRC Press).  It’s up on Amazon as well.

The March blog post summarizes the contents of the book, but there is one other feature of it I’d like to highlight.  In addition to the usual index of topics, I added an index of identities and theorems.  Every identity and theorem in the book appears in this index, with page numbers indicating exactly where.  My intent was for this to facilitate one of my main goals with the book: Understanding particular binomial identities better by looking at them through multiple lenses.  For example, the references to Identity 24, $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1}$ (which I used in my last post), lead you to proofs of it that involve the absorption identity, integration, the beta function, probability, generating functions, finite differences, and mechanical summation.  Each proof gives another perspective on why Identity 24 is true.

Also, at some point within the past couple of months I needed to find a particular binomial identity.  Sure enough, it was in the index!  That was gratifying.

(There are a couple of small errors on the CRC site.  First, I am no longer department chair, as I finished my three-year term in 2018.  I was department chair when I submitted the book proposal, and I corrected it on the info sheet I was sent a couple of months back, but for some reason it didn’t get updated on the CRC site.  Second, there is a chapter on mechanical summation that didn’t make it into the site’s description of the Table of Contents.  I suspect this is because the TOC list is from the original draft of the book I sent CRC, and the mechanical summation chapter was added later.)

Sum of the Reciprocals of the Binomial Coefficients

In this post we’re going to prove the following identity for the sum of the reciprocals of the numbers in column k of Pascal’s triangle, valid for integers $k \geq 2$:

Identity 1: $\displaystyle \sum_{n=k}^{\infty} \frac{1}{\binom{n}{k}} = \frac{k}{k-1}.$

The standard way to prove Identity 1 is is to convert the binomial coefficient in the denominator of the left side to an integral expression using the beta function, swap the integral and the summation, and pull some algebraic tricks with derivatives to sum the infinite series and then evaluate the integral.  (See, for example, the proof of Identity 107 on pages 77-78 of my upcoming Art of Proving Binomial Identities.)  In this post, though, we’re going to show how one can prove this identity using just three simple binomial identities:

Identity 2: $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+x} = \frac{n!}{x(x+1) \cdots (x+n)},$

Identity 3: $\displaystyle \sum_{k=0}^m \binom{n}{k} (-1)^k = (-1)^m \binom{n-1}{m},$

Identity 4: $\displaystyle \sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{k+1} = \frac{1}{n+1}$.

Identity 2 is your basic partial fractions decomposition formula when the factors in the denominator are consecutive integers.  Identity 3 gives the formula for the partial alternating row sum of the binomial coefficients.  Identity 4 is perhaps less well-known, but it does have a nice interpretation as two different ways of expressing the probability of drawing the red ball from a jar containing one red ball and n numbered blue balls.  (These are Identities 109, 20, and 24, respectively, in The Art of Proving Binomial Identities.)

On to the proof.

Proof of Identity 1.

First, let’s rewrite the summand of Identity 1 as a fraction with consecutive integer factors and apply Identity 2:

$\displaystyle \frac{1}{\binom{n}{k}} = \frac{k!}{(n-k+1) \cdots n} = k \frac{(k-1)!}{(n-k+1) \cdots n} = k \sum_{j=0}^{k-1} \binom{k-1}{j} \frac{(-1)^j}{j + n - k+1}.$

This gives the left side of Identity 1 as

$\displaystyle k \sum_{n=k}^{\infty} \sum_{j=0}^{k-1} \binom{k-1}{j} \frac{(-1)^j}{j + n - k+1}.$

Now, let’s transform the region of summation (just as we might transform the region of integration in a double integral) from an $(n,j)$ space to an $(i,j)$ space, where $i = j+n-k+1$.  The idea here is that we want to see what happens when we fix a particular denominator and sum over all the numerator expressions for that denominator.  The original region of summation in $(n,j)$ space looks like an infinite rectangle whose three finite sides are $n = k, j = 0$, and $j = k-1$.  The transformed region of summation looks like an infinite trapezoid whose three finite sides are $i = j+1, j = 0$, and $j = k-1$.  With the diagonal side $i = j+1$, we have to split the infinite series into two parts, one with i running from 1 to $k-1$ and one with i running from k to infinity.

Thus, we have $\displaystyle k \sum_{n=k}^{\infty} \sum_{j=0}^{k-1} \binom{k-1}{j} \frac{(-1)^j}{j + n - k+1} = k \sum_{i=1}^{k-1} \frac{1}{i} \sum_{j=0}^{i-1} \binom{k-1}{j} (-1)^j + k \sum_{i=k}^{\infty} \frac{1}{i} \sum_{j=0}^{k-1} \binom{k-1}{j} (-1)^j.$

Identity 3 tells us how to evaluate the two inner sums, leaving us (as the second inner sum is zero) with

$\displaystyle \sum_{n=k}^{\infty} \frac{1}{\binom{n}{k}} = k \sum_{i=1}^{k-1} \frac{1}{i} \sum_{j=0}^{i-1} \binom{k-1}{j} (-1)^j = k \sum_{i=1}^{k-1} \binom{k-2}{i-1}\frac{(-1)^{i-1}}{i} = k \sum_{i=0}^{k-2} \binom{k-2}{i}\frac{(-1)^i}{i+1} = \frac{k}{k-1},$

where the last step follows from Identity 4.

| 1 Comment

The Art of Proving Binomial Identities

I recently finished a book, The Art of Proving Binomial Identities, that will be published by CRC Press later this year.  We’re past the page proofs stage, and I think all that’s left on my end is to provide a little input on the cover the CRC folks are creating.  For this post I thought I would talk a little about the background of the book, as well as what’s in it.  (UPDATE: Here’s a link to the book’s web page on the CRC site.)

Back in 2010-11 I spent a fair amount of time on what was then a new mathematics question-and-answer web site, Mathematics Stack Exchange.  The questions on Math.SE range from calculus homework problems to the occasional research-level mathematics question.  Since multiple answers are allowed for the same question, sometimes you’ll see several creative solutions for the same problem.  I became particularly intrigued by all the different ways for proving various binomial coefficient identities.  (See, for example, the answers to this question.)  However, I couldn’t find a text anywhere that pulled together all of the different methods for proving binomial identities that I was seeing on Math.SE.  So I decided to write one.  The result, many years later, is The Art of Proving Binomial Identities.

The book has ten chapters.

1. Introduction.  This chapter introduces the binomial coefficients and proves that four different definitions of the binomial coefficients are equivalent.  It also gives several proofs that the sum of row n in Pascal’s triangle is $2^n$.  The different proof techniques used give an overview of the text as a whole.
2. Basic Techniques.  This chapter is on a generalization of the binomial coefficient that allows us to prove Newton’s binomial series, binomial coefficients with negative upper indices (a special case of the just-considered generalization), the absorption identity (which has a perhaps-surprising number of applications), and binomial inversion.  The harmonic numbers make their first appearance, and we’ll see them here and there throughout the rest of the book.
3. Combinatorics.  Basic combinatorial interpretations of the binomial coefficients, such as committees and the number of successes in coin flips or ball selections, are used in this chapter to prove a variety of identities.  We also look at inclusion-exclusion, sign-reversing involutions, lattice path arguments, and choosing with replacement.  We also get our first look at the derangement numbers.
4. Calculus.  Differentiating and integrating the binomial theorem (sometimes repeatedly) can prove a lot of binomial identities.  We also look at the connection between Leibniz’s generalized product rule and the binomial theorem as well as the use of the gamma function and beta integral to prove more complicated binomial identities.
5. Probability.  The binomial, negative binomial, and hypergeometric distributions contain binomial coefficients in their probability mass functions.  Various manipulations of these pmfs, particularly moment calculations, can lead to several nice probabilistic interpretations of binomial identities.  We also introduce the technique of indicator variables in probabilistic arguments, discuss the extension of inclusion-exclusion to a probabilistic setting, and consider a probabilistic proof of the relationship between the beta integral and the binomial coefficients.
6. Generating Functions.  Generating functions are a powerful tool for proving identities.  We introduce the idea of a generating function and give several examples of their use in proving binomial identities, with particular focus on the negative binomial series, identities with central binomial coefficients, and convolution.  The last section in the chapter discusses exponential generating functions.  These are especially nice from a binomial coefficients point of view because binomial coefficients appear naturally in the sequence that is generated by the product of two egfs.
7. Recurrence Relations and Finite Differences.  This chapter introduces recurrence relations as a tool for proving binomial identities.  The bulk of the chapter, though, is devoted to exploring the relationship between binomial coefficients and finite differences.  It turns out, for instance, that the binomial coefficients arise naturally when taking repeated finite differences of the same sequence.  In addition, we discuss the relationship between the binomial transform of a sequence and the binomial transform of the finite difference of that sequence, a relationship I first explored in a paper [1] I wrote a while back.  In the last section we prove how the factorial formula for the binomial coefficients can be derived from its recurrence relation without knowing the formula in advance (a derivation which first appeared in a recent paper [2] of mine).
8. Special Numbers. The inspiration for this chapter is the chapter of the same name in the classic text Concrete Mathematics, although not all the numbers discussed are the same.  There are sections on the Fibonacci numbers, both kinds of Stirling numbers, the Bell numbers, the Lah numbers, the Catalan numbers (including more sophisticated lattice path arguments than we saw in Chapter 3), and the Bernoulli numbers.
9. Miscellaneous Techniques.  The two techniques discussed in this chapter are the use of complex numbers and linear algebra to prove binomial identities.  Substituting the imaginary unit i into the binomial theorem and separating real and imaginary parts leads to proofs of binomial identities that can be difficult to prove otherwise.  We then generalize this idea by using complex roots of unity in place of i.  For the second technique, placing Pascal’s triangle into a matrix and using matrix operations can also lead to quick proofs and new perspectives on binomial identities.  In particular, the binomial inversion technique from Chapter 2 turns out to be matrix inversion in disguise.  We also consider matrices containing Stirling, Lah, and Fibonacci numbers.
10. Mechanical Summation.  This chapter is devoted to an explanation of the automated identity proving techniques for hypergeometric sums developed by Gosper and extended by Zeilberger.  The three sections are on (1) hypergeometric series and notation, (2) Gosper’s algorithm, and (3) Zeilberger’s extension to Gosper’s algorithm.

Finally, there is an appendix containing hints and/or a solution to every problem in the text, an index of identities appearing in the text, and a general index.

References

1. Michael Z. Spivey, “Combinatorial Sums and Finite Differences,” Discrete Mathematics, 307 (24): 3130-3146, 2007.
2. Michael Z. Spivey, “The Binomial Recurrence,” Mathematics Magazine, 89 (3): 192-195, 2016.
Posted in binomial coefficients, publishing | 1 Comment

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?

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.

Posted in games, teaching | 1 Comment

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.

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 | 2 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.