1
$\begingroup$

I need help with the last inductive steps, can someone help? I hope my formatting is good enough, first time here.

The case:

"Let the fibonacci sequence be recursivly defined so that $$F_0 = 0, F_1 = 1$$ Else if n >= 2 $$F_n = F_{n-1}+F_{n-2} $$ Prove that $$F_n \geq (3/2)^{n-1}$$ For all numbers in the set $\{6,7,8,9...\}$"

Basecase: $$F_{2} = F_{1} + F_{0} = 1 + 0 $$ $$F_{3} = F_{2} + F_{1} = 1 + 1 $$ $$F_{4} = F_{3} + F_{2} = 2 + 1 $$ $$F_{5} = F_{4} + F_{3} = 3 + 2 $$ $$F_{6} = F_{5} + F_{4} = 5 + 3 $$

$$F_{6} \geq (3/2)^{5} = 8 \geq 7.59 $$

Induction step:

We assume the above is true for $n=k$, so now we prove it is true for $n=k+1$

We remember $$F_n \geq (3/2)^{n-1}$$

$$F_{k+1} \geq (3/2)^{k}$$

We know that

$$ F_{k} = F_{k-1}+F_{k-2} $$ $$ F_{k+1} = F_{k}+F_{k-1} $$ $$ F_{k}+F_{k-1} \geq (3/2)^{k} $$

I'm not quite sure where to go from here, can anyone help? I've looked at another thread about the same question, but I don't understand the last part of his equation nor the answers.

In my case we are told that "you may need to use $(3/2)+1 > (3/2)^{2}$", but I don't know how to apply it to my case.

$\endgroup$
  • $\begingroup$ See math.stackexchange.com/a/1343414/589. $\endgroup$ – lhf Oct 25 '18 at 11:29
  • $\begingroup$ Ihf, thanks but I already read that actually. Inside the link I post there's also a direction to that exact answer, but I couldn't understand it. However, José's answer makes perfect sense to me and is very intuitive - to me atleast! $\endgroup$ – jubibanna Oct 25 '18 at 14:24
3
$\begingroup$

If $F_k\geqslant\left(\frac32\right)^{k-1}$ and $F_{k+1}\geqslant\left(\frac32\right)^k$, then\begin{align}F_{k+2}&=F_k+F_{k+1}\\&\geqslant\left(\frac32\right)^{k-1}+\left(\frac32\right)^k\\&=\left(\frac32\right)^{k-1}\left(1+\frac32\right)\\&>\left(\frac32\right)^{k-1}\left(\frac32\right)^2\\&=\left(\frac32\right)^{k+1}.\end{align}

$\endgroup$
  • $\begingroup$ Thanks, this makes very much sense! <3 $\endgroup$ – jubibanna Oct 25 '18 at 10:45
  • $\begingroup$ José, how can $(3/2)^{k-1} + (3/2)^{k}$ be equal to $(3/2)^{k-1}(1+3/2)$ ? $\endgroup$ – jubibanna Oct 25 '18 at 14:33
  • $\begingroup$ I did not claim that they are equal. What I claimed was that$$\left(\frac32\right)^{k-1}+\left(\frac32\right)^k=\left(\frac32\right)^{k-1}\left(1+\frac32\right).$$ $\endgroup$ – José Carlos Santos Oct 25 '18 at 14:34
  • $\begingroup$ Sorry, just edited my question. How did you find it's the same? $\endgroup$ – jubibanna Oct 25 '18 at 14:38
  • $\begingroup$ \begin{align}\left(\frac32\right)^{k-1}+\left(\frac32\right)^k&=\left(\frac32\right)^{k-1}+\left(\frac32\right)^{k-1}\times\frac32\\&=\left(\frac32\right)^{k-1}\left(1+\frac32\right).\end{align} $\endgroup$ – José Carlos Santos Oct 25 '18 at 14:45
0
$\begingroup$

Write $F_{k+1}\geq (3/2)^k+(3/2)^{k-1}=(3/2)^{k-1}(1+3/2)$ from here you can finish using the hint.

$\endgroup$
  • $\begingroup$ Thanks for the reply, it helped me to make sense of it all! $\endgroup$ – jubibanna Oct 25 '18 at 10:45
  • $\begingroup$ No problem, I am happy it was helpfull $\endgroup$ – Madarb Oct 25 '18 at 10:48

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.