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)$
Prove $\sum \limits_{k=0}^{n} (k+1){n \choose k} = 2^{n-1} (n+2)$
combinatoricsinductionsummation
Best Answer
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:
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.