Necesito un límite inferior exponencial simple para la recencia de Fibonacci

Question

$f(1) = f(2) = 1$ y $f(n) = f(n-1)+f(n-2)$

Estaba pensando en esto pero no estoy seguro de que sea correcto:

$f(n) = f(n-1)+f(n-2) = f(n-2)+f(n-3) + f(n-2)$

ya que el caso base es 1, entonces $f(n-3) \geq 1$ por lo que tenemos que

$f(n) \geq 2f(n-2)$

aplicando la misma lógica para $f(n-2)$ obtenemos lo siguiente:

$f(n) \geq 2f(n-2) \geq 4f(n-4) \geq ... \geq 2^{k}f(n-2k)$

¿cuándo nos detenemos? Cuando $n-2k = 1$ o $n-2k = 2$ por lo que tenemos:

$f(n) \geq 2^{\frac{n-2}{2}}$

pero siento que me falta algo... al menos veo que esto se mantiene asintóticamente, pero no estoy seguro para qué $n$ ¿es correcta la última desigualdad?

Answer 1

Tienes razón. También puedes justificar esa desigualdad por inducción. En primer lugar, $f(1)=1\geqslant2^{-\frac12}$ y $f(2)=1\geqslant2^0$ . Por otro lado. \begin{align}f(n+1)&=f(n)+f(n-1)\\&\geqslant2^{\frac{n-2}2}+2^{\frac{n-3}2}\\&=2^\frac12\times2^{\frac{n-3}2}+2^{\frac{n-3}2}\\&\geqslant2^\frac12\times2^{\frac{n-3}2}+2^\frac12\times2^{\frac{n-3}2}\\&=2\times2^\frac12\times2^{\frac{n-3}2}\\&=2^\frac n2\\&\geqslant2^\frac{n-1}2.\end{align}