2
$\begingroup$

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png)

$$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$

And for the life of me I can't figure out how to express the formula with n+1 in terms of n.

$\endgroup$
1
$\begingroup$

Let $\displaystyle S=\sum_{i=0}^n i\binom ni,$

$\displaystyle j=n-i\implies S=\sum_{j=0}^n (n-j)\binom n{n-j}=\sum_{j=0}^n (n-j)\binom nj$ as $\displaystyle \binom nj=\binom n{n-j}$ $\displaystyle\implies S=\sum_{i=0}^n (n-i)\binom ni $

$\displaystyle\implies S+S=n\sum_{i=0}^n \binom ni$

Now, we can resort to this inductive proof and set $x=y=1$


Without Induction,

$$r\cdot\binom nr=r\cdot \frac{n\cdot(n-1)!}{r\cdot(r-1)!\cdot[(n-1)-(r-1)]!}=n\binom{n-1}{r-1}$$ for $0\le r\le n$ and $\binom nr=0$ for $r<0$ or $r>n$

Now, put $a=b=1 $ in $\displaystyle (a+b)^{n-1}=\sum_{r=0}^{n-1}\binom{n-1}ra^{n-1}b^r$

$\endgroup$
0
$\begingroup$

** I was going to withdraw this answer as it does not use induction, but decided to leave it anyway and take the criticism. Thanks lab bhattacharjee for setting me right**

Start with $$ (x+1)^n = \sum _i {n \choose i} x^i $$ and differentiate with respect to $x$ $$ n(x+1)^{n-1} = \sum _i {n \choose i} i x^{i-1} $$ Now set $x=1$ to get your identity $$ n ~2^{n-1} = \sum _i i~ {n \choose i} $$

$\endgroup$
  • $\begingroup$ Have you noticed "inductively"? $\endgroup$ – lab bhattacharjee Feb 4 '14 at 5:01
  • $\begingroup$ oops, I did not. I was busy editing his post $\endgroup$ – user44197 Feb 4 '14 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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