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

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

  • $\begingroup$ Try using Binet's Formula. $\endgroup$
    – Blue
    Dec 15, 2013 at 23:44
  • 2
    $\begingroup$ 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$. $\endgroup$
    – MJD
    Dec 15, 2013 at 23:52
  • 1
    $\begingroup$ I think the way that you arrived at this already is a proof by induction on $x$. $\endgroup$
    – Carsten S
    Dec 16, 2013 at 0:23
  • $\begingroup$ It also appears in the Wikipedia article. $\endgroup$
    – MJD
    Dec 16, 2013 at 0:34

3 Answers 3


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

  • $\begingroup$ Welcome back! ${}{}$ $\endgroup$
    – MJD
    Dec 16, 2013 at 1:33
  • $\begingroup$ I'm having trouble understanding the first line of matrices. And the third line. And what M^n is. $\endgroup$
    – JShoe
    Dec 21, 2013 at 5:15
  • $\begingroup$ @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. $\endgroup$ Dec 21, 2013 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.

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

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.