6

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.

1111111
  • 83

3 Answers3

5

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}$$

achille hui
  • 122,701
  • Thanks for the detailed solution. Your solution I guess essentially is the same as the fixed point solution suggested by @Did. But since I like the fixed point theory more than the eigen value solution I vote his. Again thanks. – 1111111 May 17 '14 at 14:16
4

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}. $$

Did
  • 279,727
  • Deal! $b_{n+1}=2b_n$ with $b_1=-1$. – 1111111 May 17 '14 at 14:14
  • Yep! Hence $b_n$ converges to $___$, which implies that $a_n$ converges to $___$. Well done. – Did May 17 '14 at 14:15
  • Fixed points here map to eigenvectors in my approach. Distinct fixed points means two independent eigenvectors, which means the matrix is diagonalizable, and the recursion has a nice solution. Fun. – robjohn May 18 '14 at 17:30
1

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} $$

robjohn
  • 345,667