I'm currently stuck with the following problem. How do I calculate the order of growth of the following sequence:
$f_{n} = 2f_{n-1} + f_{n-2}$
Assuming that
$f_{0} =1$ and $f_{1} = 1$
I've got the following hints: they used $(1- 2x - x^2) = (1-Ax)(1-Bx) $ to get the roots of the solution.
How do I get from the squence to $(1-2x-x^2)$ and why do I have to equal it to $(1-Ax)(1-Bx)$
Somehow the solution is $(1+\sqrt{2})^n$
Thanks for your help community
Process 1:
Start with $1-2x-x^2$. Now, the given, from the problem, is that \begin{align} 1-2x-x^2 &= (1- a x)(1 - b x) \\ &= 1 -(a+b) x + ab x^2. \end{align} Equating coefficients leads to $a + b = 2$ and $ab = -1$. Using this information leads to \begin{align} a - \frac{1}{a} &= 2 \\ a^2 - 2 a - 1 &= 0 \\ a &= 1 \pm \sqrt{2}. \end{align} By choosing $a = 1 + \sqrt{2}$ then $b$ becomes $b = 1 - \sqrt{2}$. Since $f_{n}$ increases with $n$ then consider a solution of the form $$f_{n} = A \, (1+\sqrt{2})^{n} + B \, (1-\sqrt{2})^{n}$$ With $f_{0} = 1$ and $f_{1} = 1$, then it can be found that $A = B = \frac{1}{2}$ and $$f_{n} = \frac{1}{2} \, \left[ (1+\sqrt{2})^{n} + (1-\sqrt{2})^{n} \right].$$
Now, in terms of growth of $f_{n}$, the following is noticed. It can be determined that $0 \leq 1-\sqrt{2} \leq -1$ and $3 \leq 1 + \sqrt{2} \geq 1$. Taking powers of these values leads to $|(1-\sqrt{2})^{n}| \to 0$ as $n \to \infty$ and $(1+\sqrt{2})^{n} \to \infty$. This leads to $$f_{n} \approx (1+\sqrt{2})^{n} $$ as $n \to \infty$.