<s>[INST] Upper bound $f(n) \leq c\alpha^n$ with recurrence $f(n) = 2 \cdot f(n-1) + f(n-2)$ with $f(1) = 1$ and $f(2) = 2$ I have following recurrence: $f(n) = 2 \cdot f(n-1) + f(n-2)$ with $f(1) = 1$ and $f(2) = 2$.
How can I find an upper bound with the form $f(n) \leq c\alpha^n$?
I know that in this task the value of $c$ does not have to be determined. 
 [/INST] As it was suggested in the comments, there is a technique to solve this type of problems (here is an example, you will find a lot more on MSE). By noting $a_n=f(n)$, we have a homogeneous recurrence
$$a_{n}=2a_{n-1}+a_{n-2}$$
which can be solved using characteristic polynomial technique. In this case, the polynomial is
$$x^2-2x-1=0$$
It has $1-\sqrt{2}$ and $1+\sqrt{2}$ as solutions, thus the general term of the recurrence is
$$a_n=A(1-\sqrt{2})^n+B(1+\sqrt{2})^n \tag{1}$$
Given initial conditions $a_1=1, a_2=2$ we have
$$1=A(1-\sqrt{2})+B(1+\sqrt{2})$$
$$2=A(1-\sqrt{2})^2+B(1+\sqrt{2})^2$$
leading to $A=-\frac{\sqrt{2}}{4}$ and $B=\frac{\sqrt{2}}{4}$
or
$$a_n=\frac{\sqrt{2}}{4}\left(1+\sqrt{2}\right)^n-\frac{\sqrt{2}}{4}\left(1-\sqrt{2}\right)^n \tag{2}$$
As a result
$$f(n)<\frac{\sqrt{2}}{2}\left(1+\sqrt{2}\right)^n$$
because $|1-\sqrt{2}|<1$ and $\left(1-\sqrt{2}\right)^n \rightarrow 0$ when $n\rightarrow\infty$.
</s>