Krdytkyu

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?

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.

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

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

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 $2times N$ grid is $F_{N+1}$. Consider the number of domino coverings of a $2times (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 $2times (m-2)$ grid
and on the right side we have a covering of a $2times (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 $2times (m-1)$ grid and another of a $2times 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 $2times (m+n-1)$ grid is
$$F_{m+n}=F_{m-1}cdot F_{n}+F_{m}cdot F_{n+1}.$$