# Using Binomial Theorem to prove identity

I need to prove the following using the binomial theorem

$${n \choose k} = {n-2 \choose k} + 2{n-2 \choose k-1} + {n-2 \choose k-2}$$

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

I'm trying to use $(1+x)^n = (1+x)^2(1+x)^{n-2}$ but i dont know how to go from there?

-

You're quite close already - note that by the Binomial Theorem, $$(1+x)^{n-2} = \sum_{k=0}^{n-2} {n-2 \choose k} x^k.$$
Expanding $(1+x)^2 = 1 + 2x + x^2$, we get
$$(1+x)^n = (1+x)^2(1+x)^{n-2} = \sum_{k=0}^{n-2} {n-2 \choose k} \left(x^k +2 x^{k+1} +x^{k+2}\right).$$
Now, the trick is to collect the different powers of $x$, that iş tranforming the formula in a way that only $x^k$ appears on the right-hand side. Can you do this?
Hmmm I think i got it expanding \sum_{k=0}^{n-2} {n-2 \choose k} \left(x^k +2 x^{k+1} +x^{k+2}\right).$$should give the right side of my identity right ? If my assumption of 2*sum(n-2,k)x^(k+1) = 2*sum(n-2,k-1)x^k ? – Thatdude1 Sep 16 '12 at 19:47 The assumption looks slightly doubious, but I suppose this is just missing sum signs. Apart from that, you have the right idea. – Johannes Kloos Sep 16 '12 at 20:03 Do you know how to prove this with a combinatorial proof too. Apparently i have to consider the set of all k-subsets of {1,2...n} and classify them according to whether or not they contain the element 1 and/or the element 2 – Thatdude1 Sep 16 '12 at 21:44 Take a set of n elements, and count the number of k-subsets. There are four possibilities: The k-subsets not containing neither 1 nor 2 (there are n-2 \choose k, why?), those containing 1 but not 2, those containing 2 but not 1 and those containing both. When you know how many subsets there are of each typę the final result is almost obvious; you just need a (very simple) argument why you can just add the numbers. – Johannes Kloos Sep 17 '12 at 7:13 @JohannesKloos Can you explain how you can go from the expansion, to being able to reduce 2*sum(n-2,k)x^(k+1) = 2*sum(n-2,k-1)x^k ? – Overload119 Sep 17 '12 at 23:12 Why not just using the basic binomial coeficient identity twice?$$ \binom{n + 1}{k + 1} = \binom{n}{k + 1} + \binom{n}{k}