Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

6 Answers 6

up vote 20 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
(+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.

share|improve this answer
    
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} $$
share|improve this answer

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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.