Recurrence Relations

**jzellt** · March 19th 2008, 08:12 PM

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.

**topsquark** · March 19th 2008, 09:06 PM

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:
$a_n = 4a_{n - 1} + 5$

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

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

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

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

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

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

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

$m = 1, 4$

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

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

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

$A + B = 2$

$B = 2 - A$

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

So we see that there is no unique solution here.

You try the other one.

-Dan

Math Help - Recurrence Relations

LinkBack

Thread Tools

Display

Recurrence Relations

Similar Math Help Forum Discussions

Recurrence Relations

Recurrence relations

Recurrence relations

recurrence relations - degree of the recurrence

recurrence relations

Search Tags