Can't understand an equality between sums

Question

During an induction proof I came across an equality that I can't understand. During the last step of the induction there is: $$ \sum_{k=1}^{n}{(k+1){n \choose k-1}} = \sum_{k=0}^{n-1}{(k+2){n \choose k}} $$

My question is which sum and combination identities were used to achieve this transformation. Using simply the index shift of sums I couldn't work out the same result. Edit: I understand that the equality stands, I can't understand how I can produce the RHS from the LHS. Which identities do I have to use?

Answer 1

If you're unfamiliar with index shifts, change the variable first. \begin{align} \sum_{k=1}^{n} (k+1)\binom{n}{k-1} &=\sum_{h=1}^{n} (h+1)\binom{n}{h-1} && \text{(change dummy variable)} \\ &=\sum_{k=0}^{n-1} (k+2)\binom{n}{k} && \begin{gathered} h-1=k \\ h+1=k+2 \\ \begin{aligned} & h=1\implies k=0\\ & h=n\implies k=n-1 \end{aligned} \end{gathered} \end{align}

Answer 2

Just write down the terms explicitly on both sides. The term corresponding to $k=1$ on LHS is same as the one corresponding to $k=0$ on RHS. The two sides are sums of exactly the same numbers.

Answer 3

Note that$$\sum_{k=1}^n(k+1)\binom n{k-1}=2\binom n0+3\binom n1+\cdots+(n+1)\binom nn$$and that$$\sum_{k=0}^n(k+2)\binom nk=2\binom n0+3\binom n1+\cdots+(n+1)\binom nn.$$So, you are summing the same numbers!