I'm trying to find the closed form of the Fibonacci recurrence but, out of curiosity, in a particular way with limited starting information. I am aware that the Fibonacci recurrence can be solved fairly easily using the characteristic root technique (and its corresponding linear algebra interpretation):



But what I'm wondering is if its possible to determine Fibonacci Recurrence's closed form using the following two theorems:

  1. $\forall n \ge 2, \sum_{i=1}^{n-2} F_i = F_n - 2$

  2. $\forall n \ge 1, F_n < ((1 + \sqrt 5)/2)^n $

I suspect that it may be possible because the 2nd theorem involves the "golden ratio" $\varphi = (1 + \sqrt 5)/2$, but I have no idea where I might start so some hints or a little insight would be appreciated. Both theorems are true and I can provide the proofs if necessary.

Im using the following definition of the Fibonacci Recurrence:

$F_0 = F_1 = 1$

$F_{i+1} = F_i + F_{i-1} , \forall i \ge 2$

  • 2
    $\begingroup$ Just from your first relation, we have $F_n-F_{n-1}=F_{n-2}$ which gets you back to the usual recursion. $\endgroup$
    – lulu
    Mar 5, 2020 at 0:25
  • $\begingroup$ Also, I suppose that you meant to write $F_n<\left( \frac {1+\sqrt 5}2\right)^n$ for $2$. $\endgroup$
    – lulu
    Mar 5, 2020 at 0:27
  • $\begingroup$ Further, you should clarify your sum in $1$. What is the lower limit? The usual identity is that $F_n-1=\sum_{i=0}^{n-2}F_i$. Not sure if you want a variant of that or not. $\endgroup$
    – lulu
    Mar 5, 2020 at 0:32
  • $\begingroup$ These two theorems come out of "Data Structures and Algorithm Analysis in Java" by Mark Allen Weiss, so these are it. I wouldn't reject variants of these outright, but I'd like to stick to these $\endgroup$ Mar 5, 2020 at 0:38
  • $\begingroup$ The problem is that, as you have written it, you have the lower limit as $i=i$. If you meant $i=1$, then what does your identity say for $n=2$? $\endgroup$
    – lulu
    Mar 5, 2020 at 0:39

1 Answer 1


To see that this does not work, note that your first relation quickly implies (for $n≥2$) $$F_n=F_{n-1}+F_{n-2}$$

which, of course, is the usual Fibonacci recursion. It also quickly shows that $F_2=2$.

Thus, to find a counterexample, we want initial conditions such that $F_0+F_1=2$ and for which the entire series satisfies the given inequality.

Take, for instance, $$F_0=\frac 12\quad \& \quad F_1=\frac 32$$

Standard methods show that, with those initial conditions, we get the closed formula $$F_n=\frac 12\times \left(\frac {1+\sqrt 5}2\right)^{n+1}+\;\;\frac 12\times \left(\frac {1-\sqrt 5}2\right)^{n+1}$$

But then simple numerical work establishes the desired inequality for modestly sized $n$ and for large $n$ the second term becomes negligible and the desired equality is easily shown for the first term.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .