2
$\begingroup$

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.

  • 0
    You should really try to write out the first few terms and see what happens if you have nowhere to go.2012-02-01

3 Answers 3

2

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

1

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

0

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 $