A non-homogenous linear recurrence: Why does my method fail?

Question

I'm trying to solve this recurrence relation:

$$a_m = 8 \cdot a_{m-1} + 10^{m-1}, a_1=1$$

By the change of variable $\displaystyle b_m = \frac{a_m}{10^m}$ I obtained this linear non-homogenous relation:

$$b_m = \frac{8}{10}b_{m-1} + \frac{1}{10}, b_1 = \frac{1}{10}$$

Now I'm trying to solve this one. Since it's non-homogenous because of a constant, I thought maybe it was a good idea to use linear algebra by writing this recurrence relation in this matrix form:

$$\begin{bmatrix} b_m \\ b_{m-1} \end{bmatrix} = \begin{bmatrix} \frac{1}{10} & \frac{8}{10}\\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ b_{m-1} \end{bmatrix}$$

So, If we set $A=\begin{bmatrix} \frac{1}{10} & \frac{8}{10}\\ 0 & 1 \end{bmatrix}$, my recurrence relation can be written like this:

$$\begin{bmatrix} b_m \\ b_{m-1} \end{bmatrix} = A^m \begin{bmatrix} 1 \\ a_1 \end{bmatrix} = A^m \begin{bmatrix} 1 \\ \frac{1}{10} \end{bmatrix}$$

The problem arises when I want to calculate the eigenvalues and eigenvectors of $A$ to find $A^m$. It involves square roots and stuff and apparently they don't get canceled. Another problem is that if I write the same recurrence relation in the following way my calculations TOTALLY changes, I mean eigenvalues change, so, eigenvectors will change too, and it seems like a totally different problem:

$$\begin{bmatrix} b_m \\ b_{m-1} \end{bmatrix} = \begin{bmatrix} \frac{8}{10} & \frac{1}{10}\\ 1 & 0 \end{bmatrix} \begin{bmatrix} b_{m-1} \\ 1 \end{bmatrix}$$

Using wolfram alpha I know the exact form for $b_m$:

$$b_m = \frac{1}{2} ( 1 - (\frac{4}{5})^m ) $$

Which agrees with what I expect.

Is there something wrong with my method that such complications arise?

Answer 1

Your method fails because

$$ A \left[ \begin{matrix} b_m \\ b_{m-1} \end{matrix} \right]$$

isn't anything useful.

Instead, try setting up a matrix such that

$$ \left[ \begin{matrix} 1 \\ b_{m} \end{matrix} \right] = A \left[ \begin{matrix} 1 \\ b_{m-1} \end{matrix} \right]$$

so that repeated application of $A$ does give you something useful.

---

Addendum: it is even possible to skip the change of variable, by using

$$ \left[ \begin{matrix} 10^m \\ a_m \end{matrix} \right] = \left[ \begin{matrix} 10 & 0 \\ 1 & 8 \end{matrix} \right] \left[ \begin{matrix} 10^{m-1} \\ a_{m-1} \end{matrix} \right]$$

Answer 2

Your method fails because you can't exponentiate $A$ as you did; the output of one step is not the input to the next one. You want instead something of this form:$$\begin{bmatrix} b_m \\ b_{m-1} \end{bmatrix}=A\begin{bmatrix} b_{m-1} \\ b_{m-2} \end{bmatrix}$$

Answer 3

From $b_m = \frac{8}{10}b_{m-1}+\frac{1}{10}$, we have $10b_m = 8b_{m-1}+1$. Shift the index to get $10b_{m+1} = 8b_m+1$. Subtract to get $10b_{m+1}-10b_{m} = 8b_m-8b_{m-1}$ or $10b_{m+1} = 18b_m-8b_{m-1}$ or $5b_{m+1} = 9b_m-4b_{m-1}$. Then use the characteristic polynomial and the initial condition to get a closed form of $b_m$.

Answer 4

I agree with your first equation with A but not the equation with A^m. Your approach would work if your first equation related (b_m, b_m-1) with (b_m-1, b_m-2) but it doesn't.

A simple way to solve this is to let b_m = c_m + k and substitute in into the recursion for b_m to get= .

c_m = . 8 c_m-1 + .8 k + 1,

so that if we let k = - 1/8 then the recursion for c_m is simple, so c_m can be found and then the original a_m.

Answer 5

Just looking at the recurrence, it's solution has to be of the form $a_n = c_1 8^n + c_2 10^n$... plugging that in and fiddling with the constants should be enough to get a solution.

OK, whip out generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence without subtraction in indices: $$ a_{n + 1} = 8 a_n + 10^n $$ Multiply by $z^n$, sum over $n \ge 0$, recognize the resulting sums: $$ \frac{A(z) - a_0}{z} = 8 A(z) + \frac{1}{1 - 10 z} $$ Replace $a_0 = 0$ (run the recurrence backwards from $a_1 = 1$), solve for $A(z)$, write as partial fractions: $$ A(z) = \frac{1}{2} \cdot \frac{1}{1 - 10 z} - \frac{1}{2} \cdot \frac{1}{1 - 8 z} $$ As the above are just two geometric series, you see directly that: $$ a_n = \frac{10^n - 8^n}{2} $$