Límite superior de $f(n) \leq c\alpha^n$ con recurrencia $f(n) = 2 \cdot f(n-1) + f(n-2)$ $f(1) = 1$ y $f(2) = 2$

Question

Tengo la siguiente repetición: <span class="math-container">$f(n) = 2 \cdot f(n-1) + f(n-2)$</span> <span class="math-container">$f(1) = 1$</span> y <span class="math-container">$f(2) = 2$</span>.

¿Cómo puedo encontrar un límite superior con la forma <span class="math-container">$f(n) \leq c\alpha^n$</span>?

Sé que en esta tarea, el valor de <span class="math-container">$c$</span> no tiene que determinarse.

Answer 1

Como se sugirió en los comentarios, no es una técnica para resolver este tipo de problemas (aquí es un ejemplo, usted va a encontrar mucho más sobre el MSE). Observando $a_n=f(n)$, tenemos una recurrencia homogénea $$a_{n}=2a_{n-1}+a_{n-2}$$ que se puede resolver usando el polinomio característico de la técnica. En este caso, el polinomio es $$x^2-2x-1=0$$ Ha $1-\sqrt{2}$ e $1+\sqrt{2}$ como soluciones, por lo tanto el término general de la recurrencia es $$a_n=A(1-\sqrt{2})^n+B(1+\sqrt{2})^n \tag{1}$$ Dadas las condiciones iniciales $a_1=1, a_2=2$ hemos $$1=A(1-\sqrt{2})+B(1+\sqrt{2})$$ $$2=A(1-\sqrt{2})^2+B(1+\sqrt{2})^2$$ conduce a $A=-\frac{\sqrt{2}}{4}$ e $B=\frac{\sqrt{2}}{4}$ o $$a_n=\frac{\sqrt{2}}{4}\left(1+\sqrt{2}\right)^n-\frac{\sqrt{2}}{4}\left(1-\sqrt{2}\right)^n \tag{2}$$ Como resultado $$f(n)<\frac{\sqrt{2}}{2}\left(1+\sqrt{2}\right)^n$$ debido a $|1-\sqrt{2}|<1$ e $\left(1-\sqrt{2}\right)^n \rightarrow 0$ cuando $n\rightarrow\infty$.