Thread: Characteristic equation solution to recurrence problem

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

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

Which is the Fib. seq. if we say :

$\displaystyle x_0 = x_1 = 1$

So, what I remember is (and this seems right from googling) replace the time series with a power series ($\displaystyle x_n$ -> $\displaystyle 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...

$\displaystyle y^2 - y - 1 = 0$

With the golden ratio, for a root ->

$\displaystyle 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

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

$\displaystyle 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:

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

2. 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.
observe that S(m,n) need not be the same as S(n,m).

3. 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:

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

Hence:

$\displaystyle 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 $\displaystyle P_0$ term.

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

$\displaystyle 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 $\displaystyle P_{term} = 0$

By making M the subject this gives the repayment.