# Finding closed form of Fibonacci Sequence using limited information

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

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

• Just from your first relation, we have $F_n-F_{n-1}=F_{n-2}$ which gets you back to the usual recursion.
– lulu
Mar 5, 2020 at 0:25
• Also, I suppose that you meant to write $F_n<\left( \frac {1+\sqrt 5}2\right)^n$ for $2$.
– lulu
Mar 5, 2020 at 0:27
• 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.
– lulu
Mar 5, 2020 at 0:32
• 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 Mar 5, 2020 at 0:38
• 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$?
– lulu
Mar 5, 2020 at 0:39

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.