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

share|improve this question
2  
No, your second equality is completely wrong. –  Robert Israel Feb 9 at 20:04

4 Answers 4

up vote 5 down vote accepted

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

share|improve this answer
    
But this summation will be from k=0 and not from k=2. –  math1234567 Feb 9 at 20:29
1  
$k(k-1)=0$ for $k=0,1$ so can write your summation just as well from $k=0$. –  Your Ad Here Feb 9 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).$$

share|improve this answer
    
(+1) Is there a trick to come up with such stories? –  Your Ad Here Feb 9 at 21:17
1  
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 at 21:50

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

share|improve this answer

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

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.