Skip to main content
minor corrections
Source Link
Sil
  • 17k
  • 3
  • 39
  • 81

Using induction directly on the inequality directly is not very helpful, because the fact that $f(n)<1$ does not tell yousay how close the left side$f(n)$ is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usuallySimilar inequalities are often solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to. See for example $1$ theProve by induction $\sum \frac {1}{2^n} < 1$ $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 thisthe equality withby 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 equality implies the desired inequality as wellfollows trivially since $F_{n+5}/2^{n+4}$ is always a positive number.

Using induction directly on the inequality is not very helpful, because the fact that $f(n)<1$ does not tell you how close the left side is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usually solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to $1$ the $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 this equality with 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 equality implies the desired inequality as well.

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.

added 125 characters in body
Source Link
Sil
  • 17k
  • 3
  • 39
  • 81

Using induction directly on the inequality is not very helpful, because the fact that $f(n)<1$ does not tell you how close the left side is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usually solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to $1$ the $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 weit 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 this oneequality with induction (which I claim is rather simple, and you will getjust need to use $F_{n+2}=F_{n+1}+F_{n}$ in the induction step). Then the equality implies the desired inequality as well.

Using induction directly on the inequality is not very helpful, because the fact that $f(n)<1$ does not tell you how close the left side is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usually solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to $1$ the $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 we conjecture $$ \sum_{i=0}^{n+2}\frac{F_i}{2^{2+i}}=1-\frac{F_{n+5}}{2^{n+4}}. $$ Now prove this one with induction, and you will get the desired inequality as well.

Using induction directly on the inequality is not very helpful, because the fact that $f(n)<1$ does not tell you how close the left side is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usually solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to $1$ the $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 this equality with 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 equality implies the desired inequality as well.

Source Link
Sil
  • 17k
  • 3
  • 39
  • 81

Using induction directly on the inequality is not very helpful, because the fact that $f(n)<1$ does not tell you how close the left side is to $1$, so there is no reason it should imply that $f(n+1)<1$. This is usually solved by proving stronger statement, such as for example $f(n)=1-\frac{1}{n}$, which then encodes how close to $1$ the $f(n)$ is. My bet is that your exercise is designed to demonstrate this observation.

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 we conjecture $$ \sum_{i=0}^{n+2}\frac{F_i}{2^{2+i}}=1-\frac{F_{n+5}}{2^{n+4}}. $$ Now prove this one with induction, and you will get the desired inequality as well.