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

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?

-
Why not just use the method of undetermined coefficients? The general solution of the homogeneous equation $b_m=0.8b_{m-1}$ is $b_m=C(0.8)^m$; the nonhomogeneous equation has a particular solution $b_m=0.5$; so the general solution of the nonhomogeneous equation is $b_m=0.5+C(0.8)^m$. From the initial value $b_1=0.1$ we get $C=-0.5$. – bof May 6 '14 at 3:47
@bof: Yeah, that's even better. I didn't think of undetermined coefficients. I haven't had a course in discrete mathematics yet, that's why that I don't know much about how these problems are typically solved. – math.n00b May 6 '14 at 4:00
But you've had a course in differential equations, right? The methods are quite similar. In fact, a linear recurrence for the sequence $b_m$ can be transformed into a linear differential equation for the exponential generating function $$y(t)= \sum_{m=0}^\infty b_m t^m/m!.$$ – bof May 6 '14 at 4:06
@bof: Not yet! I'm a first year student. I'll probably take a course in ODE's next semester. – math.n00b May 6 '14 at 4:29

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

-

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

-

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.

-

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

-

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

-