# how to work out a closed form of a sequence

Consider the following linear recurrence sequence.

$x_1 = 11$, $x_{n+1} = -0.8x_n + 9,\quad n = 1,2,3, \ldots.$

Find a closed form for this sequence.

-
What did you try? – Davide Giraudo Feb 1 '12 at 18:59
en.wikipedia.org/wiki/… – yoyo Feb 1 '12 at 19:05
You should really try to write out the first few terms and see what happens if you have nowhere to go. – Patrick Da Silva Feb 1 '12 at 19:08

To get an idea of what the closed form might look like, let's iterate the relation a few times: \begin{align} x_n &=9-.8x_{n-1}\\ &=9-.8(9-.8x_{n-2})\\ &=9-.8\cdot9+.8^2x_{n-2}\\ &=9-.8\cdot9+.8^2(9-.8x_{n-3})\\ &=9-.8\cdot9+.8^2\cdot9-.8^3x_{n-3}\tag{1} \end{align} Looking at $(1)$, it appears that $$x_n=9\frac{1-(-.8)^k}{1+.8}+(-.8)^kx_{n-k}\tag{2}$$ Equation $(2)$ can be verified using induction.

Verification: The case $k=1$ is just the given recursion: $x_n=9-.8x_{n-1}$.

Suppose $(2)$ is true for some $k$, then \begin{align} x_n &=9\frac{1-(-.8)^k}{1+.8}+(-.8)^kx_{n-k}\\ &=9\frac{1-(-.8)^k}{1+.8}+(-.8)^k(9-.8x_{n-k-1})\\ &=9\frac{1-(-.8)^k}{1+.8}+9(-.8)^k+(-.8)^{k+1}x_{n-k-1}\\ &=9\frac{1-(-.8)^{k+1}}{1+.8}+(-.8)^{k+1}x_{n-k-1}\\ \end{align} So $(2)$ is true for $k+1$.

Using $x_1=11$ and $k=n-1$, $(2)$ becomes \begin{align} x_n &=5(1-(-.8)^{n-1})+(-.8)^{n-1}11\\ &=5+6(-.8)^{n-1}\tag{3} \end{align}

-

$x_{n+1}+a=-0.8(x_n+a)$

if a=-5, this equation is equivalent to $x_{n+1}=-0.8x_n+9$

then we obtain:

$x_n-5=(-0.8)^{n-1}(x_1-5)$

Thus:

$x_n=5+6(-0.8)^{n-1}$

-

Use generating functions. Define $X(z) = \sum_{n \ge 0} x_{n + 1} z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get: $$\frac{X(z) - x_1}{z} = - \frac{4 X(z)}{5} + \frac{9}{1 - z}$$ Thus: $$X(z) = \frac{55 - 10 z}{5 - z - 4 z^2} = 5 \cdot \frac{1}{1 - z} + 6 \cdot \frac{1}{1 + 4 z / 5}$$ Two geometric series: $$x_{n + 1} = 5 + 6 \cdot (-0.8)^n$$

-