21
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I suppose using the Binet formula is a "mosquito-nuking" solution... but it works. $\endgroup$ – J. M. isn't a mathematician Nov 23 '10 at 7:17
  • $\begingroup$ @J.M.: "overkill" (FTFY) $\endgroup$ – Isaac Dec 24 '10 at 22:16
  • $\begingroup$ @Isaac, It's an idiom here and MO... $\endgroup$ – J. M. isn't a mathematician Dec 24 '10 at 23:58
  • $\begingroup$ Actually, Binet's formula, $F_n = (\varphi^n - \psi^n)/\sqrt{5}$ where $\varphi$ is the golden ratio and $\psi = 1 - \varphi$, is simple, proved using high-school algebra, and facilitates straightforward, direct proofs of many Fibonacci-number properties. $\endgroup$ – user0 Feb 3 '17 at 15:56
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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$. $\endgroup$ – ghshtalt Nov 23 '10 at 18:45
  • $\begingroup$ F(m+n−1)+F(m+n)=F(m+n−1). seems wrong. probably should be + instead of last - $\endgroup$ – RiaD Dec 11 '17 at 22:11
14
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ Right. This is basically the matrix proof translated into the language of walks on graphs, which is then further translated into a tiling problem. $\endgroup$ – Qiaochu Yuan Nov 23 '10 at 17:46
  • 3
    $\begingroup$ @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. $\endgroup$ – Aryabhata Nov 23 '10 at 18:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Nov 23 '10 at 18:46
  • $\begingroup$ 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 ;) $\endgroup$ – ghshtalt Nov 23 '10 at 18:52
  • $\begingroup$ @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/… $\endgroup$ – Qiaochu Yuan Nov 23 '10 at 19:08
13
$\begingroup$

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

Improve this answer
$\endgroup$
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$ – ghshtalt Nov 23 '10 at 8:37
  • $\begingroup$ 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? $\endgroup$ – ghshtalt Nov 23 '10 at 8:38
  • 5
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Nov 23 '10 at 17:38
5
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ ...and looks like somebody else did use Binet... :D $\endgroup$ – J. M. isn't a mathematician Nov 23 '10 at 7:20
  • $\begingroup$ @J.M. : I didn't see your comment when I wrote the answer :). $\endgroup$ – user17762 Nov 23 '10 at 7:23
  • $\begingroup$ 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? $\endgroup$ – ghshtalt Nov 23 '10 at 7:41
  • $\begingroup$ @user3711: Use $\phi^2 = 1 + \phi$ to simplify. Or as the others have stated you can try induction. $\endgroup$ – user17762 Nov 23 '10 at 7:45
  • $\begingroup$ i'm sorry, but i'm having trouble figuring out how to use that to simplify.... $\endgroup$ – ghshtalt Nov 23 '10 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.