# 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.... – N. S. Nov 13 '11 at 22:40
@N.S. But it's messy for me... Are there any combinatorial proofs? – Kou Nov 13 '11 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 ... – N. S. Nov 13 '11 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. – Henning Makholm Nov 13 '11 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. – Martin Sleziak Jul 12 '12 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.

-

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.

-

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.)

-

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

-

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.

-