3
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much! $\endgroup$ – EtherealMist Jul 21 '19 at 20:26
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sorry, I don't understand how this will help prove the proposition? $\endgroup$ – EtherealMist Jul 20 '19 at 20:00
  • $\begingroup$ You need to find the sum of two geometric progressions. It is easy. $\endgroup$ – Witold Jul 20 '19 at 22:09
  • $\begingroup$ I'm still confused. Also, how do you factor in the $\frac{1}{2^{2+i}}$ part into this? $\endgroup$ – EtherealMist Jul 20 '19 at 22:22
  • $\begingroup$ 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}$. $\endgroup$ – Witold Jul 20 '19 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.