Question

The Fibonacci numbers are recursively dened by F1 = 1; F2 = 1 and for n > 1; F_(n+1) = F_n + F_(n-1): So the rst few Fibonacci Numbers are: 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; : : : There are numerous properties of the Fibonacci numbers.

a) Use the principle of Strong Induction to show that all integers n > 1 and m > 0

F_(n-1)F_(m )+ F_(n)F_(m+1) = F_(n+m):

Solution. (Hint: Use induction with respect to m. First verify the formula the base case,for m = 1 case (here use again induction on n) the assume that it is true for m = 1;m = 2; ;m = k then prove that it remains true if m = k + 1 (still with the use of induction on n)

Answer 1

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 nn stairs, then it turns out there are Fn+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)=F2=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)=F3=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 Fn way thto climbinge n−1 stairs after having taken a step of 1 stairs, and there are Fn−1 ways to finish climbing the n−2 stairs after having taken a step of 2 stairs. So, there are Fn+Fn−1=Fn+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 Fm+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 Fm ways. And since then there are Fn+1 ways to climb the first n stairs, that means that there are Fm⋅Fn+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−1stairs, which can be done in Fn 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 Fm−1⋅Fn 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:

Fm+n=Fm−1⋅Fn+Fm⋅Fn+1