$0^2{{n}\choose{0}} + 1^2{{n}\choose{1}} + 2^2 {{n}\choose{2}} + ... +n^2{{n}\choose{n}} = n (1+n)* 2^{n-2}, n \in \mathbb{N} \setminus \{0\}$ proof.

Question

I need to pove that:

$$0^2{{n}\choose{0}} + 1^2{{n}\choose{1}} + 2^2 {{n}\choose{2}} + ... +n^2{{n}\choose{n}} = n (1+n)* 2^{n-2}, n \in \mathbb{N} \setminus \{0\}$$

I think that the left hand side looks like binominal theorem. The problem is that in that case the sequence: $$0^2+1^2+2^2+...n^2$$ would be therefore equal to the multiplication of growing powers on one element and decreasing powers of other element. That is impossible since powers are constant and equal.

And I can't do my induction proof without any transformation of that expression since adding $1$ to $n$ would make that structure in its current form irregular - I wouldn't be able to extract the seqence that is my thesis.

Therefore I don't know how to transform that expression so that it can be proven by induction (as I assume).

Answer 1

Let

$$f(x)=\sum_{k=0}^nx^k{n\choose k}=(1+x)^{n}$$

Differentiating we get that

$$f'(x)=\sum_{k=0}^nkx^{k-1}{n\choose k}=n(1+x)^{n-1}$$

and so

$$xf'(x)=\sum_{k=0}^nkx^{k}{n\choose k}=nx(1+x)^{n-1}$$

differentiating again, we get that

$$(xf'(x))'=\sum_{k=0}^nk^2x^{k-1}{n\choose k}=n(1+x)^{n-1}+n(n-1)x(1+x)^{n-2}$$

plugging in $x=1$ we get that

\begin{align*} \sum_{k=0}^nk^2{n\choose k}&=2^{n-1}n+n(n-1)2^{n-2}\\ &=n2^{n-2}(2+n-1)\\ &=n(1+n)2^{n-2} \end{align*}

and we are done

Answer 2

Let $n \in \mathbb{N}^*$, and $S_n = \displaystyle \sum_{k=0}^{n} k^2 \binom{n}{k} = \sum_{k=0}^{n} k(k-1) \binom{n}{k} +\sum_{k=0}^{n} k \binom{n}{k} $

You can rapidly check that $\displaystyle k \binom{n}{k} = n \binom{n-1}{k-1}$ and $ \displaystyle k (k-1) \binom{n}{k} = n(n-1) \binom{n-2}{k-2} $.

So $\displaystyle \sum_{k=0}^n k \binom{n}{k} = n \sum_{k=1}^n\binom{n-1}{k-1} = n \sum_{k=0}^{n-1} \binom{n-1}{k} = n (1+1)^{n-1} = n 2^{n-1} $

Also $ \displaystyle \sum_{k=0}^n k(k-1) \binom{n}{k} = n(n-1) \sum_{k=2}^n\binom{n-2}{k-2} = n(n-1) \sum_{k=0}^{n-2} \binom{n-2}{k} = n(n-1) 2^{n-2}$.

Thus $S_n = n2^{n-1} + n(n-1)2^{n-2} = 2n 2^{n-2}+n(n-1)2^{n-2} = n(n+1)2^{n-2} $