Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$):

enter image description here

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.

share|improve this question
add comment

4 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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
1  
@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
add comment

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

share|improve this answer
add comment

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!

share|improve this answer
1  
This is neat, thank you :) –  Listing Nov 29 '11 at 7:30
add comment

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}$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.