Discrete Mathematics – Fibonacci Addition Law $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

discrete mathematicsfibonacci-numbers

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?

Best Answer

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

Related Solutions

[Math] Sum of product of Fibonacci numbers

Let's use $$ F_n = \frac{1}{\sqrt{5}} \left( \phi^n - (-1)^n \phi^{-n} \right) $$ where $\phi$ is a Golden ratio constant $\phi = \frac{\sqrt{5}+1}{2}$. Now the sum reduces to the combination of geometric sums: $$ \begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^k - (-1)^k \phi^{-k}\right)\left(\phi^{n-k} - (-1)^{n-k} \phi^{k-n}\right) \\ &=& \frac{1}{5}\sum_{k=1}^{n-1} \left(\phi^n - (-1)^k \phi^{n-2k} - (-1)^{n-k} \phi^{2k-n} + (-1)^n \phi^{-n} \right) \\ &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) - \frac{\phi^{n}}{5} \sum_{k=1}^{n-1} \left( -\phi^{-2}\right)^{k} - \frac{(-1)^{n}}{5} \phi^{-n} \sum_{k=1}^{n-1} \left(-\phi^2\right)^k \end{eqnarray} $$ Using the geometric sum $\sum_{k=1}^{n-1} x^k = \frac{x-x^n}{1-x}$ we get: $$\begin{eqnarray} \sum_{k=1}^{n-1} F_k F_{n-k} &=& \frac{n-1}{5} \left(\phi^{n} + (-1)^n \phi^{-n}\right) + \frac{2}{5} \frac{\phi^{n-1} + (-1)^n \phi^{1-n}}{\phi + \phi^{-1}} \\ &=& \frac{n-1}{5} L_n + \frac{2}{5} F_{n-1} \end{eqnarray} $$ where $L_n$ denotes $n$-th Lucas number.

Quick sanity check in Mathematica:

In[84]:= Table[
 Sum[Fibonacci[k] Fibonacci[n - k], {k, 1, n - 1}] == (n - 1)/
    5 LucasL[n] + 2/5 Fibonacci[n - 1], {n, 1, 6}]

Out[84]= {True, True, True, True, True, True}

The sum stated in the edited question is obtained by replacing $n$ with $n+1$ in the sum evaluated above: $$ \sum_{k=1}^{n} F_k F_{n+1-k} = \frac{n}{5} L_{n+1} + \frac{2}{5} F_n $$

Fibonacci Numbers – Summation of Fibonacci Numbers with Odd and Even n

Fibonacci numbers are defined by the recurrence relation,

$$F_n=F_{n-1}+F_{n-2},~~~F_1=F_2=1.$$

Rearranging, we have $F_{n-1}=F_n-F_{n-2}$. Letting $n=2k$,

$$F_{2k-1}=F_{2k}-F_{2(k-1)},$$

hence, the sum of odd-indexed Fibonacci numbers telescopes:

$$\sum_{k=2}^{m}F_{2k-1}=\sum_{k=2}^{m}(F_{2k}-F_{2(k-1)})=F_{2m}-F_{2}.$$

Since $F_1=F_2$,

$$\sum_{k=2}^{m}F_{2k-1}=F_{2m}-F_{2}\\ \implies F_1+\sum_{k=2}^{m}F_{2k-1}=F_{2m}\\ \implies \sum_{k=1}^{m}F_{2k-1}=F_{2m},$$

which is the formula the OP mentioned finding.

The derivation of the analogous formula for a sum of even-indexed Fibonacci numbers is highly similar. The key is the recurrence relation.

Best Answer

Related Solutions

[Math] Sum of product of Fibonacci numbers

Fibonacci Numbers – Summation of Fibonacci Numbers with Odd and Even n

Related Question