Fibonacci Sequence proof by induction

Question

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.

Answer 1

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.

Answer 2

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.