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