Fibonacci addition law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

$$ M^n\ :=\ \left[\begin{array}{rr} \!\!1 & 1 \\\ \!\!1 & 0 \end{array}\right]^{\large n} =\, \left[\begin{array}{cc} F_{n+1} &\!\! F_n \\\ F_n &\!\! F_{n-1} \end{array}\right] $$

Now comparing the entries of $\ M^{n+m} = M^n \ M^m\,$ immediately yields the Fibonacci addition law.

Remark $\ M$ is the shift operator, i.e. $\,(F_{n−1},F_n)M^t = (F_n,F_{n+1}).\,$ The same idea works for any linear recurrence.

Answer 4

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

Answer 5

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

Then your claim will follow.

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

Answer 6

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.

Answer 7

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

Answer 8

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