A sequence $(a_n)_{nβ₯0}$ in $R$ satisfies $6π_π = a_{n-2} + a_{n-1},$ where $ π_0 =-1$ $ π_1 = -1$
Determine the asymptotic growth of $(a_n)_{nβ₯0}$.
My question is: Should we first solve this recurrence and then find the asymptotic growth? I am familiar with the asymptotic growth functions and recurrences but I am not sure how to start this problem..
Any hint or idea would be much appreciated.
$\endgroup$2 Answers
$\begingroup$Recurrence sequences have a lot in common with linear differential equations. Here we have the analogous differential equation$$ 6y'' - y' - y = 0, $$$y'(0) = -1$, $y(0) = -1$. Characteristic equation is $6\lambda^2 - \lambda - 1 = 0$, $\lambda = \frac{1}{2}, -\frac{1}{3}$. So the solution is $y = C_1 e^{\frac{1}{2}t} + C_2 e^{-\frac{1}{3}t}$. From the condition we obtain $C_1 = -\frac{8}{5}$ and $C_2 = \frac{3}{5}$. Now it's obvious that the asymptotic behaviour is close to $-\frac{8}{5}e^{\frac{1}{2}t}$ (or $-\frac{8}{5}e^{\frac{1}{2}n}$) since the second summand tends to zero.
$\endgroup$ 2 $\begingroup$This recurrence relation can be written as$$\begin{pmatrix} a_{n-1} \\ a_n \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ \frac{1}{6} & \frac{1}{6}\end{pmatrix}\begin{pmatrix} a_{n-2} \\ a_{n-1}\end{pmatrix}.$$Hence, by induction,$$\begin{pmatrix} a_{n-1} \\ a_n \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ \frac{1}{6} & \frac{1}{6}\end{pmatrix}^{n-1}\begin{pmatrix} a_0 \\ a_1\end{pmatrix}.$$Computing the eigendecomposition of $A := \begin{pmatrix} 0 & 1 \\ \frac{1}{6} & \frac{1}{6}\end{pmatrix}$ will give you the asymptotic growth of $(a_n)_{n \in \mathbb{N}}$. Usually it will be determined by the largest eigenvalue of $A$ unless you exactly hit the eigenvector of the lower eigenvalue or the eigenvalues are equal in size.
$\endgroup$ 1
