4
$\begingroup$

Recall that the Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n−1} + F_{n−2}$ for $n ≥ 2$. Prove that:

$$\forall \,\, n ≥ 1 ,\,\, F_n < \left(\frac 74\right)^n$$

In this question I understand how to do the basis step. In the induction step I know that you have to assume that n=k but I am having trouble figuring out on how to do that. Could someone please explain how to do this question.

$\endgroup$
  • $\begingroup$ there's something called strong induction where, instead of assuming it's true for n=k, you assume it's true for all n<=k $\endgroup$ – Luke Naylor Apr 4 '18 at 17:53
  • $\begingroup$ You have to prove two basis steps, $n=1,n=2$ then do the induction step to show that if true for $n=k-1,n=k$ then it is true for $n=k$ and $n=k+1.$ (Which really means show it for $n=k+1.$) $\endgroup$ – Thomas Andrews Apr 4 '18 at 18:03
  • $\begingroup$ See math.stackexchange.com/a/1538834/589 $\endgroup$ – lhf Apr 4 '18 at 18:03
  • $\begingroup$ Could someone explain how to find the basis step. $\endgroup$ – Josh Apr 4 '18 at 18:09
2
$\begingroup$

Use strong induction

It's sufficient to show

$$(7/4)^m+(7/4)^{m+1}<(7/4)^{m+2}$$

$$\iff1+(7/4)<(7/4)^2$$

$$\iff4^2+7\cdot4<7^2$$

$\endgroup$
  • $\begingroup$ but i didnt understand question alot $\endgroup$ – Noor Boeing Mar 31 '18 at 0:47
  • $\begingroup$ @NoorBoeing, Please pinpoint your confusion $\endgroup$ – lab bhattacharjee Mar 31 '18 at 0:48
  • $\begingroup$ I didnt understand your suggested answer $\endgroup$ – Noor Boeing Mar 31 '18 at 0:49
  • $\begingroup$ @NoorBoeing, Assume $F(n)<(7/4)^n$ for $n\le m+1$ $\endgroup$ – lab bhattacharjee Mar 31 '18 at 2:12
2
$\begingroup$

The proof will be by strong induction on n. There are two steps you need to prove here since it is an induction argument. You will have two base cases since it is strong induction.

First show the base cases by showing this inequailty is true for n=1 and n=2.

Then for the inductive step, assume the inequality is true for $F_{n-1}$ and $F_{n-2}$ (known as the inductive hypothesis) then show it is true for $F_{n}$.
$F_{n}$

=$F_{n-1}$+$F_{n-2}$ (by definition of Fibonacci numbers.)

<$(7/4)^{n-1}$+$(7/4)^{n-2}$ (by the inductive hypotheses)

=$(7/4)^{n-2}((7/4)+1)$ (arithmetic, factor $(7/4)^{n-2}$ from both terms)

=$(7/4)^{n-2} ((28/16)+16/16)$ (arithmetic, why? I wanted to compare to $7/4^2$=49/16 so I wanted a denominator of 16)

=$(7/4)^{n-2}(42/16)$ <$(7/4)^{n}$. (since 42/16<49/16)

So by the principle of mathematical induction, this inequality is true.

Hope this makes sense now.

$\endgroup$
  • $\begingroup$ its confusing.... $\endgroup$ – Noor Boeing Mar 31 '18 at 0:58
1
$\begingroup$

There's something called Strong Induction.

The base cases are for $F_k$ such that $k=0,1$.

For the inductive step, assume that $\exists~ n$ such that $F_{n-1}<\frac{7^n}{4^n}$ and $F_{n-1}<\frac{7^{n-1}}{4^{n-1}}$

It's now quite easy to show that $$\begin{align*} F_{n+1}&=F_n+F_{n-1}\\ &<\frac{7^n}{4^n} + \frac{7^{n-1}}{4^{n-1}}\\ &<\frac{7^{n+1}}{4^{n-1}} \end{align*}$$ for all $n\geq 1$

$\endgroup$
0
$\begingroup$

Method 1: Base case: $$F_1=1<\frac74; F_2=1<\frac74.$$ Inductive hypothesis: $$F_{n-1}<\left(\frac74\right)^{n-1}; F_n<\left(\frac74\right)^n.$$ Inductive step: $$F_{n+1}=F_{n-1}+F_n<\left(\frac74\right)^{n-1}+\left(\frac74\right)^n=\left(\frac74\right)^n\left(\frac47+1\right)<\left(\frac74\right)^{n+1}.$$

Method 2: Prove $F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}<\left(\frac74\right)^n$.

Base case: $F_1=1<\frac74$.

Inductive hypothesis: the above estimate.

Inductive step: $$F_{n+1}=\frac{\phi^n\cdot \frac{1+\sqrt{5}}{2}-\psi^n\cdot \frac{1-\sqrt{5}}{2}}{\sqrt{5}}=$$ $$\left(\frac12+\frac{\sqrt{5}}{2}\right)\cdot \frac{\phi^n-\psi^n}{\sqrt{5}}+2\left(\frac{1-\sqrt{5}}{2}\right)^n<$$ $$\left(\frac12+\frac{\sqrt{5}}{2}+2\right)\cdot \left(\frac74\right)^n<\left(\frac74\right)^{n+1}.$$

$\endgroup$
0
$\begingroup$

The proposition that you're trying to prove is that $F_n<(\frac{7}{4})^n$

For $n = 0$, this is trivial; $0 < (\frac{7}{4})^0$

For $n = 1$, we have $1 < (\frac{7}{4})^1$

For your induction step, you assume that for all k < n, $F_k<(\frac{7}{4})^k$

So $F_{n-2}<(\frac{7}{4})^{n-2}$ and $F_{n-1}<(\frac{7}{4})^{n-1}$

$F_{n} = $

$F_{n-2}+ F_{n-1}$ <

$(\frac{7}{4})^{n-2} + (\frac{7}{4})^{n-1}$ =

$(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} = $

$\frac 4 4(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} $=

$\frac {11} 4 (\frac{7}{4})^{n-2}$=

$\frac {44} {16} (\frac{7}{4})^{n-2}$<

$\frac {49} {16} (\frac{7}{4})^{n-2}$=

$ (\frac{7}{4})^{n}$

$\endgroup$
  • $\begingroup$ Could you please show the basis step as well. $\endgroup$ – Josh Apr 4 '18 at 18:23

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.