# Summation proof (with binomial coefficents)

I am trying to prove that $\sum_{k=2}^n$ $k(k-1) {n \choose k}$=$n(n-1)2^{n-2}$.

I was initially trying to use induction, but I think a more simple proof can be done using the fact that $\sum_{k=0}^n {n \choose k}$=$2^n$.

This is how I begin to proceed:

$\sum_{k=2}^n$ $k(k-1) {n \choose k}$= $\sum_{k=0}^{n-2}$ $(k+2)(k+1) {n \choose k+2}$= $2^{n-2} *\sum_{k=0}^{n-2}$ $(k+2)(k+1)$.

First of all, is this correct so far? And second, how would I proceed from here.

-
No, your second equality is completely wrong. – Robert Israel Feb 9 '14 at 20:04

By the binomial theorem

$$\sum_{k=0}^n {n\choose k} x^k=(1+x)^n$$

Take two derivatives in $x$ and plug in $x=1$.

-
But this summation will be from k=0 and not from k=2. – math1234567 Feb 9 '14 at 20:29
$k(k-1)=0$ for $k=0,1$ so can write your summation just as well from $k=0$. – Your Ad Here Feb 9 '14 at 20:32

Here is a combinatorial argument. We have a group of $n$ people, and want to award one of them a gold medal, another a silver medal, and to award plastic medals to some subset of the rest (the subset may be empty).

We count the number of ways to do this in two different ways:

1) There are $n$ ways to decide who gets the gold, and for each such way there are $n-1$ ways to decide who gets the silver. There remain $n-2$ people. We can choose a subset of these to get plastic in $2^{n-2}$ ways, for a total count of $$(n)(n-1)2^{n-2}.$$

2) For any $k\ge 2$, we can choose the $k$ people who will get some sort of medal in $\binom{n}{k}$ ways. From these, we can choose the gold and silver medal winners in $(k)(k-1)$ ways. The rest get plastic. That gives a total count of $$\sum_{k=2}^n \binom{n}{k}(k)(k-1).$$

-
(+1) Is there a trick to come up with such stories? – Your Ad Here Feb 9 '14 at 21:17
Hard to know, in this case I was operating essentially from memory. Once one has seen/invented a few "two ways of counting" proofs, mild variants come easily. – André Nicolas Feb 9 '14 at 21:50

$$k(k-1)\cdot{n \choose k}=n(n-1)\cdot{n-2 \choose k-2}$$

-

Let $a(z), b(z), c(z)$ be Exponential Generating Functions with $a(z) = \sum_{n}[(a_nz^n)/n!]$ etc.

Binomial convolution states that if $a(z) = b(z)c(z)$ then $a_n = \sum_{k=0}^n {n \choose{k}}b_kc_{n-k}$

By using the usual product of formal power series, the proof becomes quite simple

-