# Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

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?

• Shouldn't ${n\choose p}+{n\choose p+1}={n+n\choose p+p+1}={2n\choose 2p+1}$? – Jodo1992 May 6 '16 at 6:28
• @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 – Olivier Oloa May 6 '16 at 6:29
• @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}}$ – 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}