Suppose $a_0 = 0$, $a_1 = 1$, and $$ a_{n+1} = a_n+2 a_{n-1}$$ if $n \ge 1$. Find $$\lim_{n\rightarrow\infty}\frac{a_{n+1}}{a_n}$$
Usually, what's the approach we use for recursive sequence like this?
I know another type of recursive question with no fraction involved,
but don't know how to do the type with fraction....
4 Answers
$\begingroup$Here’s a completely different approach. Divide the recurrence by $a_n$ to get
$$\frac{a_{n+1}}{a_n}=1+\frac{2a_{n-1}}{a_n}=1+\frac2{a_n/a_{n-1}}\;.\tag{1}$$
If we set $b_n=\dfrac{a_{n+1}}{a_n}$, we can rewrite $(1)$ as $$b_n=1+\frac2{b_{n-1}}\;.\tag{2}$$
Since $a_0=0$ and $a_1=1$, we can’t define $b_0$, but $a_2=a_1+2a_0=1$, so $b_1=\dfrac11=1$. Then $b_2=3$, $b_3=\frac53$, $b_4=\frac{11}5$, $b_5=\frac{21}{11}$, $b_6=\frac{43}{21}$, and $b_7=\frac{85}{43}$. This is enough to show a clear pattern: if $b_n=\frac{c_n}{d_n}$ in lowest terms, it appears that
$$c_{n+1}=2c_n+(-1)^{n+1}\tag{3}$$
and
$$d_{n+1}=c_n\;,\tag{4}$$
so that $$b_{n+1}=\frac{c_{n+1}}{d_{n+1}}=\frac{2c_n+(-1)^{n+1}}{c_n}=2-\frac{(-1)^n}{c_n}\;.\tag{5}$$
It’s not too hard to use $(2)$ to prove $(3)$ and $(4)$ by induction on $n$. $(3)$ and the fact that $c_1=1$ imply that $\langle c_n:n\in\Bbb Z^+\rangle$ is a strictly increasing sequence of positive integers, and $(5)$ then allows us to calculate $\lim\limits_{n\to\infty}b_n$ very easily.
$\endgroup$ $\begingroup$I’d use discrete calc to find a direct formula for $a_n$ in terms of just n and then do the limit.
$(E^2)a=(E)a+(2I)a$where $E$ is a shift operator and $I$ the identity. then you can solve for the eigenvalue for E
$(E^2-E-2I)a=0$which factors to$(E-2I)(E+I)a=0$
so $E=2I$ or $E=-1I$
if $E=bI$ where $b$ is a constant that means $a=c(b^n)$ where $c$ is a evaluated at $n=0$, but since there’s two solutions for $E$, we add the two corresponding solutions for $a$
so
$a_n=b(2)^n+c(-1)^n$
and to solve for $b$ and $c$ we just plug in the $n=0$ and $n=1$ values to make two linear equations and solve them.
It’s not too hard to show $b=1/3$ and $c=-1/3$so ultimately $a_n=((2)^n - (-1)^n)/3$and then you can compute the limit.
remember that the power of two will end up overwhelming the $(-1)^n$ so in the limit $a_n$ is approximately equal to $2^n/3$
$\endgroup$ 1 $\begingroup$Let $\lim\limits_{n\to \infty}\dfrac{a_{n+1}}{a_n}=l$. Now, $l=\lim\limits_{n\to \infty}\dfrac{a_{n+1}}{a_n}=1+\dfrac{2}{l}$. Thus $l^2=l+2$. The root of this equation gives the limit.
$\endgroup$ 4 $\begingroup$The recursion is linear, so you can express it as a $2\times2$ matrix with entries:
$a_{11}=1, a_{12}=2 , a_{21}=1 , a_{22}=0 $ , that maps the $2\times1$-vector ($a_n,a_{n+1}$) to the $2\times1$-vector ($a_{n+1},a_n$). Try diagonalizing the matrix to find a closed form for $a_n$
$\endgroup$ 1
