4

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.

Martin Sleziak
  • 53,687
Josh
  • 41
  • 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 – Luke Naylor Apr 04 '18 at 17:53
  • 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.$) – Thomas Andrews Apr 04 '18 at 18:03
  • See https://math.stackexchange.com/a/1538834/589 – lhf Apr 04 '18 at 18:03
  • Could someone explain how to find the basis step. – Josh Apr 04 '18 at 18:09

5 Answers5

3

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$$

lab bhattacharjee
  • 274,582
2

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.

Maggie Myers
  • 244
2

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$

Mathejunior
  • 3,344
0

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}$

Martin Sleziak
  • 53,687
Acccumulation
  • 12,210
0

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}.$$

farruhota
  • 31,482