Proving an exponential bound for a recursively defined function I am working on a function that is defined by
$$a_1=1, a_2=2, a_3=3, a_n=a_{n-2}+a_{n-3}$$
Here are the first few values:
$$\{1,1,2,3,3,5,6,8,11,\ldots\}$$
I am trying to find a good approximation for $a_n$. Therefore I tried to let Mathematica diagonalize the problem,it seems to have a closed form but mathematica doesn't like it and everytime I simplify it gives:
a_n = Root[-1 - #1 + #1^3 &, 1]^n Root[-5 + 27 #1 - 46 #1^2 + 23 #1^3 &, 1] + 
 Root[-1 - #1 + #1^3 &, 3]^n Root[-5 + 27 #1 - 46 #1^2 + 23 #1^3 &, 2] + 
 Root[-1 - #1 + #1^3 &, 2]^n Root[-5 + 27 #1 - 46 #1^2 + 23 #1^3 &, 3]

I used this to get a numerical approximation of the biggest root: $$\text{Root}\left[x^3-x-1,1\right]=\frac{1}{3} \sqrt[3]{\frac{27}{2}-\frac{3 \sqrt{69}}{2}}+\frac{\sqrt[3]{\frac{1}{2}
   \left(9+\sqrt{69}\right)}}{3^{2/3}}\approx1.325$$
Looking at the function I set 
$$g(n)=1.325^n$$
and plotted the first 100 values of $\ln(g),\ln(a)$ ($a_n=:a(n)$) in a graph (blue = $a$, red = $g$):

It seems to fit quite nicely, but now my question:
How can I show that $a \in \mathcal{O}(g)$, if possible without using the closed form but just the recursion. If there would be some bound for $f$ thats slightly worse than my $g$ but easier to show to be correct I would be fine with that too.

It might not be exactly what you are asking for but you can dominate the series by a rough exponential estimate without finding any closed forms like so:
Given $$a_n = a_{n-2} + a_{n-3} = a_{n-3} + a_{n-4} + a_{n-5}$$ it can be seen the sequence is increasing (i.e. $a_{n-1} < a_n$) when $0 < a_{n-5}$, which holds when $n > 5$ and it can be checked directly that we can strengthen this to $n \ge 5$.
This implies that $$a_n < 3 a_{n-3}$$ and on this basis split the sequence into three parts:


*

*$b_n = a_{3n}$

*$b'_n = a_{3n+1}$

*$b''_n = a_{3n+2}$


which are all smaller than $3^n$ for $n \ge 2$ by induction, we find then (by dividing $n$ by $3$) that for $n \ge 4$:
$$a_n < \sqrt[3]{3}^n.$$
which is roughly $1.442\ldots$
P.S. Thanks to Srivatsan for the idea behind this estimate!
