I have the following sequence:
$ \sum\limits_{k=1}^n k\binom{n-1}{k-1} $
What is the sum of this sequence.
I have the following sequence:
$ \sum\limits_{k=1}^n k\binom{n-1}{k-1} $
What is the sum of this sequence.
HINT: That $k-1$ in the binomial coefficient is a little ugly, and the index starts at $k=1$, so why not shift it? Then you get
$\begin{align*} \sum_{k=1}^n\binom{n-1}{k-1}k&=\sum_{k=0}^{n-1}\binom{n-1}k(k+1)\\ &=\sum_{k=0}^{n-1}\binom{n-1}kk+\sum_{k=0}^{n-1}\binom{n-1}k\;.\tag{1} \end{align*}$
You should immediately recognize the second summation in $(1)$. The first isn’t quite so obvious, but if you apply a useful standard identity, you can turn it into something pretty straightforward:
$k\binom{n}k=\frac{kn!}{k!(n-k)!}=\frac{n!}{(k-1)!(n-k)!}=\frac{n(n-1)!}{(k-1)!(n-k)!}=n\binom{n-1}{k-1}\;.$
We have by the Binomial Theorem $(1+x)^{n-1}=\sum_{j=0}^{n-1}\binom{n-1}{j}x^j=\sum_{k=1}^n \binom{n-1}{k-1}x^{k-1}.$ Let $f(x)=x(1+x)^{n-1}.\tag{$1$}$ Then $f(x)=\sum_{k=1}^n \binom{n-1}{k-1}x^{k}$, and therefore $f'(x)=\sum_{k=1}^n k\binom{n-1}{k-1}x^{k-1}.$ It follows that our sum is $f'(1)$. But $f'(1)$ is easy to find from Expression $(1)$.
$\sum_{k=1}^n \binom{n-1}{k-1}\cdot k$ $=\sum_{k=1}^n \binom{n-1}{k-1}+\sum_{k=1}^n \binom{n-1}{k-1}\cdot(k-1)$
Now, $ \binom{n-1}{k-1}\cdot(k-1)=\frac{(n-1)!}{\{n-1-(k-1)\}!(k-1)!}\cdot(k-1)$
$=(n-1)\frac{(n-2)!}{\{n-2-(k-2)\}!(k-2)!}=(n-1)\binom{n-2}{k-2}$
$\sum_{k=1}^n \binom{n-1}{k-1}\cdot k$ $=\sum_{k=1}^n \binom{n-1}{k-1}+(n-1)\sum_{k=1}^n\binom{n-2}{k-2}$
$=\sum_{r=0}^{n-1} \binom{n-1}{r}+(n-1)\sum_{s=0}^{n-2}\binom{n-2}{s}$ as $\binom{n}{r}=0$ if $r<0$ or $r>n$
$=(1+1)^{n-1}+(n-1)(1+1)^{n-2}=2^{n-2}(2+n-1)=(n+1)2^{n-2} $