I am working on the following problem:
Define $\{a_n\}$ where $a_0=0$, $a_1=1$, and $a_n=A\cdot a_{n-1}+B\cdot a_{n-2}$ for all $n\geq 2$ where $A,B\in\mathbb{R}$. Find a constant $M$ such that $a_n\leq M^n$ for all $n\geq 0$.
And I'm sure there are many bounds we can use, however, I want to try to find the best one I can.
I didn't know how to approach this directly (so please let me know if you have a better approach), so instead I tried to find a closed form for $a_n=A\cdot a_{n-1}+B\cdot a_{n-2}$.
I guessed a solution of the form $a_n=c\lambda^n$ for some $\lambda\in\mathbb{R}$. Then I substituted this solution into the recurrence relation to get the characteristic equation $$\lambda^2-A\lambda-B=0$$ and using the quadratic formula I got $$\lambda=\frac{A\pm\sqrt{A^2+4B}}{2}$$
Now I considered three cases:
If $A^2+4B=0$ then $$a_n=\frac{2n}{A}\left(\frac{A}{2}\right)^n=n\left(\frac{A}{2}\right)^{n-1}$$
If $A^2+4B>0$ then $$a_n=\frac{1}{\sqrt{A^2+4B}}\left(\frac{A+\sqrt{A^2+4B}}{2}\right)^n-\frac{1}{\sqrt{A^2+4B}}\left(\frac{A-\sqrt{A^2+4B}}{2}\right)^n$$
If $A^2+4B<0$ then $$a_n=\left(\frac{2A\left(\sqrt{-B}\right)^n}{\sqrt{-A^2(A^2+4B)}}\right)\sin\left(\arctan\left(\frac{\sqrt{-(A^2+4B)}}{A}\right)n\right)$$
So now I believe that my problem reduces to bounding these three equations.
- For $a_n=\frac{2n}{A}\left(\frac{A}{2}\right)^n=n\left(\frac{A}{2}\right)^{n-1}$, I don't think we can find an $M$ such that $a_n\leq M^n$ for all $n\geq 0$ because $n\left(\frac{A}{2}\right)^{n-1}$ will eventually surpass $M^n$ for any $M$. Is this line of thinking correct? If so, how can I show no $M$ exists? I was thinking proof by contradiction?
- For $a_n=\frac{1}{\sqrt{A^2+4B}}\left(\frac{A+\sqrt{A^2+4B}}{2}\right)^n-\frac{1}{\sqrt{A^2+4B}}\left(\frac{A-\sqrt{A^2+4B}}{2}\right)^n$, I think picking $M=\frac{A+\sqrt{A^2+4B}}{2}$ should do the trick. I will try to prove it by induction later. Does my approach for this case sound plausible?
- For $a_n=\left(\frac{2A\left(\sqrt{-B}\right)^n}{\sqrt{-A^2(A^2+4B)}}\right)\sin\left(\arctan\left(\frac{\sqrt{-(A^2+4B)}}{A}\right)n\right)$, I know $-1\leq \sin(x)\leq 1$ so that means I need to look at $\frac{2A\left(\sqrt{-B}\right)^n}{\sqrt{-A^2(A^2+4B)}}$, but I am not too sure what $M$ value to pick here.
Also, I believe the above 3 cases hold for any real $A,B$ as long as $A\neq 0$. So the only case left is $A=0$ which reduces the recurrence to $a_n=B\cdot a_{n-2}$ and $$a_n\begin{cases}0 \quad \text{if } n=2k\\ B^{k} \quad \text{if }n=2k+1\end{cases}$$ So I think in this case we can pick $M=B$. Does my approach for this case sound plausible? Furthermore, with these 4 cases do I indeed cover all real numbers $A,B$?