# 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.

-

Induction would work.

Notice that the characteristic equation has a unique real positive root $\lambda \approx 1.325 \cdots$. We will show that $a_n = O(\lambda^n)$. Fix a constant $c > 0$ such that $a_n \leqslant c \lambda^n$ for $n \leqslant 3$; such a constant clearly exists. We will show that $a_n \leqslant c \lambda^n$ for all $n$.

Fix $n \geqslant 4$, and assume that $a_k \leqslant c \lambda^k$ for all $k < n$. Then we have \begin{align*} a_n &= a_{n-2} + a_{n-3} \\ &\leqslant c \lambda^{n-2} + c \lambda^{n-3} \\ &= c \lambda^{n-3} (\color{Purple}{\lambda+1}) \\ &= c \lambda^{n-3} \cdot \color{Purple}{\lambda^3} \\ &= c \lambda^n, \end{align*} where we have used the fact that $\lambda^3 = \lambda+1$. Thus the induction hypothesis is verified for $n$.

-
I didn't expect to see an answer so fast, thank you :-). By numerically solving the characteristic equation I easily see that there is an unique real positive root, do you mean this or is there a faster way to see that? –  Listing Nov 28 '11 at 23:32
@Listing, Sorry about being vague there. I removed that part for now. I will collect together my thoughts and say something later. –  Srivatsan Nov 28 '11 at 23:46

Your function $a_n$ is a classical recurrence relation. It is well-known that $$a_n = \sum_{i=1}^3 A_i \alpha_i^n,$$ where $\alpha_i$ are the roots of the equation $x^3 = x + 1$. You can find the coefficients $A_i$ by solving a system of linear equations. In your case, one of the roots is real, and the other two are complex conjugates whose norm is less than $1$, so their contribution to $a_n$ tends to $0$. So actually $$a_n = A_1 \alpha_1^n + o(1).$$ Mathematica diligently found for you the value of $A_1$, and this way you can obtain your estimate (including the leading constant).

-

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!

-
This is neat, thank you :) –  Listing Nov 29 '11 at 7:30

As another angle to approach things, note that once you have the characteristic equation it's easy to see that growth is exponential: we're looking for a root $x=\alpha$ of $f(x) = x^3-x-1=0$ and $f(1)\lt 0$ while $f(2)\gt 0$, so there's at least one root $\alpha\gt 1$, implying exponential growth by the usual theory of linear recurrences.

On the flip side, there's an even easier (if looser) exponential bound than QED's on the high end: $a_n\lt 2^n$ for $n\in\{1,2,3\}$, and assuming the inductive hypothesis we get \begin{align}a_n &= a_{n-2}+a_{n-3} \\ &\lt 2^{n-2}+2^{n-3} \\ &\lt 2^{n-2}+2^{n-2} \\ &= 2^{n-1} \\ &\lt 2^n.\end{align}

-