The recurrence relation a is defined as follows. Sow that a $\in$ O $(2^n)$.
$a_0$ = 1
$a_1$ = 2
$a_n$ = 1 + $a_{n-1}$ + $a_{n-2}$
I am having trouble proving that this recurrence is true. I tried using n = 2 as the base case. $a_2$ = 4 once I replace the 2 for the n in the last condition. I then show that $2^2$ is also = 4 thus proving that a $\in$ O $(2^n)$. My only issue is that when I try using 3 the the answer to $a_3$ = 7 and $(2^3)$ = 8. Am I approaching this prove correctly? I also know for a fact that this recurrence is an increasing.
We'll show $a_n \le 2^n$ for all $n \ge 0$.
The base case is clear since $a_0 = 1 = 2^0$ and $a_1 = 2 = 2^1$.
Assume that for some $n \ge 1$ we have $a_k \le 2^k$ for all $k=0,1,\ldots, n$. We wish to show that $a_{n+1} \le 2^{n+1}$.
We have $$a_{n+1} = 1+a_n + a_{n-1} \le 1+2^n+2^{n-1} \le 2^{n-1}+2^n+2^{n-1} = 2^{n}+2^n = 2^{n+1}$$ which completes the proof.