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

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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?

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

share|improve this answer

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{{n \choose k} = {n - 2 \choose k} + 2{n - 2 \choose k - 1} +{n - 2 \choose k - 2}:\ {\large ?}}$.

\begin{align}&\color{#66f}{\large% {n - 2 \choose k} + 2{n - 2 \choose k - 1} + {n - 2 \choose k - 2}} \\[3mm]&=\oint_{\verts{z}\ =\ 1}\bracks{% {\pars{1 + z}^{n - 2} \over z^{k + 1}} +2\,{\pars{1 + z}^{n - 2} \over z^{k}} +{\pars{1 + z}^{n - 2} \over z^{k - 1}}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n - 2} \over z^{k + 1}} \pars{1 + 2z + z^{2}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{k + 1}} \,{\dd z \over 2\pi\ic} = \color{#66f}{\large{n \choose k}} \end{align}

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.