4
$\begingroup$

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?

3 Answers 3

4

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?

  • 0
    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 ?2012-09-16
  • 0
    The assumption looks slightly doubious, but I suppose this is just missing sum signs. Apart from that, you have the right idea.2012-09-16
  • 0
    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 22012-09-16
  • 0
    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.2012-09-17
  • 0
    @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 ?2012-09-17
  • 0
    I don't understand what reduction you are talking about - the sums as they stand make no sense.2012-09-17
1

Why not just using the basic binomial coeficient identity twice? $$ \binom{n + 1}{k + 1} = \binom{n}{k + 1} + \binom{n}{k} $$

1

$\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}