Prove for the Fibonacci sequence: $F(m+n) = F(m-1) \cdot F(n) + F(m) \cdot F(n+1)$

Question

The following formula shall be proved by induction: $$F(m+n) = F(m-1) \cdot F(n) + F(m) \cdot F(n+1)$$ Where $F(i), i \in \mathbb{N}_0$ is the Fibonacci sequence defined as: $F(0) = 0$, $F(1) = 1$ amd $$F(n+1) = F(n) + F(n-1) \text{ for } n \geq 1.$$

How would you go about this task, especially considering that you have two variables which may be changed? Do you have to look at three cases ($m$ increases, $n$ increases, both $m$ and $n$ increase) in order to fully prove it or is there an easier way?

Answer 1

Here is a proof in the same spirit as RobertZ's.

First, let's relate the Fibonacci numbers to the following problem:

Suppose that you want to go up some flight of stairs and at every step you can take either one or two stairs: in how many ways can you get up the stairs?

Well, if we say that there are $n$ stairs, then it turns out there are $F_{n+1}$ ways to do it.

A very easy inductive proof shows why:

Base cases: If there is $1$ stairs, you can do it in only $1$ way, and indeed $F_{1+1}=F_2=1$. If there are $2$ stairs, then there are two ways: either take two steps of $1$, or take one step of $2$. And indeed, $F_{2+1}=F_3=2$

Inductive step: Say you have $n >2$ stairs. For your first step you can either go one up or two stairs up. By inductive hypothesis, there are $F_{n}$ ways to finish climbing the $n-1$ stairs after having taken a step of $1$ stairs, and there are $F_{n-1}$ ways to finish climbing the $n-2$ stairs after having taken a step of $2$ stairs. So, there are $F_{n}+F_{n-1}=F_{n+1}$ ways to climb $n$ stairs.

OK, so now that we have made a connection between the Fibonacci numbers and the number of ways to climb stairs in this way, we can prove your desired result very quickly:

Let's climb $m+n-1$ stairs. We now know we can do this in $F_{m+n}$ ways. But note that there are two different possibilities for us climbing those $m+n-1$ stairs:

1. The first way is that as we climb the stairs, we will at some point have climbed exactly $n$ stairs. If this happens, then there are $m-1$ stairs left to climb, which can be done in $F_m$ ways. And since then there are $F_{n+1}$ ways to climb the first $n$ stairs, that means that there are $F_m \cdot F_{n+1}$ ways to climb all the $m+n-1$ stairs this way.

2. The second way is that at some point we will have climbed exactly $n-1$ stairs, which can be done in $F_{n}$ ways, after which we take a single step of $2$ stairs, and then finish climbing the remaining $m-2$ stairs. This can therefore be done in $F_{m-1} \cdot F_{n}$ ways

The total number of ways to climb the $m+n-1$ stairs, then, is the sum of these two ways, and so it must be true that:

$$F_{m+n} = F_{m-1} \cdot F_{n} + F_{m} \cdot F_{n+1}$$

So note that after I established the connection between climbing stairs and the Fobonacci numbers, the proof was straightforward (and did not use induction). But to establish the connection, I used induction.

Answer 2

You can get away with inducting on just $n$:

$$ \begin{align} F(m + n) & = F(m + (n - 1)) + F(m + (n -2))\\ & = F(m-1)F(n-1) + F(m)F(n) + F(m-1)F(n-2) + F(m)F(n-1) \\ & = F(m-1)[F(n-1) + F(n-2)] + F(m)[F(n)+F(n-1)] \\ & = F(m-1)F(n) + F(m)F(n+1)\end{align}$$

Answer 3

A combinatorial proof (no induction).

Using the representation of the Fibonacci numbers as the numbers of domino coverings the given identity can be shown in a quick and elegant way.

It is known that the number of domino coverings of a $2\times N$ grid is $F_{N+1}$. Consider the number of domino coverings of a $2\times (m+n-1)$ grid. Any covering can be of two types.

1) The covering has a pair of horizontal dominoes at position $m-1$ and $m$.

Therefore on the left side we have a covering of a $2\times (m-2)$ grid and on the right side we have a covering of a $2\times (n-1)$ grid. Therefore the number of such coverings is $F_{m-1}\cdot F_{n}$.

2) The covering can be split into two coverings, one of a $2\times (m-1)$ grid and another of a $2\times n$ grid.

Therefore the number of such coverings is $F_{m}\cdot F_{n+1}$.

Finally we may conclude that the number of domino coverings of a $2\times (m+n-1)$ grid is $$F_{m+n}=F_{m-1}\cdot F_{n}+F_{m}\cdot F_{n+1}.$$

Answer 4

I won't mention every use of induction. Define $$M:=\left(\begin{array}{cc} 0 & 1\\ 1 & 1 \end{array}\right),\,V_{n}:=\left(\begin{array}{c} F_{n}\\ F_{n+1} \end{array}\right)=M^{n}\left(\begin{array}{c} 0\\ 1 \end{array}\right)$$ so $M^{m}=\left(\begin{array}{cc} F_{m-1} & F_{m}\\ F_{m} & F_{m+1} \end{array}\right)$ and $$\left(\begin{array}{c} F_{m+n}\\ F_{m+n+1} \end{array}\right)=M^{m}\left(\begin{array}{c} F_{n}\\ F_{n+1} \end{array}\right)=\left(\begin{array}{c} F_{m-1}F_{n}+F_{m}F_{n+1}\\ F_{m}F_{n}+F_{m+1}F_{n+1} \end{array}\right).$$