Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 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 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 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 at 4:29

5 Answers 5

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.