Prove $\sum \limits_{k=0}^{n} (k+1){n \choose k} = 2^{n-1} (n+2)$

Question

How can I prove this statement using induction? Im stuck at getting the Induction step simplified:

$\sum \limits_{k=0}^{n+1} (k+1){n+1 \choose k} = 2^{n+1-1} (n+1+2)$

Answer 1

Under the assumption that $$\sum_{k=0}^n\binom{n}{k}(k+1)=2^{n-1}(n+2)$$ we need to complete the inductive step by showing that $$\sum_{k=0}^{n+1}\binom{n+1}{k}(k+1)=2^{n}(n+3).$$ The main annoying issue here that we must find a way to get around is the binomial coefficient $\binom{n+1}{k}$. We have to eventually use the inductive hypothesis with the binomial coefficient $\binom{n}{k}$, but we can't do so directly when the left hand side of what we want to prove has $\binom{n+1}{k}$---so what we need to do now is to simplify $\binom{n+1}{k}$ into something in terms of $\binom{n}{k}$ to apply the inductive hypothesis.

The way to do so is by the following identity:

$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$ for all positve integers $n,k$ with $k\leq n$.

There are many ways to prove this equality, for example by just invoking the explicit formula for the binomial coefficient $\binom{n}{k}=\frac{n!}{k!(n-k)!}$. Now we are already almost done. We simplify: $$\begin{split}\sum_{k=0}^{n+1}\binom{n+1}{k}(k+1)&=\sum_{k=0}^{n+1}\binom{n}{k}(k+1)+\sum_{k=0}^{n+1}\binom{n}{k-1}(k+1)\\ &=2^{n-1}(n+2)+\sum_{k=0}^n\binom{n}{k}(k+2)\\&=2^{n-1}(n+2)+\sum_{k=0}^n\binom{n}{k}(k+1)+\sum_{k=0}^n\binom nk\\&=2\times 2^{n-1}(n+2)+2^n = 2^n(n+3),\end{split}$$ as desired. Make sure you think through what I did above to see the two places where I invoked the inductive hypothesis, and why that was made possible by the manipulation to split up $\binom{n+1}{k}$ into something that looks like $\binom{n}{k}$. Also note the places where the indexing variables don't seem to match up with what's in the inductive hypothesis, and convince yourself that what I did was indeed valid by e.g. writing out small cases. Once you've done so, the inductive proof should become more transparent.

Answer 2

Hint : Have you tried using Pascal's triangle for the induction step

In summary. Suppose that this is a true for $n$: $$ I.H. \ : \sum_{k=0}^n (k+1)\binom{n}{k} = 2^{n-1}(n+2)$$

And you want to value $$ S = \sum_{k=0}^{n+1} (k+1)\binom{n+1}{k} $$

If it's easier for you, you can start removing the case $k=0$ and $k=n+1$, $$ S = 1 + (n+2) + \sum_{k=1}^{n} (k+1)\binom{n+1}{k}$$

and then using Pascal's triangle $$ S = 1 + (n+2) + \sum_{k=1}^{n} (k+1)\left[\binom{n}{k}+\binom{n}{k-1}\right]$$

Can you finish using the induction hypothesis? Try to transform this last sum in order to use the induction hypothesis.

Start by splitting the sum is two, the first one is almost the induction hypothesis, lacking the initial term $k=0$.

Edit you will also need the fact that $$ \sum_{k=0}^n \binom{n}{k} = 2^n$$