Grant Sanderson, who runs the excellent mathematics YouTube channel 3Blue1Brown, recently posted a video premised around introducing generating functions, and how they can be used to solve problems. At the end of the video he gives four puzzles for further exploring generating functions. One of them was this:
Compute the sum \sum\limits_{k=0}^n2^k\binom{n}{k}.
(Hint, expand the expression (1+x)^n.)
First, let’s look at that sum.
\sum\limits_{k=0}^n2^k\binom{n}{k} = 2^0\binom{n}{0} + 2^1\binom{n}{1} + \dots + 2^{k-1}\binom{n}{k-1} + 2^k\binom{n}{k}.
Doing as the hint says,
(1+x)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1} + \dots + \binom{n}{k-1}x + \binom{n}{k}.
This gives us a polynomial with coefficients close to that of the desired sum. We’re just missing the powers of 2, which can be easily added in by changing the binomial we’re expanding.
(2 + x)^n = 2^0\binom{n}{0}x^n + 2^1\binom{n}{1}x^{n-1} + \dots + 2^{k-1}\binom{n}{k-1}x + 2^k\binom{n}{k}.
The coefficients of f(x) = (2 + x)^n are exactly those of the desired sum. So the sum be found by evaluating f(1) = (2 + 1)^n = 3^n. Thus, we get the answer that \sum\limits_{k=0}^n2^k\binom{n}{k} = 3^n.
That was a pretty surprising result. When I saw it, I thought, “3^n is the number of ways to make n choices when there are 3 options for every choice. I bet there’s an elegant combinatorial proof of this identity.”
Sure enough, there is, and it didn’t take too long to find.
Given a set of n objects, consider the number of different ways that Alice can choose k of those objects, 0\le k \le n, and then give a subset of the k objects she has chosen to Bob.
For any given value of k, Alice has \binom{n}{k} ways to choose k objects. She can then select any of the 2^k subsets of k to give to Bob. So, for a given k, the number of ways for Alice to choose k objects and then give some of them to Bob is 2^k\binom{n}{k}. Summing over all possible values Alice can choose for k gives \sum\limits_{k=0}^n2^k\binom{n}{k}.
But instead of first choosing k objects and then giving a subset of those to Bob, Alice could instead consider each of the original n objects and make one of three choices: leave it alone, take it for herself, or give it to Bob. Since there are three possible choices for each of n objects, the number of ways this can be done is 3^n.
Both of these methods count the number of ways the original set of n objects can be partitioned into three groups (Alice’s objects, Bob’s objects, and the leftover objects). Therefore, \sum\limits_{k=0}^n2^k\binom{n}{k} = 3^n. \blacksquare
I love this proof, and combinatorial proofs in general. While the generating function method is fascinating and no-doubt powerful, it doesn’t tell me why the identity is true. The combinatorial proof, though, tells me that the expressions are two different ways of looking at how to partition a set into three groups.
Now I’m curious if there’s a combinatorial solution to the problem that’s the main focus of the video.