Finding recurrence formula containing $1/a_n$ with using generating function

Question

Actually I want to find formula $a_n$ from equation: $a_{n+1} = 1 / (3-a_n),a_0=5/2$

I called A(x)=$\sum_{n=0} a_{n}x^n$

It is easy to find $$\sum_{n=0} a_{n+1}x^n = \frac{\sum_{n=0} a_{n}x^n - a_0}{x} = \frac{A(x) - 5/2}{x}$$

However, what should I do to find this in terms of A(x) $$\sum_{n=0} \frac{1}{3-a_n}x^n$$

Answer 1

Hint: try to find two sequences $(b_n)_{n=0}^{\infty}, (c_n)_{n=0}^{\infty}$ of integers such that $a_n = \frac {b_n} {c_n}$ for any $n$. So, for example, $b_0=5$ and $c_0=2$; $b_1=2$ and $c_1=1$ as $a_1=2$. $a_{n+1} = 1 / (3-a_n)$ is then transforms to $$\frac {b_{n+1}}{c_{n+1}} = \frac 1 {3 - \frac {b_n}{c_n}} = \frac {c_n}{3c_n-b_n}.$$ Thus, $b_{n+1}=c_n \iff b_n=c_{n-1}$ and $c_{n+1}=3c_n-b_n=3c_n-c_{n-1}$. From this point on, you can use a generating function to find $c_n$.

Answer 2

A recurrence of the form:

$$ u_{n + 1} = \frac{a u_n + b}{c u_n + d} $$

is called a Ricatti recurrence (if $c = 0$ it is just a linear recurrence, if $a d = b c$ is it just $u_n = \text{constant}$). There are several ways to solve them, perhaps the simplest is due to Brand, "A Sequence Defined by a Difference Equation", American Mathematical Monthly 62:7, pp 489-492 (sep 1955). If we change variables to $y_n = c u_n + d$, we get:

$$ y_{n + 1} = \alpha - \frac{\beta}{y_n} $$

were $\alpha = a + d$, $\beta = a d - b c$.

Defining now $y_n = x_{n + 1} / x_n$ we get:

$$ x_{n + 2} - \alpha x_{n + 1} + \beta x_n = 0 $$

Solve this one, using e.g. $x_0 = 1$, $x_1 = y_0$ from the initial value, and substitute.

In your case, $a = 0, b = 1, c = -1, d = 3$, so $\alpha = 3, \beta = 1$, the auxiliary recurrence is:

$$ x_{n + 2} - 3 x_{n + 1} + x_n = 0 $$

Here we'd take $x_0 = 1, x_1 = 1/2$. The solution (courtesy of Maxima's solve_rec) is quite ugly:

$$ x_{n}={{\left(3-\sqrt{5}\right)^{n}\,\left(2\,\sqrt{5}+5\right)\,2 ^{-n-1}}\over{5}}-{{\left(\sqrt{5}+3\right)^{n}\,\left(2\,\sqrt{5}-5 \right)\,2^{-n-1}}\over{5}} $$

I'm too lazy to finish it off. The end result is of the form:

$$ a_n = \frac{a' \cdot r^n + b' \cdot s^n}{c' \cdot r^n + d' \cdot s^n} $$ for constants $a', b', c', d'$ and $r, s$ the ugly irrationals under powers above.