Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was looking at the decomposition of Fibonacci numbers using the definition of $F_n = F_{n-1} + F_{n-2}$, and noted the pattern in the coefficients of the terms were Fibonacci numbers. It appears to hold, and I believe it's true, but I haven't seen a proof for it. Does one exist?

$F_n = 1F_{n-1} + 1F_{n-2}$
$F_n = 2F_{n-2} + 1F_{n-3}$
$F_n = 3F_{n-3} + 2F_{n-4}$
$F_n = 5F_{n-4} + 3F_{n-5}$
etc

This can be generalized to
$F_n = F_xF_{n-(x-1)}+F_{x-1}F_{n-x}$

share|improve this question
    
Try using Binet's Formula. –  Blue Dec 15 '13 at 23:44
2  
Yes, that identity is well-known. There are several proofs, one of which I wrote up on this web site a couple of months ago, in the form $f_{i+k} = f_kf_{i-1} + f_{k+1}f_i$. –  MJD Dec 15 '13 at 23:52
1  
I think the way that you arrived at this already is a proof by induction on $x$. –  Carsten Schultz Dec 16 '13 at 0:23
    
It also appears in the Wikipedia article. –  MJD Dec 16 '13 at 0:34

3 Answers 3

up vote 8 down vote accepted

HINT $\ \ $ If you change variables this Fibonacci addition law can be put in the form

$$\color{#c00}{F_{n+m} = F_nF_{m+1} + F_{n-1}F_m} $$

Expressing the Fibonacci recurrence in matrix form makes the proof of the addition law easy

$$ 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) $$ $$\begin{eqnarray} 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) \\ \\ \\ \Rightarrow\ \ \left(\begin{array}{ccc} F_{n+m+1} & F_{n+m} \\\ \color{#c00}{F_{n+m}} & F_{n+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} \\\ \color{#C00}{F_nF_{m+1} + F_{n-1}F_m} & F_{n}F_{m} + F_{n-1}F_{m-1} \end{array}\right)\end{eqnarray}$$

share|improve this answer
    
Welcome back! ${}{}$ –  MJD Dec 16 '13 at 1:33
    
I'm having trouble understanding the first line of matrices. And the third line. And what M^n is. –  JShoe Dec 21 '13 at 5:15
    
@Jshoe $\ M$ is the matrix being raised to power $n$. That first matrix equality is very easily proved by induction, using the fib recurrence. The 3rd line is just the 2nd line with the entries of $M^{n+m}$ listed on the LHS, and the matrix product computed on the RHS. –  Bill Dubuque Dec 21 '13 at 5:27

First, I want to say that I agree with Carsten Schultz's comment: what you have is almost a proof by induction, and it could be turned into one without much trouble. But I think the proof that follows is very elegant, in the sense of revealing a deeper truth, so I'd like to present it again.

Let's call a sequence "fibonacci-like" if it satisfies the recurrence $$s_{n+2} = s_n + s_{n+1}$$ for all $n$. It's easy to see (or to show) that if $s$ and $t$ are two fibonacci-like sequences, then so is the sequence that you get by multiplying every term of $s$ or of $t$ of them by some constant, and so is the sequence you get by adding together corresponding terms of $s$ and $t$. For example, $1,1,2,3,5,8\ldots$ and $2,8,10,18,28,\ldots$ are both fibonacci-like, and so is what you get if you multiply every element of $1,1,2,3,5,8\ldots$ by 3, namely $3,3,6,9,15,24,\ldots$, and so is what you get if you add them together: $3,9,12,21,33,54,\ldots$.

Since any such sequence $s_i$ is completely determined by $s_0$ and $s_1$, we can agree to write a fibonacci-like sequence with the notation $[s_0, s_1]$, where $s_0$ and $s_1$ are the first two terms of the sequence; that tells us everything about it. Then the Fibonacci sequence itself is written $[0, 1]$, whereas $[1, 3]$ is the Lucas sequence $1,3,4,7,11,\ldots$.

Observe that in this notation, $[a_0, a_1] + [b_0, b_1] = [a_0+ b_0, a_1+b_1]$. So for example if you add the Fibonacci sequence $[0,1]$ to itself, you get $[0,2]$, which is in fact the sequence $0, 2, 2, 4, 6, 10,\ldots$ that you get from adding the Fibonacci sequence to itself termwise. Similarly, $c\cdot[a_0, a_1] = [c\cdot a_0 , c\cdot a_1]$. For example if you double every term of the Lucas sequence $[1,3] = 1,3,4,7,11,\ldots$ you get $2,6,8,14,22,\ldots$, which is exactly the sequence we are writing as $[2,6]$.

Finally, observe that $[0,1]$ is that standard Fibonacci sequence whose $i$th term is $f_i$, and $[1,0]$ is the "shifted" Fibonacci sequence, whose $i$th term is $f_{i-1}$. (Note that I am following the standard convention here that has $f_0 = 0$ and $f_1 = 1$; your $F_i$ seems to have $F_0 = 1$ and $F_1=1$, which is not the usual convention.)

Now suppose we have some fibonacci-like sequence $ s = [a, b]$. (Remember, $[a,b]$ is just shorthand for the fibonacci-like sequence $a, b, a+b, a+2b, 2a+3b, \ldots$.) We can decompose $[a,b]$ as follows: $$[a,b] =b[0,1] + a[1,0] $$ which shows that $s_i = bf_i + af_{i-1}$. Indeed if you look at a the example terms I showed above you see for example that $s_4 = 2a + 3b = af_3 + bf_4$. This identity holds for any fibonacci-like sequence:

If $s$ is a fibonacci-like sequence whose first two terms are $s_0$ and $s_1$, then $$s_i = s_0f_{i-1} + s_1f_i$$ for all $i$.

(You have to properly understand $f_{-1} = 1$ for this to work at $i=0$.)

Now consider the Fibonacci sequence shifted over $k$ places for some fixed $k$: this sequence begins $f_k, f_{k+1}, f_{k+2}, \ldots$; its $i$th term is $f_{i+k}$. Obviously it is fibonacci-like. In our notation it is represented as $[f_k, f_{k+1}]$ and by the previous paragraph it is equal to $f_k[1,0] + f_{k+1}[0,1]$, so by the previous theorem its $i$th term is equal to $f_kf_{i+1} + f_{k+1}f_i$. But it's $i$th term is also equal to $f_{i+k}$, so we have:

$$f_{i+k} = f_kf_{i-1} + f_{k+1}f_i.$$

Now put $i=x, k = n-x$ and we have your claim, except you have $F_n = f_{n+1}$, so the subscripts are a little muddled.

share|improve this answer

Try going the other way.

$F_n = F_{n-1} + F_{n-2}$

$F_{n+1} = F_n + F_{n-1} = F_{n-1} + F_{n-1} + F_{n-2}$

$F_{n+2} = F_{n+1} + F_{n} = F_{n} + F_{n} + F_{n-1} = 2(F_{n-1}+F_{n-2})+F_{n-1}$

Etc. Hopefully the pattern becomes more "obvious" when seen this way. Then once you get to $F_{n+x}$, replace that with $F_{n}$ and replace your $F_n$ terms with $F_{n-x}$ and you should rederive your formula.

share|improve this answer
    
The pattern was obvious to begin with, I'm just not sure that that is a satisfactory proof in and of itself. –  JShoe Dec 15 '13 at 23:59
    
I agree. OP asked for a proof, but this isn't one. –  MJD Dec 16 '13 at 0:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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