Friday 22 May 2015

summation - Can't understand an equality between sums



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...