Combinatorial proofs

Continuing from a previous post, we found that if we begin with $n$ th powers of $(n+1)$ consecutive integers and then repeatedly take successive differences, it seems like we always end up with the factorial of $n$ , that is, $n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$ . We then derived an algebraic expression for the result of the iterative difference procedure. So the goal now is to prove that

$\displaystyle \sum_{i=0}^n (-1)^{n-i} \binom n i (k+i)^n = n!$

that is,

$\displaystyle (-1)^n \binom n 0 k^n + (-1)^{n-1} \binom n 1 (k+1)^n + \dots + \binom n n (k+n)^n = n!$

Now, it’s possible (probable, in fact) that this can be proved by purely algebraic means. If you come up with such a proof I would love to see it! But I must confess that I spent several hours banging my head against it (algebraically speaking) without making any progress. Eventually I turned to the idea of a combinatorial proof.

What do I mean by that? Combinatorics is the subfield of mathematics concerned with counting. The essence of a combinatorial proof is to show that two different expressions are just two different ways of counting the same set of objects—and must therefore be equal. I’ve described some combinatorial proofs before, in counting the number of ways to distribute cookies.

As another simple example, consider the binomial coefficient identity

$\displaystyle \binom n k = \binom {n-1}{k} + \binom{n-1}{k-1}$

It’s certainly possible to prove this algebraically, by expanding out the binomial coefficients (using $\binom n k = \frac{n!}{k!(n-k)!}$ ), but we can give a more elegant proof, based on the fact that $\binom n k$ is the number of ways to choose a subset of $k$ things out of a set of $n$ things. For example, here are the $\binom 5 3 = 10$ ways to choose three things out a set of five:

Consider the first element of the size- $n$ set. Every subset of size $k$ either includes this first element, or it doesn’t. The number of size- $k$ subsets which do not include the first element is $\binom{n-1}{k}$ , since that’s the number of ways to choose $k$ things from the remaining $n-1$ elements. The number of size- $k$ subsets which do include the first element is $\binom{n-1}{k-1}$ , because they correspond to choosing $k-1$ of the remaining $n-1$ things. Therefore $\binom n k = \binom{n-1}{k} + \binom{n-1}{k-1}$ .

Here’s an illustration of how this works in the particular case when $n = 5$ and $k = 3$ :

Notice how the ten subsets from above have been split into two groups: the first group, on the left, are those that don’t include the first element; you can see that each of them corresponds to one of the $\binom 4 3 = 4$ size- $3$ subsets of the remaining four elements. The second group, on the right, are those that do include the first element; each corresponds to one of the $\binom 4 2 = 6$ size- $2$ subsets of the remaining four elements.

So that’s the idea of a combinatorial proof. And we want to do something similar for the identity we are trying to prove—although, of course, it’s going to be a bit more difficult!

You might have fun trying to think about what a combinatorial proof of our target equation might look like; although if you don’t have much experience with combinatorics you may have trouble coming up with what sorts of things the two sides of the equation might be counting! That’s what I’ll talk about in my next post.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

12 Responses to Combinatorial proofs

AB says:

February 18, 2012 at 1:07 am

Well, I don’t know about algebraic, but if you notice that you are taking $x^n$ and differentiating it $n$ times, the fact that you get $n!$ as a result becomes not as surprising. And yes, this argument can be expanded into a proof.

I’m really waiting to see how you’ll do it combinatorially.
- Brent says:
  
  February 18, 2012 at 7:21 am
  
  Ah, interesting! I think I see what you are getting at—taking pairwise differences is a discrete analog of differentiation. I’m not sure I see how to work out the details, though. If you have time to expand it into something a bit more detailed I would certainly be interested to see it.
Jon wilson says:

February 18, 2012 at 4:29 am

Why do you have a ‘k’ in your alternate expression for the factorial of ‘n’? I think you may in fact mean n (instead of k)
Maybe that is why you had trouble proving it algebraically!
- Brent says:
  
  February 18, 2012 at 7:15 am
  
  It does look wrong, doesn’t it? But surprisingly, the k is in fact correct! It turns out that the equation is true for all values of k. This corresponds to the fact that we can start with any sequence of (n+1) consecutive integers and we still end up with the factorial of n; k represents the first integer in the sequence.
Matt Gardner Spencer says:

February 18, 2012 at 11:12 am

I have a proof, but I wouldn’t call it algebraic, since I’m taking derivatives. Start with the original sum. Expand out the $(k+i)^n$ and switch the order of summation, factoring out everything that is not in the inner sum.

Now go to the binomial theorem: $(1+x)^n=\sum_{j=0}^n{n\choose k}x^j.$ Taking derivatives and plugging in $x=-1$ gives you 0 on the left, and the terms of the inner sum on the right. At least for the first $n-1$ derivatives. The $n$ -th derivative gives you $n!$ on the left, and the very last term of the inner sum (and only for one value of the outer sum). So everything cancels except for one term: $n!$
- Brent says:
  
  February 18, 2012 at 11:30 am
  
  Ah, neat. Maybe this is what AB was referring to above.
Antony Goddard (@d4maths) says:

February 18, 2012 at 12:13 pm

If sequence space X is the set of sequences A = a[0],a[1],a[2]….

define the difference operator D A = {a[i+1]-a[i]}

The set of sequences where a[i] = some polynomial in i = P(i) is a vector space in X.
The difference operator D is linear: for scalars k and l, and polynomials p and q
D (kp+lq) = kDp+llDq
The the polynomials p(k,n) = n, n(n+1)/2, n(n+1)(n+2)/3, … n(n+1)(n+2)..(n+k-1)/k!
all satisfy the relation D p(k,n) = p(k-1,n) … easily proved by induction.
furthermore D is nilpotent on any particular polynomial. i.e. there exists k, D^k( p )= 0
we know D^k p(k,n) = 1
D^k (q) = 0 for polynomials of lower degree.

now p(k,n) = n^k/k! + lower order terms
D^k p(k,n) = 1 = (1/k!) * D^k (n^k)
D^k n^k = k!
Pingback: Another binomial sum » eon
Pingback: Making our equation count | The Math Less Traveled
Arie van der Velde says:

March 27, 2012 at 5:00 pm

Intriguing identity.. you may want to have a look at the following short article I came across:

Click to access page510-513.pdf

It explains how to prove finite sums with sine and cosine rules and differentiation. Looks rather clever and more creative than induction (which obviously was my first idea on the one above here, but turns out rather awkward soon..). The article technique is nice and I never saw it before.
In your case I guess you have to squeeze the k in the cosine arguments and probably you need to differentiate n times to get the (k+i)^n. I haven’t tried to work it out (maybe later;) so I don’t know if the binomial term nicely drops out, but it might be worth the try. the simpler examples of Lin suggest some factorial build-up (n*(n-1)*…) Best of luck! 😉
Steve says:

May 6, 2012 at 9:58 am

If you take consecutive values of a polynomial of degree n, and take first differences, you get values for a polynomial of degree n-1 whose leading coefficient (the one in $x^{n-1}$ ) is n times the leading coefficient in your original polynomial (the one in $x^n$ ).

Similarly, if you start with every kth value of a polynomial of degreen n and keep taking differences, you end up with $k^n n!$ times the original leading coefficient.

But your alternative proof is more interesting.
Pingback: Fibonacci multiples | The Math Less Traveled