# Showing that an equation holds true with a Fibonacci sequence: $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question: Let $F_n$ the sequence of Fibonacci numbers, given by $F_0 = 0, F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Show for $n, m \in \mathbb{N}$: $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$

My (very limited) attempt so far: after creating a small list of the values $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34, F_{10}=55$ i can see that yes it does seem to work for instance $F_{6+3}=F_5 F_3 +F_6 F_4 = 10 +24 = 34 = F_9$. However, I really don't know where to begin as showing that this must hold in general terms. Should I be looking to use limits? Or perhaps induction? What is the best way to solve this?

-
I suppose using the Binet formula is a "mosquito-nuking" solution... but it works. – J. M. Nov 23 '10 at 7:17
@J.M.: "overkill" (FTFY) – Isaac Dec 24 '10 at 22:16
@Isaac, It's an idiom here and MO... – J. M. Dec 24 '10 at 23:58

Fix $m \in \mathbb{N}$. We shall use induction on $n$. For $n=1$, the RHS of the equation becomes $$F_{m-1}F_{1} + F_{m}F_{2} = F_{m-1} + F_{m}$$, which is equal to $F_{m+1}$. When $n=2$, the equation is also true.( I hope you can prove this!).

Now assume, that the result is true for $k=3,4, \cdots , n$. We want to show that the result is true for $k=n+1$. $$\text{For} \ k=n-1 \ \text{we have} \quad F_{m+n-1} = F_{m-1}F_{n-1} + F_{m}f_{n}$$ and $$\text{For} \ k = n \ \text{we have} \quad F_{m+n}=F_{m-1}F_{n} + F_{m}F_{n+1}$$ Adding both the sides you will get $$F_{m+n-1} + F_{m+n} = F_{m+n-1} = F_{m-1}F_{n+1} + F_{m}F_{n+2}$$

Oh, i reversed the notations. This is for proving $$F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1}$$

-
@Chandru1 thanks a lot for the help i think i'm slowly starting to understand this stuff. To prove it with $n=2$ i simply broke $F_{n+2}$ down into $F_{n+1} + F_n = F_n + F_{n-1} + F_n$ which is what i obtained when substituting $n=2$. – ghshtalt Nov 23 '10 at 18:45

If pressed, I'd nuke with Binet's formula myself, but here's another approach. By an easy induction, if $$A=\pmatrix{0&1\\\\ 1&1}$$ then $$A^n=\pmatrix{F_{n-1}&F_n\\\\ F_n&F_{n+1}}.$$ Comparing the top right entry in the equation $A^m A^n=A^{m+n}$ gives $$F_{m-1}F_n+F_m F_{n+1}=F_{m+n}.$$

-

HINT $\ \$ If you put the Fibonacci recurrence into matrix form then the result is obvious, viz.

$$M^n\ :=\ \left(\begin{array}{ccc} 1 & 1 \\\ 1 & 0 \end{array}\right)^n\ =\ \left(\begin{array}{ccc} F_{n+1} & F_n \\\ F_n & F_{n-1} \end{array}\right)$$

Now compute $\ M^{n+m}\ =\ M^n \ M^m$

-
ok so what i compute is: $$M_{n+m} = M_n*M_m = \left(\begin{array}{ccc} F_{n+1} & F_n \\\ F_n & F_{n-1} \end{array}\right)*\left(\begin{array}{ccc} F_{m+1} & F_m \\\ F_m & F_{m-1} \end{array}\right) = \left(\begin{array}{ccc} F_{n+1}F_{m+1} + F_nF_m & F_{n+1}F_m + F_nF_{m-1} \\\ F_nF_{m+1} + F_{n-1}F_m & F_{n}F_{m} + F_{n-1}F_{m-1} \end{array}\right)$$ which as you said shows the desired expression in the bottom left(and i assume equivalent) in the top right. is this method something one can usually use with sequences? i guess i just don't know how it works in general... – ghshtalt Nov 23 '10 at 8:37
that is, have i understood it correctly if i were to say that to define a sequence, one creates a $2 X 2$ matrix with the upper left value equal to the next value the bottom left and upper right values equal to the current value, and the bottom right equal to the previous? – ghshtalt Nov 23 '10 at 8:38
@user3711: The matrix $M$ is simply the shift operator viz. $\ (F_{n-1},F_n)\:M^t\ = (F_n,F_{n+1})\:.\$ The same idea works for any linear recurrence. – Bill Dubuque Nov 23 '10 at 17:38

With Fibonacci numbers usually there are multiple ways of proving identities.

One way (which is one of my favourites) to prove your identity is the following:

Consider the following problem:

A person climbs up $\displaystyle n$ steps, by taking either one step, or two steps at a time.

The total number of ways the person can climb up all the $\displaystyle n$ steps is $\displaystyle F_{n+1}$ (Why?)

Now consider climbing $\displaystyle m+n-1$ steps and split into the cases when the person lands on step $\displaystyle n$ and the cases when the person lands on step $\displaystyle n-1$ and takes two steps at that point (and so does not land on step $\displaystyle n$ in those cases). These two cases cover all possibilities, and so we have:

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

-
Right. This is basically the matrix proof translated into the language of walks on graphs, which is then further translated into a tiling problem. – Qiaochu Yuan Nov 23 '10 at 17:46
@Qia: That is one way of looking at it. But I wouldn't say it is basically just a translation... I think it is interesting on its own. – Aryabhata Nov 23 '10 at 18:11
I like this proof for giving a simple combinatorial interpretation of the result - it offers better 'motivation' IMHO than the matrix proof, which might look like magic to someone not familiar with those manipulations. – Steven Stadnicki Nov 23 '10 at 18:46
In any case it was good to try to see it from another angle, although to be honest, i'm still having some trouble really visualizing this, hopefully it hits me later... and yes the matrices seem really efficient but at least for me they still look like magic ;) – ghshtalt Nov 23 '10 at 18:52
@Steven: the two proofs are equivalent. Powers of the Fibonacci matrix count walks on a certain graph, the Fibonacci graph, which can in turn be interpreted in terms of certain tilings. I discuss a generalization to companion matrices in this blog post: qchu.wordpress.com/2009/08/23/… – Qiaochu Yuan Nov 23 '10 at 19:08

There are several good answers already, but I thought I would add the following derivation because it is one of the few uses I know for the sum property of permanents; namely,

If $A$, $B$, and $C$ are matrices with identical entries except that one row (column) of $C$, say the $k^{th}$, is the sum of the $k^{th}$ rows (columns) of $A$ and $B$, then $\text{ per } A + \text{ per } B = \text{per } C$.

Start with the matrices $\begin{bmatrix} F_n & F_{n-1} \\ F_0 & F_1 \end{bmatrix}$ and $\begin{bmatrix} F_n & F_{n-1} \\ F_1 & F_2 \end{bmatrix}$. Since $F_0 = 0$ and $F_1 = F_2 = 1$, they have permanents $F_n$ and $F_n + F_{n-1} = F_{n+1}$, respectively. Applying the Fibonacci recurrence and the permanent sum property, we have $\text{ per } \begin{bmatrix} F_n & F_{n-1} \\ F_2 & F_3 \end{bmatrix} = F_{n+2}$. By continuing to construct new matrices whose second rows are the sums of the second rows of the previous two matrices, this process continues until we have $F_n F_{m+1} + F_{n-1}F_m = \text{ per} \begin{bmatrix} F_n & F_{n-1} \\ F_m & F_{m+1} \end{bmatrix} = F_{n+m}.$

For more on this approach (but with determinants), see this paper I wrote a few years ago: "Fibonacci Identities via the Determinant Sum Property," The College Mathematics Journal, 37 (4): 286-289, 2006.

-
+1: Hadn't seen this before. – Aryabhata Nov 23 '10 at 23:49

Try proving this statement: Claim: If $f(n) = f(n-1)+f(n-2)$, then $f(n) = F_n f_1 + F_{n-1} f_0$.

Now "fix" $m$ and think of $F_{n+m}$ as a linear recurrence in $n$ with initial conditions $F_{m+1}$ and $F_m$.

By the way, there is a short and clean proof of Claim, but you should know it uses the fact $F_{-1} = 1$.(Something you can easily verify if you did not already know).

-

One simple way is to use the formula for the $n^{th}$ Fibonacci number, viz,

$F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}$ where $\phi$ is the golden ratio.

$\phi = \frac{1 + \sqrt{5}}{2}$.

Or another equally simple way is to use induction on $n$ and then on $m$ or just using induction on one of these might turn out to suffice.

It will be interesting to see a direct proof...

-
...and looks like somebody else did use Binet... :D – J. M. Nov 23 '10 at 7:20
@J.M. : I didn't see your comment when I wrote the answer :). – user17762 Nov 23 '10 at 7:23
am i interpreting this properly if i write: $\frac{\Phi^{n+m} - (1-\Phi)^{n+m}}{\sqrt{5}} = \frac{\Phi^{n-1} - (1-\Phi)^{n-1}}{\sqrt{5}} * \frac{\Phi^{m} - (1-\Phi)^{m}}{\sqrt{5}} + \frac{\Phi^{n} - (1-\Phi)^{n}}{\sqrt{5}} * \frac{\Phi^{1+m} - (1-\Phi)^{1+m}}{\sqrt{5}}$ $\frac{\Phi^{m} - (1-\Phi)^{m}}{\sqrt{5}}(\frac{\Phi^{n-1} - (1-\Phi)^{n-1}}{\sqrt{5}} + \frac{\Phi^{n} - (1-\Phi)^{n}}{\sqrt{5}} * F_1)$ $\frac{\Phi^{m} - (1-\Phi)^{m}}{\sqrt{5}}(\frac{\Phi^{n-1} - (1-\Phi)^{n-1}}{\sqrt{5}}+\frac{\Phi^{n} - (1-\Phi)^{n}}{\sqrt{5}})$ ? what can i do at the end? – ghshtalt Nov 23 '10 at 7:41
@user3711: Use $\phi^2 = 1 + \phi$ to simplify. Or as the others have stated you can try induction. – user17762 Nov 23 '10 at 7:45
i'm sorry, but i'm having trouble figuring out how to use that to simplify.... – ghshtalt Nov 23 '10 at 8:08

These can almost always be solved by induction. (In general sequences that are defined by recursion go often well together with induction.)

For this formula we can do the following: Induct on $m$. If $m=1$, then $F_{n+m} = F_{n}F_{m-1} + F_{n-1}F_m = F_{n}F_{0} + F_{n-1}F_1 = F_n + F_{n-1} = F_{n+1}$.

Suppose then that the result holds for $m$ and smaller. Now $$F_{n+m+1} = F_{n+m} + F_{n+m-1} = F_{n}F_{m-1} + F_{n-1}F_m + F_{n}F_{m-2} + F_{n-1}F_{m-1}$$ $$= F_{n}(F_{m-1} + F_{m-2}) + F_{n-1}(F_m + F_{m-1}) = F_{n}F_{m} + F_{n-1}F_{m+1}.$$

-