Induction: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

I found crazy (for me at least) induction example, in fact it just would be nice to prove. (Even have problems with starting) Any hints are highly valued: $$0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}=n(1+n)2^{n-2} $$

Solution 1:

You need to prove that $$\sum_{k=0}^{n} k^2 \dbinom{n}k = n(n+1) 2^{n-2}$$ Below is a way to prove, without using induction explicitly.

Consider the binomial expansion $$(1+x)^n = \sum_{k=0}^{n} \dbinom{n}kx^k$$ Differentiate once gives us $$n(1+x)^{n-1} = \sum_{k=0}^{n} k\dbinom{n}kx^{k-1}$$ $$nx(1+x)^{n-1} = \sum_{k=0}^{n} k\dbinom{n}kx^{k}$$ Differentiate again to give $$n(n-1)x(1+x)^{n-2} + n(1+x)^{n-1} = \sum_{k=0}^{n} k^2\dbinom{n}kx^{k-1}$$ Now plug in $x=1$ to get what you want.

Solution 2:

Count cardinality of $S=\left\{(A,x,y): A \subseteq \{1,2,\dots,n\} \wedge x,y \in A\right\}$ in two different ways:

Way 1. If $A$ has $k$ elements, then you have $k^2$ choices for $x,y$ and $n \choose k$ for $A$. So $|S|=\sum_{k} k^2 {n \choose k}$.

Way 2. Two cases:

• If $x=y$, then we have $n$ choices for $x$ and $2^{n-1}$ choices for $A$.

• If $x \neq y$, then we have $n(n-1)$ choices for $x,y$ and $2^{n-2}$ choices for $A$.

Therefore $|S|=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$.