# Fibonacci Sequence proof by induction

Let $$F_0, F_1, F_2, ..., F_n, ...$$ be the Fibonacci sequence, defined by the recurrence $$F_0 = F_1 = 1$$ and $$\forall n \in \Bbb{N},$$ $$F_{n+2} = F_{n+1} + F_n$$. Give a proof by induction that $$\forall n \in \Bbb{N},$$ $$\sum_{i=0}^{n+2} \frac{F_i}{2^{2+i}} < 1.$$

I showed that the "base case" works i.e. for $$n = 1$$, I showed that $$\sum_{i=0}^3 \frac{F_i}{2^{2+i}} = \frac{19}{32} < 1.$$

After this, I know you must assume the inequality holds for all $$n$$ up to $$k$$ and then show it holds for $$k +1$$ but I am stuck here.

• Evidently he means the second of those definitions; otherwise $\frac12$ is an upper bound. – Mark Fischler Jul 19 '19 at 22:53
• @MarkFischler I edited the question to add more details. Could you clarify your comment? – EtherealMist Jul 19 '19 at 23:07
• You have $2^{2+i}$ in one place, $2^2+i$ in another. They are different. Which (if either) do you want? – Gerry Myerson Jul 20 '19 at 4:38
• It is more common to define $F_0=0$ and $F_1=F_2=1.$ – DanielWainfleet Jul 20 '19 at 7:03
• @GerryMyerson/ I assumed that $2^2+i$ was a typo and edited it. – DanielWainfleet Jul 20 '19 at 7:04

Using induction on the inequality directly is not helpful, because $$f(n)<1$$ does not say how close the $$f(n)$$ is to $$1$$, so there is no reason it should imply that $$f(n+1)<1$$. Similar inequalities are often solved by proving stronger statement, such as for example $$f(n)=1-\frac{1}{n}$$. See for example Prove by induction $\sum \frac {1}{2^n} < 1$ .
With this in mind and by experimenting with small values of $$n$$, you might notice: $$\sum_{i=0}^{1+2} \frac{F_i}{2^{2+i}} = \frac{19}{32} = 1-\frac{13}{32}=1-\frac{F_6}{32}\\ \sum_{i=0}^{2+2} \frac{F_i}{2^{2+i}} = \frac{43}{64} = 1-\frac{21}{64}=1-\frac{F_7}{64}\\ \sum_{i=0}^{3+2} \frac{F_i}{2^{2+i}} = \frac{94}{128} = 1-\frac{34}{128}=1-\frac{F_8}{128}$$ so it is natural to conjecture $$\sum_{i=0}^{n+2}\frac{F_i}{2^{2+i}}=1-\frac{F_{n+5}}{2^{n+4}}.$$ Now prove the equality by induction (which I claim is rather simple, you just need to use $$F_{n+2}=F_{n+1}+F_{n}$$ in the induction step). Then the inequality follows trivially since $$F_{n+5}/2^{n+4}$$ is always a positive number.
It is easy to prove by induction that $$F_n=\frac{\left(\frac{1+\sqrt{5}}{2} \right)^{n+1}-\left(\frac{1-\sqrt{5}}{2} \right)^{n+1}}{\sqrt{5}}$$ Your series is the sum of two geometric progressions.
• I'm still confused. Also, how do you factor in the $\frac{1}{2^{2+i}}$ part into this? – EtherealMist Jul 20 '19 at 22:22
• One geometric progression has a common ratio $\frac{1+\sqrt{5}}{2 \cdot 2}$. The second geometric progression has a common ratio $\frac{1-\sqrt{5}}{2 \cdot 2}$. – Witold Jul 20 '19 at 22:30