1. ## Binomial sum

Prove:

$\displaystyle \sum_{i=0}^{n}i^2{n\choose i}^2=n^2{2n-2\choose n-1}$

2. Originally Posted by streethot
Prove:

$\displaystyle \sum_{i=0}^{n}i^2{n\choose i}^2=n^2{2n-2\choose n-1}$
$\displaystyle \sum_i \binom{n}{i} x^i = (1+x)^n$.....(1)
Differentiate w.r.t. x, then multiply through by x:
$\displaystyle \sum_i i \binom{n}{i} x^i = n x (1+x)^{n-1}$....(2)
Take (2) * (2):
$\displaystyle \sum_i i \binom{n}{i} x^i \cdot \sum_j j \binom{n}{j} x^j = n^2 x^2 (1+x)^{2n-2}$
Consider the coefficient of $\displaystyle x^n$ in the preceding equation:
$\displaystyle \sum_i i (n-i) \binom{n}{i} \binom{n}{n-i} = n^2 \binom{2n-2}{n-2}$
Use $\displaystyle \binom{n}{i} = \binom{n}{n-i}$:
$\displaystyle \sum_i (n i - i^2) \binom{n}{i}^2 = n^2 \binom{2n-2}{n-2}$....3
Now it becomes apparent we are going to need to find
$\displaystyle \sum_i i \binom{n}{i}^2$, so consider (1) * (2):
$\displaystyle \sum_i \binom{n}{i} x^i \cdot \sum_j j \binom{n}{j} x^j = n x (1+x)^{2n-1}$.
Extracting the coefficient of $\displaystyle x^n$,
$\displaystyle \sum_i i \binom{n}{i} \binom{n}{n-i} = n \binom{2n-1}{n-1}$
so
$\displaystyle \sum_i i \binom{n}{i}^2 = n \binom{2n-1}{n-1}$ ....(4)
n * (4) - (3) yields
$\displaystyle n \sum_i i \binom{n}{i}^2 - \sum_i (n i - i^2) \binom{n}{i}^2 = n^2 \binom{2n-1}{n-1} - n^2 \binom{2n-2}{n-2}$
so
$\displaystyle \sum_i i^2 \binom{n}{i}^2 = n^2 \left( \binom{2n-1}{n-1} - \binom{2n-2}{n-2} \right) = n^2 \binom{2n-2}{n-1}$

3. Other solution
we know that

$\displaystyle i{n\choose i} = n{n -1\choose i-1}$

so

$\displaystyle i^2{n\choose i}^2 = n^2{n -1\choose i-1}^2$

and
$\displaystyle \sum_{i=1}^{n}i^2{n\choose i}^2=n^2\sum_{i=0}^{n-1}{n-1\choose i}^2=n^2{2n-2\choose n-1}$