1
$\begingroup$

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

http://discrete.openmathbooks.org/dmoi3/sec_recurrence.html

https://en.wikipedia.org/wiki/Recurrence_relation#Solving_non-homogeneous_linear_recurrence_relations_with_constant_coefficients

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$

$\endgroup$
12
  • 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 '20 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 '20 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 '20 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$ – bmanicus131 Mar 5 '20 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 '20 at 0:39
1
$\begingroup$

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.

$\endgroup$

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.