Characteristic equation solution to recurrence problem

Printable View

August 27th 2009, 03:45 AM
RobinShurst

Characteristic equation solution to recurrence problem

Hi!

So, I remember once being able to do this.. I'll start with a demo, we want to find a recurrence relationship for the formula

$x_{n}=x_{n-1} + x_{n-2}$

Which is the Fib. seq. if we say :

$x_0 = x_1 = 1$

So, what I remember is (and this seems right from googling) replace the time series with a power series ( $x_n$ -> $y^n$ ) and solve to find roots, I suppose this is a poor man's z-transform; although if someone can explain this in more details that'd be lovely...

So...

$y^2 - y - 1 = 0$

With the golden ratio, for a root ->

$y = \frac{\sqrt{5}}{2} \pm \frac{1}{2}$

So then (I'm getting hazy here)

We bang these two roots into a formula for the recurrence

$x_n = A[\frac{\sqrt{5} + 1}{2}]^n + B[\frac{\sqrt{5} - 1}{2}]^n$

Why? Where did that come from.. i forget.

Then solve by subbing the Fib initial conds...

$x_0 = A + B$

etc.

This is left as an exercise to the reader (not really)

Ok. So my question is, I want to work out payments on a mortgage, I thought easy, I remember how to do recurrence relations. Wrong. There is a page that shows you how to do this for payment after interest is accrued, but not before... I'm so dumb I can't even retask that solution for myself....

So:

$P_{t+1} = (P_{t} - M)(\frac{r}{12} + 1)$

Defining P{t} as the amount I owe at the beginning of the month t
M as the amount I pay
r as the interest per year so r/12 per month

I pay my payment at the beginning of the month and interest accrues over the month.

Can you try and show me how to tackle this in the the same way as the Fib series? I know it's order 1 not 2... I just don't know how to get it right.
August 27th 2009, 09:40 PM
integerfan

Recurrence relation with 2 parameters

so far i have seen all the recurrence relations(RR) similar to
F(n)= F(n-1)+F(n-2) .....the Fibonacci sequence

and they can be nonhomogeneous or of higher order.

but is there any method to solve equations like this
S(m,n)= S(m-1,n-1)+S(m,n-2)

i arrived at a RR similar to above when solving a 2 dimensional problem.
(Doh) observe that S(m,n) need not be the same as S(n,m).
August 28th 2009, 12:37 AM
RobinShurst

A solution

There are of course many ways to skin a cat...

I solved the problem another way so I'll offer it here for completeness... If anyone knows the characteristic equation solution I'd still be happy to hear it.

We know:

$P_1 = (P_0 - M)(\frac{r}{12} + 1) = P_0(\frac{r}{12} + 1) - M(\frac{r}{12}+1)$

Hence:

$P_2 = ([P_0(\frac{r}{12} + 1) - M(\frac{r}{12}+1)] - M)(\frac{r}{12} + 1) = P_0(\frac{r}{12} + 1)^2 - M(\frac{r}{12}+1)^2 - M(\frac{r}{12}+1)$

Which will become a geometric series in addition to the $P_0$ term.

So a sum to n terms and the $P_0$ term yield:

$P_n = P_0(\frac{r}{12}+1)^n + 12\frac{M(\frac{r}{12} + 1)(1-(\frac{r}{12} + 1)^n)}{r}$

As you remember, this was a mortgage repayment question, so $P_{term} = 0$

By making M the subject this gives the repayment.