Six Proofs of a Binomial Identity

I’m a big fan of proving an identity in multiple ways, as I think each perspective gives additional insight into why the identity is true.  In this post we’ll work through six different proofs of the binomial identity \displaystyle \sum_{k=0}^n \binom{n}{k} k = n 2^{n-1}.

1. The absorption identity proof.

The absorption identity states that, for real n, k \binom{n}{k} = n \binom{n-1}{k-1}.  Thus we have

\displaystyle \sum_{k=0}^n \binom{n}{k} k = \sum_{k=0}^n \binom{n-1}{k-1} n = n \sum_{k=-1}^{n-1} \binom{n-1}{k} = n \sum_{k=0}^{n-1} \binom{n-1}{k} = n 2^{n-1}, recalling that \binom{n-1}{-1} = 0.

2. The combinatorial proof.

How many chaired committees of any size can be formed from a group of n people?

One way to count them is to choose the committee first and then choose the chair.  First, we condition on the size of the committee.  If there are k people on the committee, there are \binom{n}{k} ways to choose the people to be on the committee.  Then there are k ways to choose the chair.  Summing up over all possible values of k, we find that the answer is \sum_{k=0}^n \binom{n}{k} k.

Another way is to choose the chair first and then choose the committee.  There are n choices for the chair.  Then, for each of the remaining n-1 people, we have two options: Each person could be on the committee or not.  Thus there are 2^{n-1} ways to choose the committee once the chair is chosen.  This gives an answer of n 2^{n-1} when choosing the chair first.

Since the two answers must be equal, we have \displaystyle \sum_{k=0}^n \binom{n}{k} k = n 2^{n-1}.

3. The calculus proof.

Differentiate the binomial theorem, \displaystyle \sum_{k=0}^n \binom{n}{k} x^k = (x+1)^n, with respect to x to obtain \displaystyle \sum_{k=0}^n \binom{n}{k} k x^{k-1} = n(x+1)^{n-1}.  Letting x = 1, we have \displaystyle \sum_{k=0}^n \binom{n}{k} k = n 2^{n-1}.

4. The probabilitistic proof.

Imagine an experiment where you flip a fair coin n times.  What is the expected number of heads for this experiment?

One way to determine this starts by conditioning on the number k of heads.  If there are k heads, there are \binom{n}{k} ways of choosing which k flips will be the heads.  The probability that these flips are all heads is (1/2)^k, and the probability that the remaining flips are all tails is (1/2)^{n-k}.  Multiply these together and apply the definition of expected value to get an answer of \displaystyle \sum_{k=0}^n \binom{n}{k} k \left(\frac{1}{2} \right)^k \left(\frac{1}{2} \right)^{n-k} = \sum_{k=0}^n \binom{n}{k} k \left( \frac{1}{2} \right)^n = \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} k.

Another way is to use indicator variables.  Let X_k be 1 if flip k is heads and 0 if flip k is tails.  Then the number of heads in the sequence of n flips is \sum_{k=0}^n X_k.  Also, the expected value of X_k is, by definition, E(X_k) = 1 (1/2) + 0 (1/2) = 1/2.  Thus the expected number of heads is E \left( \sum_{k=0}^n X_k \right) = \sum_{k=0}^n E(X_k) = \sum_{k=0}^n (1/2) =n/2.  (This is a formal way of arguing for the answer of n/2 that our intuition says should be the expected number of heads.)

Equating our two answers, we have \displaystyle \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} k = \frac{n}{2}, which implies \displaystyle \sum_{k=0}^n \binom{n}{k} k = n 2^{n-1}.

5. The exponential generating functions proof

For this proof we’re going to need a definition and a few properties of exponential generating functions.

First, the binomial convolution of the sequences (a_n) and (b_n) is given by \displaystyle \sum_{k=0}^n \binom{n}{k} a_k b_{n-k}.

Second, we have the following.  (See, for example, pages 126-128 of my book The Art of Proving Binomial Identities. [1])

  1. If \displaystyle f_a(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} and \displaystyle f_b(x) = \sum_{n=0}^{\infty} b_n \frac{x^n}{n!} then \displaystyle f_a(x) f_b(x) = \sum_{n=0}^{\infty} \left(\sum_{k=0}^n \binom{n}{k} a_k b_{n-k} \right) \frac{x^n}{n!}.  (This is the binomial convolution property for exponential generating functions.)
  2. We have \displaystyle e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}.  (This is the Maclaurin series for e^x.)
  3. If \displaystyle f_a(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} then x f_a(x) is the exponential generating function for the sequence given by (n a_{n-1}) = (0, a_0, 2a_1, 3a_2, \ldots).

By the definition of binomial convolution, \sum_{k=0}^n \binom{n}{k} k is the binomial convolution of the sequences with a_n = n and b_n = 1.  What are the exponential generating functions of these two sequences?

By Property 2, the exponential generating function for the sequence (b_n), with b_n = 1, is e^x.

If we take the sequence 1, 1, 1, \ldots, append a 0 to the front, and multiply it by n, we have the sequence with a_n = n.  By Property 3, then, the exponential generating function for the sequence (a_n) is x e^x.

Thus, by Property 1, the exponential generating function for \sum_{k=0}^n \binom{n}{k} k is x e^x (e^x) = x e^{2x}.  However, \displaystyle e^{2x} = \sum_{k=0}^{\infty} \frac{(2x)^k}{k!} = \sum_{k=0}^{\infty} \frac{2^k x^k}{k!}, which means that e^{2x} is the exponential generating function for the sequence (2^n).  Thus, by Property 3, x e^{2x} is also the exponential generating function for the sequence (n 2^{n-1}).   Since \left(\sum_{k=0}^n \binom{n}{k} k \right) and \left(n 2^{n-1}\right) have the same generating function, they must be equal, and so \displaystyle \sum_{k=0}^n \binom{n}{k} k = n 2^{n-1}.

6. The finite differences bootstrapping proof

This proof requires a result that I don’t think is that well-known.  It’s Theorem 4 in my paper “Combinatorial Sums and Finite Differences.” [2]

Theorem: Let (a_k) and (b_k) be sequences such that (a_k) is the finite difference sequence for (b_k); i.e., \Delta b_k = b_{k+1} - b_k = a_k for each k \geq 0.  If g_n = \sum_{k=0}^n a_k and h_n = \sum_{k=0}^n b_k then, for n \geq 0, \displaystyle h_n = 2^n \left( b_0 + \sum_{k=1}^n \frac{g_{k-1}}{2^k} \right).

First, if b_k = 1, then a_k = 0.  Thus g_n = 0, and, by the theorem, h_n = \sum_{k=0}^n \binom{n}{k} = 2^n.

Next, if b_k = k, then a_k = k+1 - k = 1.  By the theorem and the previous result, then, \displaystyle \sum_{k=0}^n \binom{n}{k} k = 2^n \left(0 + \sum_{k=1}^n \frac{2^{k-1}}{2^k} \right) = 2^n \sum_{k=1}^n \frac{1}{2} = 2^n \frac{n}{2} = n 2^{n-1}.

References 

  1. Spivey, Michael Z.  The Art of Proving Binomial Identities.  CRC Press, 2019.
  2. Spivey, Michael Z.  “Combinatorial Sums and Finite Differences.”  Discrete Mathematics, 307 (24): 3130-3146, 2007.
This entry was posted in binomial coefficients, calculus, combinatorics, generating functions, probability. Bookmark the permalink.

2 Responses to Six Proofs of a Binomial Identity

  1. jayprich says:

    Somewhat similar to your binomial convolution version, but what about writing exp(X).exp(Y)=exp(X+Y) .. expand each term of taylor series (or formal series) .. then consider X=Y=1?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s