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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Mar 5, 2020 at 0:39

1 Answer 1

Reset to default
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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.