Question regarding proof for $\sum_{k=0}^n\binom{n-k}{k} = F_{n+1}$

Question

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.

Answer 1

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

Answer 2

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