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} $$
 A: Although a year late, here is a proof using the properties
$$
k\binom{n}{k}=n\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)$
A: With induction we prove:


*

*$\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$

*$0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$

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


*

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

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

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

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


*

*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.

*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.
A: We know the nbinomial expansion $$f(x):=\sum_{i=0}^n {n\choose i}x^i = (1+x)^n.$$
Note that taking the derivative and multiplying by $x$ turns $x^i$ into $ix^i$, thus
$$xf'(x)=\sum_{i=0}^n {n\choose i}ix^i$$
 and repeating this step
$$x (f'(x)+xf''(x))=\sum_{i=0}^n {n\choose i}i^2x^i$$
We want this evaluated at at $x=1$.
With $f'(x) = n(1+x)^{n-1}$ and $f''(x)=n(n-1)(1+x)^{n-2}$, we obtain
$$ 1\cdot(n2^{n-1}+1\cdot n(n-1)2^{n-2})=n(n-1+2)2^{n-2}=n(n+1)2^{n-2}.$$
