# How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation.

I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any hints or suggestions?

• Write their formulas.... Nov 13, 2011 at 22:40
• @N.S. But it's messy for me... Are there any combinatorial proofs?
– Kou
Nov 13, 2011 at 22:43
• It is actually very easy, if you have the right formula, which is: $\binom{n-k+1}{k+1}=\binom{n-k}{k}+\binom{n-k}{k+1}$..The proof is two lines long.... The formula you posted is wrong, that's why you failed ... Nov 13, 2011 at 22:48
• For intuition, consider Pascal's triangle. Each binomial coefficient in the triangle is in exactly one of your $s_n$s, and every term that is in $s_n$ arises as the sum of a term from $s_{n-1}$ and a term from $s_{n-2}$, and this uses each term of $s_{n-1}$ and $s_{n-2}$ exactly once. Nov 13, 2011 at 23:08
• A combinatorial proof based on number of tiling of $n\times1$ board by squares and dominos is given in Benjamin, Quinn: Proofs that Really Count; Identity 4, p.4. Jul 12, 2012 at 11:47

Consider the words of length $n+1$ with letters 0,1 and no two consecutive 1s.

Prove that they are counted by the Fibonacci numbers.

Now count the same kind of words that contain exactly $k$ letters 1.

This approach was explained in the above comments by N.S and and Henning

We can show $$\sum_{k\ge0} \binom{n-k}k=F_{n+1}$$ by induction.

Note that I did not specify the range for $k$. I am using the usual convention that $\binom pq$ is considered zero whenever $q<0$ or $q>p$. EDIT: After reading Marc van Leeuwen's answer I've realized, that this is true for non-negative $q$ only, so I've change range to $k\ge0$.

$1^\circ$ We can verify $n=-1,0,1,2$ by hand.

$2^\circ$ Inductive step: Suppose $n>1$. We want to show that this is true for $n+1$ and assume validity of the formula for $0,1,\dots,n$.

$$\sum_{k\ge0} \binom{n+1-k}k=\sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-k}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-1-(k-1)}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{j\ge0} \binom{n-1-j}{j}= F_{n+1}+F_n = F_{n+2}.$$

This proof can be visualized as follows: We are computing the sums of terms in Pascal triangle along diagonals.

It suffices to notice that each element on $k$-th diagonal is a sum of an element from $(k-1)$-th diagonal and $(k-2)$-th diagonal.

(I've taken the picture from thesis of my student I supervised some time ago. I am not sure whether she made the picture herself or found it somewhere on the Internet.)

We begin with the identity: $$\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}.$$ We apply the identity to $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ to get $$s_n= \underbrace{\color{blue}{\binom{n}{0}} + \color{grey}{\binom{n}{-1}}}_{\text{first term}} + \underbrace{\color{blue}{\binom{n-1}{1}} + \color{brown}{\binom{n-1}{0}}}_{2\text{nd term}} + \underbrace{\color{blue}{\binom{n-2}{2}} + \color{brown}{\binom{n-2}{1}} }_{3\text{rd term}} + \cdots$$

Notice that the terms in are $\color{blue}{s_{n-1}}$ and those in brown/red $\color{brown}{s_{n-2}}$. (I had to work out what $s_{n-1}$ and $s_{n-2}$ was in order to catch the pattern, in case you're wondering how I knew). And so we have our fibonacci relation $$s_n = \color{blue}{s_{n-1}} + \color{brown}{s_{n-2}}$$

As for the $\binom{n}{-1}$ term, just define it to be $0$...If that's not allowed, then wave your hands and mumble something.

The problem with proving $\binom{n-k+1}k=\binom{n-k}k+\binom{n-k-1}k$ is that it is not true (try $k=0$ for starters). However for $n\geq1$ one has \begin{aligned} s_{n-1}&=\sum_{k=0}^{\lfloor\frac n2\rfloor}\binom{n-k}k\\ &= 1+\sum_{k=1}^{\lfloor\frac n2\rfloor}(\binom{n-1-k}k+\binom{n-1-k}{k-1})\\ &= 1+\sum_{k=1}^{\lfloor\frac {n-1}2\rfloor}\binom{n-1-k}k +\sum_{k=1}^{\lfloor\frac n2\rfloor}\binom{n-1-k}{k-1}\\ &= s_{n-2}+\sum_{k=0}^{\lfloor\frac n2\rfloor-1}\binom{n-2-k}k\\ &= s_{n-2}+s_{n-3},\\ \end{aligned} so that the sequence $(s_n)_{n\geq-1}$ satisfies the Fibonacci recurrence (with $s_{-1}=\binom00=1$ by the same definition as $s_n$ for $n\in\mathbf N$). Since moreover $s_{-1}=s_0=1$ one has $s_n=F_{n+2}$ for all $n\geq-1$.

One wonders what is the point of starting the defining expression for $s_n$ with $\binom{n+1}0$, as the "$+1$" only increases the shift with respect to the Fibonacci sequence. To resume, one has $$F_n=\sum_{k=0}^{\lfloor\frac{n-1}2\rfloor}\binom{n-1-k}k \qquad\text{for }n\geq1.$$

Added: although the summation runs into terms $0$ once $k>n/2$ (this is implicitly used in the argument above where we dropped the final term from the first summation in the third line), it should not be written as an unbounded (therefore infinite) summation: when one gets to terms for $k>n$, the terms are again nonzero, by the usual convention for binomial coefficients with negative upper index. This point should have been made clearer in the question.

$\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{\dsc}[1]{\displaystyle{\color{red}{#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{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert} \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{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align}\color{#66f}{\large s_{n}}& ={n+1 \choose 0} + {n \choose 1} + {n - 1 \choose 2} + \cdots =\sum_{k\ =\ 0}^{\infty}{n + 1 - k \choose k} \\[5mm]&=\sum_{k\ =\ 0}^{\infty}\ \overbrace{\oint_{\verts{z}\ =\ \varphi^{+}} {\pars{1 + z}^{n + 1 - k} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ \dsc{n + 1 - k \choose k}}} \end{align}

where $\ds{\varphi \equiv {1 + \root{5} \over 2}}$ is the Golden Ratio. Then,

\begin{align} \color{#66f}{\large s_{n}}& =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 1} \over z} \sum_{k\ =\ 0}^{\infty}\bracks{1 \over z\pars{1 + z}}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 1} \over z} {1 \over 1 - 1/\bracks{z\pars{1 + z}}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ \varphi^{+}}{\pars{1 + z}^{n + 2} \over z^{2} + z - 1} \,{\dd z \over 2\pi\ic} \\[5mm]&=\oint_{\verts{z}\ =\ \varphi^{+}} {\pars{1 + z}^{n + 2} \over \pars{z + \varphi}\pars{z - \varphi^{-1}}} \,{\dd z \over 2\pi\ic} ={\pars{1 - \varphi}^{n + 2} \over -\varphi - \varphi^{-1}} +{\pars{1 + \varphi^{-1}}^{n + 2} \over \varphi^{-1} + \varphi} \end{align}

However, $\ds{\quad\varphi + \varphi^{-1}=\root{5}\,,\quad 1 + \varphi^{-1}=\varphi\quad}$ such that

$$\color{#66f}{\large s_{n}} ={\varphi^{n + 2} - \pars{1 - \varphi}^{n + 2} \over \root{5}} =\color{#66f}{\large F_{n + 2}}$$

where $\ds{F_{m}}$ is a Fibonacci Number.

I'm going to add in an answer which is hinted at in some other answers, and cousins of which are spelled out in different MSE threads, but which I think could use a clear, systematic exposition. This is based on Arthur Benjamin's explanation in The Magic of Math.

1. The natural numbers $$1, 2, 3, ...$$, or $$n \in \mathbb{N}$$, can each be formed by adding up a sequence of $$1$$s and $$2$$s. Some examples are shown below. I follow Benjamin and use $$f_n$$ to indicate the number of unique ways to form $$n$$ using those sequences. This does not necessarily stand for "Fibonacci", which we'll denote $$F_n$$. Their correspondence will be proven.
$$\begin{array}{|c|c|c|} \hline n & \text{sequences} & f_n \cr \hline 1 & 1 & 1 \cr \hline 2 & 11, 2 & 2 \cr \hline 3 & 111, 12, 21 & 3 \cr \hline 4 & 1111, 112, 121, 211, 22 & 5 \cr \hline 5 & 11111, 1112, 1121, 1211, 2111, 221, 212, 122 & 8 \cr \hline \end{array}$$

2. If a given sequence begins with a $$1$$, the remaining items in the sequence must sum to $$n-1$$, and there are $$f_{n-1}$$ ways to do that. If a given sequence begins with a $$2$$, the remaining items must sum to $$n-2$$, and there are $$f_{n-2}$$ ways to do that. So, $$f_n = f_{n-1} + f_{n-2}$$, which is obviously a "Fibonacci-type" recursive relation. To work out the exact connection, we can add the Fibonacci numbers into the table.
$$\begin{array}{|c|c|c|c|} \hline n & \text{sequences} & f_n & F_n \cr \hline 1 & 1 & 1 & 1 \cr \hline 2 & 11, 2 & 2 & 1\cr \hline 3 & 111, 12, 21 & 3 & 2\cr \hline 4 & 1111, 112, 121, 211, 22 & 5 & 3\cr \hline 5 & 11111, 1112, 1121, 1211, 2111, 221, 212, 122 & 8 & 5\cr \hline \end{array}$$

Now, we can see that $$F_n = f_{n-1}$$.

3. Any sequence can also be understood as an exercise in asking "where do the $$2$$s go, if any?" For example, for $$n = 5$$, we can have $$0, 1,$$ or $$2$$ twos; the answer to "where do(es) the two(s) go?" is a binomial one, of course: asking about the number of ways to order $$m$$ objects of type $$k_1$$ and $$k_2$$, where we don't distinguish objects of the same type, is a classic way to re-describe the binomial coefficient as a multinomial coefficient, if not the standard introductory way. Since we already demonstrated that the number of ways to sum $$1$$s and $$2$$s to get the natural numbers $$n$$ is a Fibonacci sequence shifted, we now have the basic connection in hand.

4. Now, we work on the details. How many binomial coefficients do we need to sum up? Let's start with the simplest scenario, which tells us where to begin the sum and also what our index variable should be: if we have no $$2$$s, we simply have $$\binom{n}{0}$$. Then, if we add in a $$2$$, we would be incrementing the sum by by $$1$$, so we have get rid of a $$1$$; we have $$\binom{n-1}{1}$$ places to put the single two.

5. Finally, where should we end our sum? Well, if we have an even number, we simply stop at $$\frac{n}{2}$$, because$$\frac{n}{2}2 = n$$. Then, the expression follows readily for even numbers: \begin{aligned} \sum_{j=0}^{\frac{n}{2}} \binom{n-j}{j} \forall n : n \mod 2 = 0 \end{aligned} Now, finally, we just need to work out what to do in the case of odd numbers. Here, we can just use hand-inspection. If $$n=5$$, we can have, at most, a pair of $$5$$s, so we want the integer part of $$\frac{5}{2}$$. This is denoted, at least in computer science, the floor of $$\frac{n}{2}$$ and written $$\lfloor{\frac{5}{2}}\rfloor$$ (note the little "feet" on the "bars"). \begin{aligned} \sum_{j=0}^{\lfloor{k}\rfloor} \binom{n-j}{j} \end{aligned} Finally, if we pick a given $$n$$ on the "binomial triangle" and then simply run our finger along the triangle, we'll see that this is always a diagonal of the triangle.