1

Can someone please work me through this problem?

Let $(f_0, f_1,f_2,...)$ be the Fibonacci sequence, that is, $f_0=0$, $f_1=1$, and $f_n = f_{n−2} + f_{n−1}$ for all $n\ge2$. Prove that $f_n>(5/4)^n$ for all integers $n\ge3$.

I appreciate any kind of help :))

time zone
  • 11
  • 2
    Hint: to prove $P(n)$ for all integers $n\ge0$, prove $P(0)$, and prove $P(n)\to P(n+1)$ for all integers $n\ge0$. In this case, take $P(n)$ to be $f_{n+3}>(5/4)^{n+3}\land f_{n+4}>(5/4)^{n+4}$. Please edit your question to indicate where you're stuck, if you still are. – J.G. Dec 12 '22 at 12:25
  • May I please know why I have to use P(0) and not P(3)? I think I will have to use P(3) since it's the least integer that should be used to prove the fn >(5/4)^n but I might be wrong. Thank you for helping me out :)) – time zone Dec 12 '22 at 12:40
  • As you say, since the statement is meant to hold starting with $n=3$, your base case ought to be $P(3)$. – lulu Dec 12 '22 at 12:43
  • Then I assume that this is true for $n=k$ where $k>=2$ and this also holds for $k+1$ right? Then $f_k+1 > (5/4)^(k+1)$ correct? – time zone Dec 12 '22 at 12:52
  • Fine, let me reword the hint: change every $n\ge0$ to $n\ge3$, and change $P(n)$ to $f_n>(5/4)^n\land f_{n+1}>(5/4)^{n+1}$. – J.G. Dec 12 '22 at 14:01

1 Answers1

0

Upon working, I realised the normal single assumption in the induction hypothesis won't do this.
Define $P(n)$ as the statement $f_n > (5/4)^n \text{ and } f_{n+1} > (5/4)^{n+1}$, only being true if both conditions are true. Prove the base case for $n = 3$ accordingly, i.e, verify $2>(5/4)^3$ and $3>(5/4)^4$. Assume $P(k)$ holds for some natural number $k\ge3$. This implies: $$f_k>(5/4)^k, \space f_{k+1} > (5/4)^{k+1}$$ For the induction step, it will be sufficient to show $f_{k+2} > (5/4)^{k+2}$, since it implies $P(k+1)$ is true, as we already have $f_{k+1} > (5/4)^{k+1}$. We know $$f_{k+2} = f_{k+1} + f_k$$ By induction hypothesis, $f_k> (5/4)^k$ and $f_{k+1}>(5/4)^{k+1}$. We get $$f_{k+2} = f_k+f_{k+1}> (5/4)^k + (5/4)^{k+1}$$ Simplifying RHS by factoring $(5/4)^k$: $$f_{k+2} > \left(\frac54\right)^k\times \frac{9}{4}>\left(\frac54\right)^k \times \left(\frac54\right)^2$$ Thus, $$\color{green}{f_{k+2} > \left(\frac54\right)^{k+2}}$$ Which completes our induction step. I leave the rest to you.

D S
  • 4,961