# Thread: Recurrence relations

1. ## Recurrence relations

If I have a recurrence relation such as:
$\displaystyle a(n) = A*a(n-1) + B*a(n-2)$ where $\displaystyle 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 $\displaystyle a(n) = r^n$
Then $\displaystyle r^n=A*r^(n-1)+B*r^(n-2)$
Then $\displaystyle r^2-(A*r)-B=0$
You solve this and you write: $\displaystyle 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

2. 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?

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

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

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

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

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

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

4. Thanks for your help but I still don't understand why it works. All I understand is that it does work.

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

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

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

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

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

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

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

$\displaystyle \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 $\displaystyle a_{1}$ and $\displaystyle a_{2}$ are constant and $\displaystyle r_{1}$ and $\displaystyle r_{2}$ are two real dinstict roots of the equation...

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

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

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

$\displaystyle \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 $\displaystyle v_{n}$...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

6. Thank you

7. Hello, durrrrrrrr!

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

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

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

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

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

So we have: .$\displaystyle 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 $\displaystyle r^{n-2}\!:\;\;r^2 - Ar - B \:=\:0$

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

Form a linear combination of the two roots:

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

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

. . $\displaystyle \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: .$\displaystyle \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  and we have the closed form of the recurrence.

#### Search Tags

recurrence, recurrence relation, relations 