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
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}
No comments:
Post a Comment