Section 5.3, Problem 36
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.
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:
The remaining sum unfortunately does not conform to the induction hypothesis. We use the identity
On the first sum we can now use the induction hypothesis.
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:
The next step towards making the sum look like the induction hypothesis consists of adding an subtracting another sum:
We know an expression for the second sum by either the binomial theorem or Problem 35:
Plug that in and we get:
Let l=k-1, and the remaining sum changes to
We are now ready to use the induction hypothesis one last time, noting that the last entry of the sum is missing:
Now clean up the mess:
(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.)