Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS further:$$\left({n\choose k}+{n\choose k+1}\right)+\left({n\choose k+1}+{n\choose k+2}\right)$$From here, however, an answer key that I'm using immediately jumps to:$$={n+1\choose k+1}+{n+1\choose k+2}$$Which then jumps to:$$={n+2\choose k+2}$$But I don't know how either of those last two steps were reached after I break down the LHS. Could someone clarify these steps for me?


These steps come from

$$ {n\choose p}+{n\choose p+1}={n+1\choose p+1}. \tag1 $$

Then, just apply $(1)$ the first time with $n:=n, \,p:=k$ and the second time with $n:=n, \,p:=k+1$ and the third time with $n:=n+1, \,p:=k+1$.

Can you take it from here?

  • $\begingroup$ Shouldn't ${n\choose p}+{n\choose p+1}={n+n\choose p+p+1}={2n\choose 2p+1}$? $\endgroup$ – Jodo1992 May 6 '16 at 6:28
  • 1
    $\begingroup$ @Jodo1992 No. You rather just have ${n\choose p}+{n\choose p+1}={n+1\choose p+1}$. see Pascal's triangle: en.wikipedia.org/wiki/Binomial_coefficient#Pascal%27s_triangle $\endgroup$ – Olivier Oloa May 6 '16 at 6:29
  • $\begingroup$ @Jodo1992 To remember this formula: you know that ${n+1}\choose {k+1}$ is the number of ways you can choose $k+1$ objects among $n+1$. Select a particular object among the $n+1$ objects. Then, either the selection contains this object, either it doesn't. If it does, you are left to choose $k$ objects among $n$, if it doesn't, you are left to choose $k+1$ objects among $n$. Hence, ${n+1}\choose{k+1}$ $={n\choose k}+ {n\choose{k+1}}$ $\endgroup$ – H. Potter May 6 '16 at 8:55

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{\quad a_{k} = a_{k + 2} = 1\,,\quad a_{k + 1} = 2}$:

\begin{align} \color{#f00}{\sum_{j = k}^{k + 2}a_{j}{n \choose j}} & = \sum_{j = k}^{k + 2}a_{j}\oint_{\verts{z} = 1} {\pars{1 + z}^{n} \over z^{\ j + 1}}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1} {\pars{1 + z}^{n} \over z}\,\,\sum_{j = k}^{k + 2}{a_{j} \over z^{\ j}} \,{\dd z \over 2\pi\ic} \\[4mm] & = \oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \pars{{1 \over z^{k}} + {2 \over z^{k + 1}} + {1 \over z^{k + 2}}} \,{\dd z \over 2\pi\ic} \\[4mm] & = \oint_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{k + 3}} \pars{z^{2} + 2z + 1}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1}{\pars{1 + z}^{n + 2} \over z^{k + 3}} \,{\dd z \over 2\pi\ic} = \color{#f00}{n + 2 \choose k + 2} \end{align}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.