Thread: Recurrence Relations

I am asked to solve the following recurrence relations...that is find a closed form for them. I am supposed to do this using "back substitution"

a) a sub n = 4a sub n-1 + 5 for all n > 0 and a sub 0 = 2.

b) b sub n = b sub n-1 + n^2 for all n > 0 and b sub 0 = 3.

Any suggestions?? Thank you.

Originally Posted by jzellt

a) a sub n = 4a sub n-1 + 5 for all n > 0 and a sub 0 = 2.

We need to "massage" this problem a little first:
$\displaystyle a_n = 4a_{n - 1} + 5$

$\displaystyle a_n - 4a_{n - 1} = 5$

This implies that
$\displaystyle a_{n + 1} - 4a_n = 5$

Thus
$\displaystyle (a_{n + 1} - 4a_n) - (a_n - 4a_{n - 1}) = 0$

$\displaystyle a_{n + 1} - 5a_n + 4a_{n - 1} = 0$

Finally:
$\displaystyle a_{n + 2} - 5a_{n + 1} + 4a_n = 0$

Solve the characteristic equation:
$\displaystyle m^2 - 5m + 4 = 0$

$\displaystyle (m - 4)(m - 1) = 0$

$\displaystyle m = 1, 4$

Thus the solution is of the form:
$\displaystyle a_n = A \cdot 4^n + B \cdot 1^n$

$\displaystyle a_n = A \cdot 4^n + B$

Your initial condition states: $\displaystyle a_0 = 2$. So
$\displaystyle a_0 = A \cdot 4^0 + B = 2$

$\displaystyle A + B = 2$

$\displaystyle B = 2 - A$

Thus
$\displaystyle a_n = A \cdot 4^n + (2 - A)$

So we see that there is no unique solution here.

You try the other one.

-Dan