# Is there a proof for this Fibonacci relationship?

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

-
Try using Binet's Formula. –  Blue Dec 15 '13 at 23:44
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
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

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

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

-

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.

-
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