# Binomial sum of a sequence

I have the following sequence:

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

What is the sum of this sequence.

-
@Stefan And now we will never know... – Did Nov 3 '12 at 17:14

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

-
beautiful!! thanks! – user844541 Nov 3 '12 at 18:19
@Beeee: You’re welcome! – Brian M. Scott Nov 3 '12 at 18:22
is ther a formual to calculate $k^x\binom{n}k=$ ? I was able to solve it for $k^2$ and for $k^3$, but maybe there is one formula for every x? – user844541 Nov 4 '12 at 19:51
@Beeee: Do you mean a formula to calculate a similar sum with a factor of $k^m$ instead of $k$? I’d do it by repeated differentiation, using the idea that André used in his answer to this question. – Brian M. Scott Nov 6 '12 at 23:18
Thank you!You really helped me! – user844541 Nov 13 '12 at 7:09

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

-
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. – Brian M. Scott Nov 3 '12 at 18:06