How should I do this proof? should induction be used?

So far I have thought about using:

$\sum_{k=0}^n {n \choose k} = 2^n$ and $\sum_{k=0}^n k^2 = \frac{1}{6}n(n+1)(2n+1)$

but I cant break up that summation so I'm not sure how to proceed.

  • $\begingroup$ You should use the search engine before asking a question. $\endgroup$ – callculus Mar 13 '17 at 0:27
  • $\begingroup$ I usually only ask when I have tried searching for and failed in finding an answer, since I know that stackexchange it not at all tolerant about duplicate questions (case in point), not sure why I couldn't find that post though. $\endgroup$ – Nick Gong Mar 13 '17 at 0:32
  • $\begingroup$ Also think of selecting $k$ people from a population of $n$ and giving out two awards (possibly both to the same lucky person). The sum for all $k$ from $0$ to $n$ can be counted using both sides of the equation (with some algebraic manipulation on the right). $\endgroup$ – Alex B. Mar 13 '17 at 0:35
  • $\begingroup$ It´s not a big problem posting a duplicate,especially if you tried your best. You can see on the linked site that there are several links to questions with equal topic but partly different approaches. $\endgroup$ – callculus Mar 13 '17 at 0:37

The binomial theorem gives that $$ \sum_{k = 0}^n {n \choose k} x^k y^{n-k} = (x+y)^n.$$ Differentiating with respect to $x$ and multiplying by $x$ gives $$ \sum_{k=1}^n {n \choose k} k x^k y^{n-k} = nx(x+y)^{n-1}.$$ Differentiating with respect to $x$ and multiplying by $x$ again gives $$ \sum_{k = 1}^n {n \choose k} k^2 x^k y^{n-k} = nx(x+y)^{n-1} + n(n-1)x^2(x+y)^{n-2}.$$ Setting $x = y = 1$ gives $$ \sum_{k = 1}^n {n \choose k} k^2 = n 2^{n-1} + n(n-1)2^{n-2} =n(n+1)2^{n-2},$$ as you were trying to show.

  • 1
    $\begingroup$ Thanks! clear and precise answer, better than the suggested duplicate to be honest. $\endgroup$ – Nick Gong Mar 13 '17 at 0:33

Note that $\sum_{k=0}^n{n\choose k}x^k = (1+x)^n$ and $(xD)^2 x^k|_{x=1} = k^2 x^k|_{x=1}=k^2$, where $D = d/dx$.


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