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

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$

You must log in to answer this question.

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