## 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. 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.” 

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?

• mzspivey says:

Could you provide some more details on the steps of that argument?