Prove $\ a_{n}<2^{n} $ for every natural number n, where $\ a_{n} $ is defined recursively by $$ a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$$ Once I get the explicit equation, proving this would be easy with induction, however I'm having trouble finding it. I can't find the connection between these guys $\ a_{4}=6, a_{5}=11, a_{6}=20, a_{7}=37 $.
Does anyone have ideas?
On
To estimate $a_n$ where $a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$, suppose $a_k < c^k$ for $k < n$.
Then $a_n < c^{n-1}+c^{n-2}+c^{n-3} = c^n(1/c+1/c^2+1/c^3)$ and $a_n < c^n$ if $1/c+1/c^2+1/c^3 < 1$. Since this is true for $c=2$, this proves the result, and shows that a smaller $c$ can be used, up to where $1/c+1/c^2+1/c^3 = 1$ (which has a root at $c_0 \sim 1.8393$).
We can similarly establish an lower bound of the form $a_n > b c^n$ like this:
Suppose $a_k > bc^k$ for $k < n$. (The purpose of the additional variable $b$ is to allow the initial inequality to be established.)
Then $a_n > b(c^{n-1}+c^{n-2}+c^{n-3}) = b c^n(1/c+1/c^2+1/c^3)$ and $a_n > bc^n$ if $1/c+1/c^2+1/c^3 > 1$. Since this is true for $c=1.8 < c_0$, this proves the result, and shows that any $c$ less than $c_0$ can be used.
This is just a way of discovering that the $a_n$ grow like $c_0^n$.
Look up generating functions for limear recurrences and the valuable and free book Generatingfunctionology from http://www.math.upenn.edu/~wilf/DownldGF.html.
You should use induction right on the recursion. We get $$a_n<2^{n-1}+2^{n-2}+2^{n-3}=2^{n-3}(5)<2^{n-3}(8)=2^n$$
The only good way to find an explicit formula would be to use generating functions. See this: http://en.wikipedia.org/wiki/Generating_function