Math 240 Discrete Mathematics - Recurrence Relation

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 \]