Ways To Count

The purpose of this page is to present several proofs of an identity that involves binomial coefficients:

(1)

$\displaystyle {n \choose 1} + 2\cdot {n \choose 2} + 3\cdot {n \choose 3} + \ldots + n\cdot {n\choose n} = n2^{n-1}.$

Four such proofs have been collected in a 1999 issue of Crux Mathematicorum by Jimmi Chui, then a secondary school student. I found two more elsewhere and present all six below.

Pure Algebra

Let $S\;$ denotes the sum in (1). Using the basic property of the binomial coefficients $\displaystyle {n\choose k} = {n\choose n-k}\;$ we have

$\displaystyle \begin{align} S&= 0\cdot {n \choose 0} + 1\cdot {n \choose 1} + 2\cdot {n \choose 2} + \ldots + n\cdot {n \choose n}\\ &= 0\cdot {n \choose n} + 1\cdot {n \choose n-1} + 2\cdot {n \choose n-2} + \ldots + n\cdot {n \choose 0}\\ &= n\cdot {n \choose 0} + (n-1)\cdot {n \choose 1} + (n-2)\cdot {n \choose 2} + \ldots + 0\cdot {n \choose n}. \end{align}$

Adding the first and the last sums gives

$\displaystyle \begin{align} 2S&= n\cdot {n \choose 0} + n\cdot {n \choose 1} + n\cdot {n \choose 2} + n\cdot {n \choose 3} + \ldots + n\cdot {n \choose n}\\ &= n\cdot 2^{n}, \end{align}$

which immediately implies (1).

Mathematical Induction

We shall prove (1) by mathematical induction. For $n = 1,$ there is nothing to prove. Assume (1) holds for some $n = k:$

(2)

$\displaystyle {k \choose 1} + 2\cdot {k \choose 2} + 3\cdot {k \choose 3} + \ldots + k\cdot {k \choose k} = k2^{k-1}.$

If the left side (2) is denoted $S(k),\;$ we have using the addition formula

$\displaystyle \begin{align} S(k+1)&= {k+1\choose 1} + 2\cdot {k+1\choose 2} + 3\cdot {k+1\choose 3} + \ldots + (k+1)\cdot {k+1\choose k+1}\\ &= 1\cdot \left({k \choose 0} + {k \choose 1}\right) + 2\cdot \left({k \choose 1} + {k \choose 2}\right) + \ldots + k\cdot \left({k\choose k-1} + {{k\choose k}}\right) + (k+1){k \choose k}\\ &= 1\cdot {k \choose 0} + 3\cdot {k \choose 1} + 5\cdot {k \choose 2} + \ldots + (2k+1){k \choose k}\\ &= \left({k \choose 0} + {k \choose 1} + {k \choose 2} + \ldots + {k \choose k}\right) + 2\cdot S(k)\\ &= 2^{k} + 2\cdot k\cdot 2^{k-1}\\ &= (k + 1)\cdot 2^{k}.\\ \end{align}$

Generating functions

Consider the generating function for the binomial coefficients:

$\displaystyle f(x) = {n \choose 0} + {n \choose 1}\cdot x + {n \choose 2}\cdot x^{2} + \ldots + {n \choose n}\cdot x^{n}.$

The derivative of which is

$\displaystyle f'(x) = {n \choose 1} + 2\cdot {n \choose 2}\cdot x^{1} + \ldots + n\cdot {n \choose n}\cdot x^{n-1}.$

So that $f'(1) = S(n).\;$ On the other hand, by the binomial theorem,

$f(x) = (1 + x)^{n},$

with the derivative

$f'(x) = n(1 + x)^{n-1},$

from which $f'(1) = n2^{n-1}.$

For the record, what we found is that $n(1 + x)^{n-1}\;$ is the generating function for the sequence $\displaystyle{k{n\choose k}}.$ This observation leads directly to the evaluation of the average in the binomial distribution.

Combinatorial Proof 1

Consider a set of $n\;$ people. We shall answer the question, "In how many ways it is possible to select a (non-empty) committee and its chairperson from the set of $n\;$ people?" We shall answer the question in two ways.

There are $\displaystyle {n\choose k}\;$ committees with $k\;$ members $k \ge 1\;$ and, for each, there are $k\;$ choices of a chairperson. Thus $S(n)\;$ is the total number of such committees with a chair.

We may also start by selecting the chairperson first and then complementing the committee by regular members out of the remaining $n-1\;$ fellows. There are $n\;$ choices for the chairperson and $2^{n-1}\;$ possibilities for other members, which gives the right hand side in (1).

Combinatorial Proof 2

The expression $\displaystyle \frac{S(n)}{2^{n}}\;$ [Benjamin & Quinn, p. 66] also has a combinatorial interpretation. It answers the question, "What is the average size of a subset of $\{1, 2, \ldots , n\}?\;$" Indeed, there are exactly $\displaystyle {n\choose k}$ subsets with $k\;$ terms whereas $2^{n}\;$ is the total number of the subsets.

On the other hand, pair each subset with its complement. The two together have n terms and the average of $\displaystyle\frac{n}{2}.\;$ So that

$\displaystyle \frac{S(n)}{2^{n}} = \frac{n}{2},$

which is equivalent to (1).

Formula for Binomial Coefficients

Recollect that [Zeitz, p. 215]

$\displaystyle {n\choose k} = \frac{n!}{k!(n-k)!}.$

Then

$\displaystyle S(n)=\sum_{k=1}^{n}\frac{k\cdot n!}{k!(n-k)!}.$

Thus

$\displaystyle\begin{align} S(n)&=\sum_{k=1}^{n}\frac{k\cdot n!}{k!(n-k)!}\\ &=\sum_{k=1}^{n}\frac{k\cdot n!}{k\cdot (k-1)!(n-k)!}\\ &=\sum_{k=1}^{n}\frac{n!}{(k-1)!(n-k)!}\\ &=\sum_{k=1}^{n}\frac{n\cdot (n-1)!}{(k-1)!(n-k)!}\\ &=n\cdot \sum_{k=1}^{n}\frac{n\cdot (n-1)!}{(k-1)![(n-1)-(k-1)]!} \end{align}.$

The derivation might have been shortened by a reference to the well known formula $\displaystyle k{n\choose k} = n{n-1\choose k-1},$ the absorbtion identity. The latter is verified directly from the definition of the binomial coefficients as was actually done above.

Absorbtion Identity

Applying the binomial theorem.

$\displaystyle\begin{align} S(n)&=n\cdot \sum_{k=1}^{n}{n-1\choose k-1}\\ &= n\cdot \left({n-1\choose 0} + {n-1\choose 1} + \ldots + {n-1\choose n-1}\right)\\ &= n\cdot 2^{n-1}. \end{align}$

References

A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Pascal's Triangle and the Binomial Coefficients

71534983