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

-

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}\\ &=(n+1)^2+\sum_{k=1}^nk^2\left[\binom{n}{k}+\binom{n}{k-1}\right]\qquad\bigl(\text{by } (1)\bigr)\\ &=(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}\\ &=f(n+1)-(n+1)2^n+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\qquad\bigl(\text{by } (3)\bigr)\\ &=f(n+1)-n2^n+2\sum_{k=0}^nk\binom{n}{k}\qquad\bigl(\text{by } (2)\bigr)\\ &=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} &= n\sum_{k=0}^{n-1}\binom{n-1}{k}\qquad\bigl(\text{by } (2)\bigr)\\ &= n\sum_{k=1}^n\binom{n-1}{k-1}\\ &= \sum_{k=0}^{n-1}n\binom{n-1}{k-1}\\ &= \sum_{k=1}^nk\binom{n}{k}\qquad\bigl(\text{by } (4)\bigr)\\ &= \sum_{k=0}^nk\binom{n}{k},\end{align} as desired.

-

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

-
(+1): Very nice! It's things like this that make me want to practice proofs by double-counting. –  Cameron Buie Nov 6 '12 at 21:19
very nice solution......sdcvvc.... –  juantheron Dec 9 '13 at 6:14

Here’s a purely combinatorial argument that avoids almost all computation.

A certain school elects zero or more members of its graduating class to the honor society. It also awards a prize in mathematics and a prize in English; these always go to members of the honor society, but they may go to the same person. If there are $n$ students in the graduating class, in how many different ways can the awards and membership in the honor society be bestowed?

• Suppose that $k$ students are admitted to the honor society: they can be chosen in $\binom{n}k$ ways, and the two awards can then be made in $k^2$ ways. Since $k$ may range from $0$ through $n$, there are $\sum_{k=0}^nk^2\binom{n}k$ ways to bestow the awards and membership.

• Alternatively, we may decide first who gets the awards.

1. If they go to the same person, there are $n$ ways to choose that person. The recipient of the awards must be chosen for the honor society, and any of the other $n-1$ students may be chosen, so there are $n2^{n-1}$ possible combinations of this kind.

2. If they go to different people, they may be bestowed in $n(n-1)$ different ways, and we must then choose any subset of the remaining $2^{n-2}$ students to fill out the honor society; there are $n(n-1)2^{n-2}$ ways to do this.

This comes to a total of $$n2^{n-1}+n(n-1)2^{n-2}=(2+n-1)n2^{n-2}=n(n+1)2^{n-2}$$ ways of bestowing the awards and memberships.

It follows that $$\sum_{k=0}^nk^2\binom{n}k=n(n+1)2^{n-2}\;,$$ since the two sides represent different ways of counting the same thing.

-
Oops; I see that @sdcvvc beat me to it while I was typing. –  Brian M. Scott Nov 6 '12 at 20:47
Nice solution.........Brian M. Scott.. –  juantheron Dec 9 '13 at 6:15

With induction we prove:

1. $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$
2. $0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$
3. $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}$

For the proofs we use Pascal's identity: $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$.

1. If $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$ then $$\binom{n+1}{0}+\binom{n+1}{1}+\binom{n+1}{2}+\cdots+\binom{n+1}{n}+\binom{n+1}{n+1}=\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{0}+\binom{n}{2}+\binom{n}{1}+\cdots+\binom{n}{n}+\binom{n}{n-1}+\binom{n}{n}=\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}+\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n+2^n=2^{n+1}.$$
2. If $0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$ then $$0\binom{n+1}{0}+1\binom{n+1}{1}+2\binom{n+1}{2}+\cdots+n\binom{n+1}{n}+(n+1)\binom{n+1}{n+1}=\\ \ldots = \\ 2\left(0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}\right)+\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2n2^{n-1}+2^n=(n+1)2^n.$$
3. If $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}$ then $$0^2\binom{n+1}{0}+1^2\binom{n+1}{1}+2^2\binom{n+1}{2}+\cdots+n^2\binom{n+1}{n}+(n+1)^2\binom{n+1}{n+1}=\\ \ldots =\\ 2\left( 0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}\right)+\\ 2\left(0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}\right)+\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=\\ 2n(1+n)2^{n-2}+2n2^{n-1}+2^n=(n+1)(2+n)2^{n-1}$$
-

Although a year late, here is a proof using the properties $$\binom{n}{k}=\frac nk\binom{n-1}{k-1}\tag{1}$$ and $$\sum_{k=0}^n\binom{n}{k}=2^n\tag{2}$$ Thus, \begin{align} \sum_{k=0}^nk^2\binom{n}{k} &=\sum_{k=0}^nnk\binom{n-1}{k-1}\tag{3}\\ &=\sum_{k=0}^nn\binom{n-1}{k-1}+\sum_{k=0}^nn(k-1)\binom{n-1}{k-1}\tag{4}\\ &=\sum_{k=0}^nn\binom{n-1}{k-1}+\sum_{k=0}^nn(n-1)\binom{n-2}{k-2}\tag{5}\\ &=n2^{n-1}+n(n-1)2^{n-2}\tag{6}\\[9pt] &=n(n+1)2^{n-2}\tag{7} \end{align} Explanation:
$(3)$: apply $(1)$
$(4)$: $k=1+(k-1)$
$(5)$: apply $(1)$
$(6)$: apply $(2)$ to both sums
$(7)$: $2n+n(n-1)=n(n+1)$

-