Derbyshire Math Problem of the Month

I'm trying to resist writing too much about one of my nerdy loves - math - on this blog, but every now and then I will give in to temptation. This is one of those times.

One of my favorite and unexpected phenomena in mathematics is when a general case turns out to be easier to prove than a specific case. This is counterintuitive, of course: usually, specific cases are easier. One famous example is Fermat's Last Theorem (which states that for n>2, there are no non-trivial integer solutions to the equation xⁿ + yⁿ = zⁿ). It's quite easy to prove this for the specific case n = 4. But the general case resisted all efforts at proof for hundreds of years (until Andrew Wiles finally succeeded in 1994).

The problem we're looking at today is simple to state. Consider the following pattern:

1 + 2 = 3
1x2 + 2x3 + 3x4 = 4x5
1x2x3 + 2x3x4 + 3x4x5 + 4x5x6 = 5x6x7

Prove that this pattern continues.

It's useful to turn this into a little "math-speak" before going any farther. We use the symbol "!" (read "factorial") to indicate the product of sequential integers. For example, 4! = 4x3x2x1 = 24. This only works for positive integers (there are ways to define "factorial" for other numbers, but they are well beyond the scope of this blog). It's pretty easily to express products like the ones in the problem above using factorials: 5x6x7 = 1x2x3x4x5x6x7/1x2x3x4 = 7!/4!. There's one other thing about factorials that needs to be said, and that is that 0! = 1. Don't worry too much about why this is so (one way to see it is the following relation: 3!/3 = 2!, 2!/2 = 1!, 1!/1 = 0!).

So we can rewrite the problem like this:

1 + 2 = 3
2!/0! + 3!/1! + 4!/2! = 5!/3!
3!/0! + 4!/1! + 5!/2! + 6!/3! = 7!/4!

But what about that first equation? From looking at the other two, it looks like we can write it like this:

1!/0! + 2!/1! = 3!/2!

And it fits. So the pattern can be written in a nice ordered way using factorials. We need to show this:

n!/0! + (n+1)!/1! + (n+2)!/2! + ... + (2n)!/n! = (2n+1)!/(n+1)!

It's worth looking at this for a minute or two and seeing how, if you substitute n = 1, 2, and 3, you get the three equations we've been writing down thus far. What we need to do is show that this works for any n.

So here's the interesting part: it turns out that this last equation is tough to prove directly. But a more general equation is pretty easy. Here's the more general one:

n!/0! + (n+1)!/1! + ... + (n+k)!/k! = (n+k+1)!/k!(n+1)

If we can show this is true, then setting k = n gives us the equation we want to prove.

First, suppose k = 0. Then our general equation says:

n!/0! = (n+0+1)!/0!(n+1)

That looks OK.

Second, let's look at that general equation again:

n!/0! + (n+1)!/1! + ... + (n+k)!/k! = (n+k+1)!/k!(n+1)

Suppose it's true. What happens if we add another term?

n!/0! + (n+1)!/1! + ... + (n+k)!/k! + (n+k+1)!/(k+1)! = (n+k+1)!/k!(n+1) + (n+k+1)!/(k+1)!

The right-hand side can be simplified:

= (n+k+1)!/k!(n+1) + (n+k+1)!/(k+1)!
= (n+k+1)!(k+1)/(k+1)!(n+1) + (n+k+1)!(n+1)/(k+1)!(n+1)
= [(k+1) + (n+1)] (n+k+1)!/(k+1)!(n+1)
= (n+k+2) (n+k+1)!/(k+1)!(n+1)
= (n+k+2)!/(k+1)!(n+1)

(I went through that pretty quickly, but almost all of the hard parts come from the fact that (n+1) times n! = (n+1)!, for example, 8x7! = 8!. That fact comes straight the definition of factorials.)

But take a look at that simplified right-hand side. We've just showed this:

n!/0! + (n+1)!/1! + ... + (n+k+1)!/(k+1)! = (n+k+2)!/(k+1)!(n+1)

which is just the general equation for k+1 instead of k. And that's good, because now we've inductively proved the general equation. See, we showed it worked for k=0, and then we showed that if it works for k, then it must work for k+1. So if it works for k=0 then it must work for k=1, which means it must work for k=2, and so on, ad infinitum. It works for all k. In particular, it works for k = n. And that's what we needed to show.