Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following sequence:

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

What is the sum of this sequence.

share|cite|improve this question
@Stefan And now we will never know... – Did Nov 3 '12 at 17:14
up vote 2 down vote accepted

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:


share|cite|improve this answer
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)$.

share|cite|improve this answer

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


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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.