3

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.

Sil
  • 16,612
EtherealMist
  • 219
  • 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 04:38
  • It is more common to define $F_0=0$ and $F_1=F_2=1.$ – DanielWainfleet Jul 20 '19 at 07:03
  • @GerryMyerson/ I assumed that $2^2+i$ was a typo and edited it. – DanielWainfleet Jul 20 '19 at 07:04
  • It is $2^{2+i}$ – EtherealMist Jul 20 '19 at 19:47
  • Does anyone have any hints to solve this? Some additional context: this is a first year intro to proofs course. – EtherealMist Jul 20 '19 at 20:01
  • Why $n+2$? This is true even with $\sum_{i=0}^{n} \frac{F_i}{2^{2+i}} < 1$ – Sil Jul 20 '19 at 22:25
  • @Sil I don't know. The question was just given that way. Any tips or hints? I'm really having trouble figuring it out. – EtherealMist Jul 20 '19 at 22:27
  • Not by induction (induction is generally bad when you want to compare inequality of form $f(n)<c$ with a constant $c$ (there is no reason why if $f(n)=0.999999$ should imply that $f(n+1)<1$ as well). This is usually resolved by proving stronger statement instead, something like $f(n)<c-\frac{1}{n}$, which in this case might be tricky to find. Without induction, there is quite an easy proof though, you can prove that the infinite sum $\sum_{i=0}^{\infty} \frac{F_i}{2^{2+i}}=1$, and since individual terms are non-negative, the statement follows. – Sil Jul 20 '19 at 22:33
  • @Sil I see. Unfortunately we don't deal with infinite sums in this course so it would have to be by induction. I just can't see it, though. Thanks for the help. – EtherealMist Jul 20 '19 at 23:49

2 Answers2

1

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.

Witold
  • 942
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.

Sil
  • 16,612