# Proving a summation involving binomial coefficients.

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

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$

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

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