1
$\begingroup$

I have the following sequence:

$ \sum\limits_{k=1}^n k\binom{n-1}{k-1} $

What is the sum of this sequence.

  • 0
    @Stefan And now we will never know...2012-11-03

3 Answers 3

2

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}\;.$

  • 0
    Thank you!You really helped me!2012-11-13
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)$.

0

$\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} $

  • 0
    I’m a firm believer that it isn’t homework until the OP says that it is, but when someone posts a question with no indication of where it came from or what’s been tried, a hint seems more appropriate than a full solution, at least when it’s possible to come up with one easily.2012-11-03