Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following sequence:

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

What is the sum of this sequence.

share|improve this question
    
What have you tried? –  Stefan Nov 3 '12 at 17:06
    
@Stefan And now we will never know... –  Did Nov 3 '12 at 17:14
add comment

3 Answers 3

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:

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

share|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
add comment

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

share|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.