2
$\begingroup$

I was working on my homework assignment for one of my classes and I have come across a proof question that my classmates and I are finding difficult to answer.

The problem is asking us to prove that for Fibonacci numbers defined as $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$, this holds true: $F_n \geq (\sqrt{2})^{n-2}$.

We are trying to prove this by induction, and the base case holds. However, we are having trouble with the inductive step. We started with assuming that $F_n \geq (\sqrt{2})^{n-2}$ holds true for n, but proving this for n+1 is proving (pun maybe intended) to be difficult.

We were playing around with the assumption and then played around with what we need to prove ($F_{n+1} \geq (\sqrt{2})^{n-1}$):

\begin{equation*} F_{n+1} \geq (\sqrt{2})^{n-1} \\ F_{n+1} = F_{n} + F_{n-1} \geq (\sqrt{2})^{n-1} \\ F_{n} + F_{n-1} \geq (\sqrt{2})^{n-1} \end{equation*}

We know that $F_n \geq (\sqrt{2})^{n-2}$ is true from the assumption and $(\sqrt{2})^{n-2} \leq (\sqrt{2})^{n-1}$, but we're not sure how to use those for the proof.

If you could help us with this, that would be great. Thanks in advance.

$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression $\endgroup$ Commented Feb 9, 2016 at 22:01
  • $\begingroup$ Your inductive hypothesis should include two inequalities, for $F_n$ and $F_{n-1}$. $\endgroup$ Commented Feb 9, 2016 at 22:02
  • $\begingroup$ Hint $1+\sqrt 2\gt 2$ and $2=(\sqrt 2)^2$ $\endgroup$ Commented Feb 9, 2016 at 22:02

3 Answers 3

Reset to default
2
$\begingroup$

HINT: If you assume that $F_k\ge 2^{(k-2)/2}$ for all $k\le n$, then you have

$$\begin{align*} F_{n+1}&=F_n+F_{n-1}\\ &\ge 2^{(n-2)/2}+2^{(n-3)/2}\\ &=2^{(n-3)/2}\left(2^{1/2}+1\right)\;, \end{align*}$$

so you’d be done if you could show that

$$2^{(n-3)/2}\left(2^{1/2}+1\right)\ge 2^{(n-1)/2}\;.$$

Now use the fact that $2^{(n-1)/2}=2\cdot 2^{(n-3)/2}$.

$\endgroup$
0
0
$\begingroup$

Use the principle of strong induction. You may assume not only that $F_n\geq(\sqrt{2})^{n-2}$, but also that $F_k\geq(\sqrt{2})^{k-2}$ for all $k$ between $1$ and $n$. Then you get $$F_{n+1}=F_n+F_{n-1}\geq (\sqrt{2})^{n-2}+(\sqrt{2})^{n-3}=(\sqrt{2})^{n-1}(1/\sqrt{2}+1/2).$$ Where can you go from here?

$\endgroup$
0
$\begingroup$

First of all, what you are trying to prove is false, for just the case $n=0$. $0\not\geq (\sqrt{2})^{-2} = \frac12$. So let's restate the theorem to say for all $n>0$ $f_n \geq (\sqrt{2})^{n-2} $.

The induction proof is easiest if you break the problem down into odd and even cases. Then the statement to be proven is that for all $n>0$, $$ F_{2n-1} \geq (\sqrt{2})^{(2n-1)-2} \text{ and } F_{2n} \geq (\sqrt{2})^{2n-2} $$

Establish the basis: When $n=1$, $F_1 = 1 > (\sqrt{2})^{-1}$ and $F_2 = 2 > (\sqrt{2})^{0}$.

Now assume the statement for $n$: $F_{2n-1} \geq (\sqrt{2})^{(2n-1)-2} \text{ and } F_{2n} \geq (\sqrt{2})^{2n-2}$.

The statement for $n+1$ is $F_{2n+1} \geq (\sqrt{2})^{(2n+1)-2} \text{ and } F_{2n+2} \geq (\sqrt{2})^{2n+2-2}$ or $$ F_{2n+1} \geq (\sqrt{2})^{2n-1} \text{ and } F_{2n+2} \geq (\sqrt{2})^{2n} $$

Let's prove the first clause first: $$ F_{2n+1} = F_{2n} + F_{2n-1} \geq (\sqrt{2})^{2n-2} + (\sqrt{2})^{2n-3} =(\sqrt{2})^{2n-1} \left( \frac{1}{\sqrt{2}} + \frac12\right) >(\sqrt{2})^{2n-1} $$

And now the second clause, making use of what we just proved about $F_{2n+1}$: $$F_{2n+2} = F_{2n+1} + F_{2n} \geq (\sqrt{2})^{2n} + (\sqrt{2})^{2n-1} =(\sqrt{2})^{2n} \left( 1+ \frac{1}{\sqrt{2}} \right) >(\sqrt{2})^{2n} $$ So we have proven both clauses of the logical and, thus the and of these is proven, thus induction is established.

The easy way might have been to use the closed form expression for $F_n$, of course.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.