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

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.

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

Marvis has given a typically excellent answer. I'll go ahead and show you an induction-style proof, just in case you're interested.

A useful basic combinatoric fact for this induction proof is Pascal's identity: $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}\tag{1}$$ Another nice basic fact is $$\sum_{k=0}^n\binom{n}k=2^n\tag{2}$$ for all $n\in\Bbb N$.

For each $n$, define $$f(n)=n(1+n)2^{n-2}\qquad \text{and}\qquad g(n)=\sum_{k=0}^nk^2\binom{n+1}{k},$$ so what we're trying to show is that $f(n)=g(n)$ for all $n$. In the $n=0$ case, this is clear, yes?

For the induction step, supposing that $f(n)=g(n)$ for some $n$, we must show that $f(n+1)=g(n+1)$.

Observe on the one hand that $$f(n+1)=(n+1)(2+n)2^{n-1}=(n+1)2^n+n(n+1)2^{n-1}=(n+1)2^n+2f(n),$$ so by inductive hypothesis, $$2g(n)=2f(n)=f(n+1)-(n+1)2^n.\tag{3}$$ On the other hand, we have $$\begin{align}g(n+1) &= \sum_{k=0}^{n+1}k^2\binom{n+1}k\\ &=\sum_{k=1}^{n+1}k^2\binom{n+1}{k}\\ &=(n+1)^2\binom{n+1}{n+1}+\sum_{k=1}^nk^2\binom{n+1}{k}\\ &\overset{(1)}{=}(n+1)^2+\sum_{k=1}^nk^2\left[\binom{n}{k}+\binom{n}{k-1}\right]\\ &=(n+1)^2+\sum_{k=1}^nk^2\binom{n}{k}+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+\sum_{k=0}^nk^2\binom{n}{k}+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+g(n)+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+g(n)+\sum_{k=0}^{n-1}(k+1)^2\binom{n}{k}\\ &=n^2+2n+1+g(n)+\sum_{k=0}^{n-1}k^2\binom{n}{k}+2\sum_{k=0}^{n-1}k\binom{n}{k}+\sum_{k=0}^{n-1}\binom{n}{k}\\ &=(n^2+2n+1)\binom{n}{n}+g(n)+\sum_{k=0}^{n-1}k^2\binom{n}{k}+2\sum_{k=0}^{n-1}k\binom{n}{k}+\sum_{k=0}^{n-1}\binom{n}{k}\\ &=g(n)+\sum_{k=0}^nk^2\binom{n}{k}+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &=2g(n)+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &\overset{(3)}{=}f(n+1)-(n+1)2^n+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &\overset{(2)}{=}f(n+1)-n2^n+2\sum_{k=0}^nk\binom{n}{k}\\ &=f(n+1)-2\left(n2^{n-1}-\sum_{k=0}^nk\binom{n}{k}\right)\end{align}$$ Hence, to see that $f(n+1)=g(n+1)$, it suffices that $$n2^{n-1}=\sum_{k=0}^nk\binom{n}{k}$$ Indeed, note that for $1\leq k\leq n$ we have $$k\binom{n}{k}=k\cdot\frac{n!}{k!(n-k)!}=n\cdot\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!}=n\binom{n-1}{k-1},\tag{4}$$ and so $$\begin{align}n2^{n-1} &\overset{(2)}{=} n\sum_{k=0}^{n-1}\binom{n-1}{k}\\ &= n\sum_{k=1}^n\binom{n-1}{k-1}\\ &= \sum_{k=0}^{n-1}n\binom{n-1}{k-1}\\ &\overset{(4)}{=} \sum_{k=1}^nk\binom{n}{k}\\ &= \sum_{k=0}^nk\binom{n}{k},\end{align}$$ as desired.