Order of growth of sequence $f_{n} = 2f_{n-1} + f_{n-2}$ 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
 A: 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$.   
