Section 5.3, Problem 36

Let

P(n)\equiv \sum_{k=0}^n k {n \choose k}=n2^{n-1}.

To show: P(n) for all n\in \mathbb N. Observe that it does not matter whether we start the sum from k=1 or k=0, as the summand for k=0 is zero.

The base case P(1) is easy to check, skipped here.

Induction step

Now suppose P(1),\dots, P(n-1) is true. We need to show that P(n) is true. P(n) involves computing the following sum, from which we split off the last summand:

\sum_{k=0}^n k {n \choose k} = \sum_{k=0}^{n-1} k {n \choose k} + n \underbrace{{n \choose n}}_1=(*).

The remaining sum unfortunately does not conform to the induction hypothesis. We use the identity

{n\choose k} = {n-1\choose k} +{n-1\choose k-1}
to 'help a little'.

(*) = \sum_{k=0}^{n-1} k \left({n-1\choose k} +{n-1\choose k-1}\right) + n=\sum_{k=0}^{n-1} k {n-1\choose k} +\sum_{k=0}^{n-1} k {n-1\choose k-1} + n.

On the first sum we can now use the induction hypothesis.

(*) = (n-1)2^{n-2}+\sum_{k=0}^{n-1} k {n-1\choose k-1} + n.

Now what can we do with the remaining sum? First, we change the start of the sum to k=1, with no change in value:

(*) = (n-1)2^{n-2}+\sum_{k=1}^{n-1} k {n-1\choose k-1} + n.

The next step towards making the sum look like the induction hypothesis consists of adding an subtracting another sum:

(*) = (n-1)2^{n-2}+\sum_{k=1}^{n-1} (k-1) {n-1\choose k-1} + \sum_{k=1}^{n-1} {n-1\choose k-1} + n.

We know an expression for the second sum by either the binomial theorem or Problem 35:

\sum_{k=1}^{n-1} {n-1\choose k-1} + n \underbrace=_{l=k-1}\sum_{l=0}^{n-1} {n-1\choose l}=2^{n-1}-1.

Plug that in and we get:

(*) = (n-1)2^{n-2}+\sum_{k=1}^{n-1} (k-1) {n-1\choose k-1} + 2^{n-1} - 1+ n.

Let l=k-1, and the remaining sum changes to

(*) = (n-1)2^{n-2}+\sum_{l=0}^{n-2} l {n-1\choose l} + 2^{n-1} - 1+ n.

We are now ready to use the induction hypothesis one last time, noting that the last entry of the sum is missing:

(*) = (n-1)2^{n-2}+ (n-1)2^{n-2} - (n-1){n-1\choose n-1} + 2^{n-1} - 1+ n.

(*) = (n-1)2^{n-2}+ (n-1)2^{n-2} - (n-1) + 2^{n-1} - 1+ n.

Now clean up the mess:

(*) = (n-1)2^{n-1}+ (n-1) + 2^{n-1} - 1+ n.

(*) = n2^{n-1}+ (n-1) - 1+ n= n2^{n-1}.

(This is long and laborious, but not really hard. A non-inductive three-liner proof also exists, but that is too close to something that will be on the final, so I won't go into it here. Feel free to hunt for it on your own time, though.) :)