2
$\begingroup$

I am currently working through the various properties of the binomial coefficient and was up to the identity

$\sum_{k=0}^n\binom{n-k}{k} = F_{n+1}$

The proof is provided elsewhere on this website, here specifically. I have reproduced the user Adi Dani's proof below.

$$\begin{align} F_{n+1}&=\sum_{k=0}^n\binom{n-k}{k}\\ &=\sum_{k=0}^{n}\Bigg(\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\Bigg)\\ &=\sum_{k=0}^{n-1}\Bigg(\binom{(n-1)-k}{k}+\binom{n-2-(k-1)}{(k-1)}\Bigg)\\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{k=0}^{n-1}\binom{n-2-(k-1)}{k-1}\\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{j=0}^{n-2}\binom{(n-2)-j}{j}\\ &=F_{n}+F_{n-1} \end{align}$$

It's all clear to me except for the changing of the index on the summation. How are you able to reduce a summation by one or two members in the series without consequence?

As an addendum to this question, I've noted that the only proofs I've had trouble with so far have involved changing the index on a summation. As such, if anyone had some good resources for looking at summations in more detail (especially if there are exercises) then that would be massively appreciated.

$\endgroup$
  • $\begingroup$ I thinks that $\sum_{k=0}^n\binom{n-k}{k} = F_{n\color{red}{+1}}$ if we speak about Fibonacci numbers $\endgroup$ – Claude Leibovici Jul 22 '17 at 7:48
  • $\begingroup$ Just changed it, thanks. $\endgroup$ – washboardalex Jul 22 '17 at 8:45
1
$\begingroup$

I believe that proof uses the convention, that $\binom{n}{k} = 0$ for all $k > n$ and for all $k < 0$. This of course means that most of the terms in the sum are equal to zero.

I've annotated the proof for a bit for you.

\begin{align} F_{n+1}&=\sum_{k=0}^n\binom{n-k}{k} \text{ (induction hypothesis) } \\ &=\sum_{k=0}^{n}\Bigg(\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\Bigg) \text{ (recursive formula for binom. coefficients) }\\ &=\sum_{k=0}^{n}\Bigg(\binom{(n-1)-k}{k}+\binom{n-2-(k-1)}{(k-1)}\Bigg)\text{ $(n-2-(k-1)= n-k-1)$} \\ &=\sum_{k=0}^{n-1}\Bigg(\binom{(n-1)-k}{k}+\binom{n-2-(k-1)}{(k-1)}\Bigg)\text{ (the $k=n$ Term is equal to zero)} \\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{k=0}^{n-1}\binom{n-2-(k-1)}{k-1} \text{ (splitting the sum into two sums) } \\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{j=-1}^{n-2}\binom{(n-2)-j}{j} \text{ (substitute $j = k-1$) } \\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{j=0}^{n-2}\binom{(n-2)-j}{j} \text{ (the $j = -1$ Term is equal to zero) } \\ &=F_{n}+F_{n-1} \end{align}

See wikipedia for the recursive formula. The article also mentions the convention I described earlier. In fact it also lists the formula for the Fibonacci numbers as $$F(n+1) = \sum_{k=0}^{\lfloor{n/2}\rfloor} \binom{n-k}{k}.$$

$\endgroup$
  • $\begingroup$ @washboardalex you are welcome! You can accept this answer by clicking the green check mark next to my answer. This shows peole looking for something similar that this question is answered. $\endgroup$ – cdwe Jul 23 '17 at 6:39
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#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{\verts{z} < {1 \over \varphi}}$ where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ is the Golden Ratio:

\begin{align} \sum_{k = 0}^{n}{n - k \choose k} & = \sum_{k = 0}^{n}\bracks{z^{k}}\pars{1 + z}^{n - k} = \sum_{k = 0}^{n}\bracks{z^{0}}{1 \over z^{k}}\,\pars{1 + z}^{n - k} \\[5mm] & = \bracks{z^{0}}\pars{1 + z}^{n} \sum_{k = 0}^{n}\bracks{1 \over z\,\pars{1 + z}}^{k} = \bracks{z^{0}}\pars{1 + z}^{n}\, {\braces{1/\bracks{z\pars{1 + z}}}^{n + 1} - 1 \over 1/\bracks{z\pars{1 + z}} - 1} \\[5mm] & = \bracks{z^{0}}\pars{1 + z}^{n}\braces{% {1 \over \bracks{z\pars{1 + z}}^{\,n}}\,{1 - \bracks{z\pars{1 + z}}^{\,n + 1} \over 1 - z\pars{1 + z}}} \\[5mm] & = \bracks{z^{n}}{1 - z^{n + 1}\pars{1 + z}^{n + 1} \over 1 - z - z^{2}} = \bracks{z^{n}}{1 \over 1 - z - z^{2}} = \bracks{z^{n}}\pars{{1 \over z}{z \over 1 - z - z^{2}}} \\[5mm] & = \bracks{z^{n + 1}}{z \over 1 - z - z^{2}} = \bracks{z^{n + 1}}\sum_{k = 0}^{\infty}F_{k}z^{k} = \bbx{F_{n + 1}} \end{align}

Note that $\ds{{z \over 1 - z - z^{2}}}$ is the Fibonacci Number Generating Function.

$\endgroup$

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.