# Recurrence Relation

## Fibonacci numbers

Fibonacci numbers are defined as:

(F_0 = 0, F_1 = 1), for (n\geq 1), $F_{n+1} = F_n +F_{n-1}$

# How to solve recurrence relation in general

In general, consider a recurrence equation of the form (X_{n+1} + \beta X_n + \gamma X_{n-1} = 0) where (n\geq 0).

Let (X_0 = c_0) and (X_1=c_1)

We consider it as a quadratic equation and solve for (x^2 + \beta x + \gamma = 0).

$x^+ = \left ( {- \beta + \sqrt {\beta^2-4\gamma} }\over{2} \right)$

$x^- = \left ( {- \beta - \sqrt {\beta^2-4\gamma} }\over{2} \right)$

If $x^+ \neq x^-$ then solution is $X_n = A(x+)n + A^\prime (x-)n$ where $A+A^\prime = c_0$ $Ax^+ + A^\prime x^- = c_1$

Note: The these big X’s and small x’s used here very visually confusing, but sadly that’s how the instructor wrote it and I didn’t want to change anything.

## Consider the example of Fibonacci sequence

$F_{n+1} - F_n - F_{n-1} = 0$

here we have (\beta = -1) and (\gamma = -1)

Solve for (x^2-x-1), We get

$x^+ = {1+\sqrt{1+4}\}\over {2}$ $x^- = {1-\sqrt{1+4}\}\over {2}$

So we have (x^+ \neq x^-)

$F_n = A \left( {1+\sqrt{5}\} \over {2} \right)^n + A^\prime \left( {1-\sqrt{5}\}\over {2} \right)^n$

where (A+A^\prime = 0) and (Ax^+ + A^\prime x^- = 1)

Solve for (A) and (A^\prime) we get

$F_n = {\{1}\over{\sqrt 5}\} \left( {1+\sqrt{5}\} \over {2} \right)^n -{\{1}\over{\sqrt 5}\} \left( {1-\sqrt{5}\}\over {2} \right)^n$