Use recursion to prove the bounds of the Fibonacci numbers when $n\geq 2$

Question

Use recursion and the following function fib (for the computation of a Fibonacchi number):

def fib(n):
  if n <2:
    return 1
  else:
    return fib(n-1) + fib(n-2)

To prove that $2^n\geq F_n\geq 2^\frac{n}{2}$ when $n\geq 2$ and $n$ is an integer.

The key here is that I'm supposed to "use recursion" to accomplish this proof. However, I'm confused by this and am uncertain as to how I should be using recursion to prove that those values are bounds for the Fibonacci numbers when $n\geq 2$. How would I do this? Thank you.

Answer 1

Use induction...

$n=2$: $2^2\ge2\ge2^{\frac 22}$

Assume true for $k\le n$..

$n+1$: $ F_{n+1}=F_n+F_{n-1}$ So $$2^{n+1}\gt3(2^{n-1})=2^n+2^{n-1}\ge F_{n+1}\ge2^{\frac n2}+2^{\frac {n-1}2}=2^{\frac {n-1}2}(2^{\frac12}+1).\ge2^{\frac {n-1}2}\cdot2=2^{\frac {n+1}2}$$........

Answer 2

Using recursion means that you need to use the recursive definition of $F_n$, that is the given code. The proof itself is just a variant of strong induction: you need to prove two base cases, because the next $k$-inequality uses the previous two inequalities.

This is easy to see for $n=2$ and $n=3$.

Suppose the inequalities are true for all $2\leq k \leq n+1$. Then use that $F_{n+2}=F_{n+1}+F_n$ and sum the two inequalities $2^{n+1}\geq F_{n+1}\geq 2^\frac{n+1}{2}$ and $2^n\geq F_n\geq 2^\frac{n}{2}$ to obtain $$2^{n+2}=4\cdot 2^n\geq3\cdot 2^n =2^n+2^{n+1}\geq F_{n+2}\geq 2^\frac{n}{2}+2^\frac{n+1}{2}=(1+\sqrt{2})2^\frac{n}{2}\geq 2\cdot 2^\frac{n}{2}= 2^\frac{n+2}{2}$$

Answer 3

Lower bound.

Suppose $F_n > a^n$ and $F_{n+1} > a^{n+1}$. We want to see what condition on $a$ will imply $F_{n+2} > a^{n+2}$.

$F_{n+2} =F_{n+1}+F_n \gt a^{n+1}+a^n =a^n(a+1) $. This is $\gt a^{n+2}$ if $a^n(a+1) > a^{n+2}$ or $a+1 > a^2 $ or $\frac54 > a^2-a+\frac14 =(a-\frac12)^2 $ or $a < \frac{\sqrt{5}}{2}+\frac12 \approx 1.618 $.

Since $\sqrt{2} \approx 1.414 \lt 1.618$, using $a = \sqrt{2}$ and $(\sqrt{2})^n =2^{n/2} $ gives the lower bound once we have shown it for two consecutive $F_n$.

This is almost exactly the same for the upper bound.

Suppose $F_n < a^n$ and $F_{n+1} < a^{n+1}$. We want to see what condition on $a$ will imply $F_{n+2} < a^{n+2}$.

Doing exectly the same analysis, we find that the condition is $a > \frac{\sqrt{5}}{2}+\frac12 \approx 1.618 $.

Since $2 > 1.618$, this gives the upper bound.

All that is left is to show that the bounds hold for two consecutive $F_n$.

To analytically show the inequalities:

$\begin{array}\\ \sqrt{2} < \frac{\sqrt{5}}{2}+\frac12\\ \iff 2\sqrt{2} < \sqrt{5}+1\\ \iff 8 < (\sqrt{5}+1)^2 =6+2\sqrt{5}\\ \iff 1 < \sqrt{5}\\ \text{which is true.}\\ \end{array} $

$\begin{array}\\ 2 > \frac{\sqrt{5}}{2}+\frac12\\ \iff 3 > \sqrt{5}\\ \iff 9 > 5\\ \text{which is true.}\\ \end{array} $