Recurrence relations

Printable View

November 30th 2010, 03:19 AM
durrrrrrrr

Recurrence relations

If I have a recurrence relation such as:
$a(n) = A*a(n-1) + B*a(n-2)$ where $a(0)=X, a(1)=Y$
how do I solve this?

Wikipedia explains how to solve such an equation and I used it and it worked for me. But I don't understand how it works.

This is what Wiki says (in short):

With our equation above we try to find an answer of the form $a(n) = r^n$
Then $r^n=A*r^(n-1)+B*r^(n-2)$
Then $r^2-(A*r)-B=0$
You solve this and you write: $a(n)=C*root1^n+D*root2^n$
You then work out what C and D are (using a(0) and a(1) which you already know and you have your equation.
(This is the link to wikipedia's explanation:
Recurrence relation - Wikipedia, the free encyclopedia)

Could someone explain why this works please.
And also, how does one prove that the new formula is correct?

Thanks
November 30th 2010, 03:57 AM
durrrrrrrr

I worked out a proof by induction for my specific problem. I still don't understand how I got the equation though. Can anyone explain it?
November 30th 2010, 04:13 AM
chisigma

The 'charachteristic equation' associated to the homogeneous linear recurrence relation $a_{n}= A\ a_{n-1} + B\ a_{n-2}$ is...

$r^{2} -A\ r - B = 0$ (1)

If the (1) has two distinct real roots $r_{1}$ and $r_{2}$ the solution is...

$a(n)= c_{1}\ r_{1}^{n} + c_{2}\ r_{2}^{n}$ (2)

... where the constants $c_{1}$ and $c_{2}$ are derived from the 'initial conditions'...

Kind regards

$\chi$ $\sigma$
November 30th 2010, 04:47 AM
durrrrrrrr

Thanks for your help but I still don't understand why it works. All I understand is that it does work.
November 30th 2010, 09:03 AM
chisigma

A second order linear homogeneous recurrence relation has the form...

$\displaystyle x_{n+2} + a_{1}\ x_{n+1} + a_{2}\ x_{n}=0$ (1)

a) we first demonstrate that if $u_{n}$ and $v_{n}$ are two independent solution of (1), then also $c_{1}\ u_{n} + c_{2}\ v_{n}$ , where $c_{1}$ and $c_{2}$ are arbitrary constants, is also solution of (1)...

... for what we have supposed is...

$\displaystyle u_{n+2} + a_{1}\ u_{n+1} + a_{2}\ u_{n}=0$

$\displaystyle v_{n+2} + a_{1}\ v_{n+1} + a_{2}\ v_{n}=0$ (2)

... so that multiplying the first of (2) by $c_{1}$ and the second of (2) by $c_{2}$ we obtain...

$\displaystyle c_{1}\ u_{n+2} + c_{2}\ u_{n+2} + a_{1}\ (c_{1} \ u_{n+1} + c_{2}\ v_{n+1}) + a_{2}\ (c_{1}\ u_{n} + c_{2}\ v_{n}) =0$ (3)

... that is what we want to demonstrate...

b) ... then we demonstrate that if $a_{1}$ and $a_{2}$ are constant and $r_{1}$ and $r_{2}$ are two real dinstict roots of the equation...

$\displaystyle r^{2} + a_{1}\ r + a_{2} =0$ (4)

... then $u_{n}= r_{1}^{n}$ and $v_{n}= r_{2}^{n}$ ...

... setting $u_{n}= r_{1}^{n}$ is the first of (3) we obtain...

$\displaystyle u_{n+2} + a_{1}\ u_{n+1} + a_{2}\ u_{n} = r_{1}^{n}\ (r_{1}^{2} + a_{1}\ r_{1} + a_{2}) =0$ (5)

... that is what we want to demonstrate. The same is for $v_{n}$ ...

Kind regards

$\chi$ $\sigma$
December 1st 2010, 03:53 AM
durrrrrrrr

Thank you
December 1st 2010, 06:59 AM
Soroban

Hello, durrrrrrrr!

I'll explain the steps.
I don't know if it will clear up the mystery for you.

Quote:

$\text{If I have a recurrence relation such as:}$

$a(n) \:=\: A\!\cdot\!a(n-1) + B\!\cdot\!a(n-2)\,\text{ where }a(0)=X,\:a(1)=Y$

$\text{how do I solve this?}$

First, we conjecture that the generating function is exponential.
. . Let $a(n) \:=\:r^n$

So we have: . $r^n \:=\:A\!\cdot\!r^{n-1} +B\!\cdot\!r^{n-2} \quad\Rightarrow\quad r^n - A\!\cdot\!r^{n-1} - B\!\cdot\!r^{n-2} \:=\:0$

Divide by $r^{n-2}\!:\;\;r^2 - Ar - B \:=\:0$

Quadratic Formula: . $r \;=\;\dfrac{A \pm\sqrt{A^2 + 4B}}{2}$

Form a linear combination of the two roots:

. . $a(n) \;=\;C\left(\dfrac{A + \sqrt{A^2+4B}}{2}\right)^n + D\left(\dfrac{A - \sqrt{A^2 + 4B}}{2}\right)^n$ .[1]

Use the first two terms of the sequence to set up a system of equations:

. . $\begin{array}{ccccccc} a(0) = X\!: & C \qquad + \qquad D &=& X \\ a(1) = Y\!: & C\left(\frac{A + \sqrt{A^2 + 4b}}{2}\right) + D\left(\frac{A - \sqrt{A^2+4B}}{2}\right) &=& Y \end{array}$

Solve the system: . $\begin{Bmatrix} C &=& \dfrac{2Y - X(A - \sqrt{A^2 + 4B}\,)}{2\sqrt{A^2+4B}} \\ \\[-3mm] D &=& \dfrac{X(A + \sqrt{A^2+4B}\,) - 2Y}{2\sqrt{A^2+4B^2}} \end{Bmatrix}$

Substitute into [1] and we have the closed form of the recurrence.