Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Question

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$.

Here are the first a few values of the series. Not sure if they are useful as they seem quite random to me. $$1,{7\over8},{3\over4},{13\over20},{7\over12},\dots$$

Thanks.

Answer 1

The sequence $(a_n)$ is iterating a homographic transformation hence a theorem which might be in your notes states that, when the two fixed points $\omega$ and $\omega'$ of the transformation are different, the reduced sequence $(b_n)$ defined by $$ b_n=\frac{a_n-\omega'}{a_n-\omega} $$ follows a simple recursion. Fixed points $\omega$ are such that, if $a_n=\omega$, then $a_{n+1}=\omega$ hence you might be able to identify them as $$ \omega=\frac12,\qquad \omega'=\frac54, $$ and I invite you to consider the reduced variable $$ b_n=\frac{4a_n-5}{2a_n-1}, $$ and to tell us what is $b_{n+1}$ in terms of $b_n$ and which asymptotics you can deduce from this observation. Deal?

Edit: To complete the last step, one can use the fact that $$ a_n=\frac{b_n-5}{2b_n-4}. $$

Answer 2

Let $p_n$, $q_n$ be two sequences to be determined such that $\displaystyle\;a_n = \frac{p_n}{q_n}\;$. In terms of $p_n$, $q_n$, the recurrence relation for $a_n$ can be rewritten as

$$a_{n+1} = \frac{2a_n+5}{-8a_n+16} \quad\iff\quad\frac{p_{n+1}}{q_{n+1}} = \frac{2p_n+5q_n}{-8p_n+16q_n}\tag{*1} $$ If we scale $p_n, q_n$ to make them satisfy the linear recurrence relation

$$\begin{bmatrix}p_{n+1}\\q_{n+1}\end{bmatrix} = \begin{bmatrix}2 & 5\\-8 & 16\end{bmatrix} \begin{bmatrix}p_{n}\\q_{n}\end{bmatrix} \tag{*2} $$ then any solution of $(*2)$ will lead to a solution of $(*1)$. It is easy to check the square matrix in $(*2)$ has eigenvalues $6$ and $12$ with corresponding eigenvectors $\begin{bmatrix}5\\4\end{bmatrix}$ and $\begin{bmatrix}1\\2\end{bmatrix}$. The general solution of $(*2)$ has the form:

$$ \begin{bmatrix}p_{n}\\q_{n}\end{bmatrix} = A \times 6^n \begin{bmatrix}5\\4\end{bmatrix} + B \times 12^n \begin{bmatrix}1\\2\end{bmatrix}$$ for suitable chosen constants $A$ and $B$. By inspection, we can reproduce $a_1 = 1$ by setting $A = \frac16$ and $B = \frac{1}{12}$. This leads to a solution of the original recurrence relation subject to $a_1 = 1$:

$$a_n = \frac{p_n}{q_n} = \frac{5 \times 6^{n-1} + 12^{n-1}}{4 \times 6^{n-1} + 2\times 12^{n-1}} = \frac{2^{n-1} + 5}{2^n + 4}$$

Answer 3

My answer is halfway between Did's answer and achille's answer. Both of their answers are very good, but perhaps there are some for whom this exposition is beneficial.

---

Solving the recursion for $a_{n+1}$ gives the linear fractional transformation $$ a_{n+1}=\frac{-2a_n-5}{8a_n-16}\tag{1} $$ One method of dealing with linear fractional transformations is via matrices and homogeneous coordinates:

Identify $\begin{bmatrix}x\\y\end{bmatrix}\simeq\dfrac xy$, and say $\begin{bmatrix}x\\y\end{bmatrix}\simeq\!\!\begin{bmatrix}u\\v\end{bmatrix}$ if $\,\dfrac xy=\dfrac uv$.

Now we can represent a linear fractional transformation as $$ \begin{bmatrix}a&b\\c&d\end{bmatrix}\begin{bmatrix}x\\1\end{bmatrix}\simeq\dfrac{ax+b}{cx+d}\tag{2} $$ Note that a diagonal matrix represents real multiplication by the ratio of the diagonal elements. Furthermore, multiplication of a matrix or vector by a scalar does not change the linear fractional transformation or the real number they represent.

Equation $(1)$ says that $$ \begin{bmatrix}a_{n+1}\\1\end{bmatrix}\simeq\begin{bmatrix}-2&-5\\8&-16\end{bmatrix}\begin{bmatrix}a_n\\1\end{bmatrix}\tag{3} $$ If we can find an invertible matrix $S$ and a diagonal matrix $D$ so that $$ \begin{bmatrix}-2&-5\\8&-16\end{bmatrix}=S^{-1}DS\tag{4} $$ then $(3)$ becomes $$ S\begin{bmatrix}a_{n+1}\\1\end{bmatrix}\simeq DS\begin{bmatrix}a_n\\1\end{bmatrix}\tag{5} $$ If we set $b_n\simeq S\begin{bmatrix}a_n\\1\end{bmatrix}$ and let $d$ be the ratio of the diagonal elements of $D$, $(5)$ says $$ b_n=d^{n-1}b_1\tag{6} $$ Then we can recover $a_n$ by $$ a_n\simeq S^{-1}\begin{bmatrix}d^{n-1}b_1\\1\end{bmatrix}\tag{7} $$

---

Computing $D$ and $S$: $$ \begin{bmatrix}-2&-5\\8&-16\end{bmatrix} =\frac16\begin{bmatrix}1&5\\2&4\end{bmatrix} \begin{bmatrix}-12&0\\0&-6\end{bmatrix} \begin{bmatrix}-4&5\\2&-1\end{bmatrix}\tag{8} $$ Thus, $d=\dfrac{-12}{-6}=2$ and $b_1\simeq S\begin{bmatrix}a_1\\1\end{bmatrix}\simeq\begin{bmatrix}-4&5\\2&-1\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}\simeq1$. Therefore, $$ a_n\simeq S^{-1}\begin{bmatrix}b_n\\1\end{bmatrix}\simeq\begin{bmatrix}1&5\vphantom{1^1}\\2&4\end{bmatrix}\begin{bmatrix}2^{n-1}\\1\end{bmatrix}\simeq\frac{2^{n-1}+5}{2^n+4}\tag{9} $$