*Last modified: September 16, 2024*

*This article is written in: ðŸ‡ºðŸ‡¸*

## Difference Equation

A **difference equation** (also known as a recurrence relation) defines each term of a sequence based on previous terms. In some cases, the general term of a sequence is given explicitly (e.g., $a_n = 3n + 2$, resulting in the sequence $5, 8, 11, \dots$). However, more commonly, a difference equation provides a relationship between terms.

For example:

$$ a_n = 4 a_{n-1} - 5 a_{n-2} $$

is a second-order difference equation because it relates $a_n$ to the two previous terms $a_{n-1}$ and $a_{n-2}$.

### Solving Difference Equations

To solve a difference equation, we often look for a solution of the form:

$$ a_n = \lambda^n $$

This assumes a solution structure where each term is proportional to the previous term by some factor $\lambda$.

**Example:**

For the difference equation:

$$ a_n = 4 a_{n-1} - 5 a_{n-2} $$

Substitute $a_n = \lambda^n$ into the equation:

$$ \lambda^n = 4 \lambda^{n-1} - 5 \lambda^{n-2} $$

Dividing both sides by $\lambda^{n-2}$, we get the **characteristic equation**:

$$ \lambda^2 - 4 \lambda + 5 = 0 $$

This is a quadratic equation. Solving for $\lambda$, we get the roots:

$$ \lambda = 2, \lambda = 3 $$

Thus, the general solution to the difference equation is:

$$ a_n = c_1 2^n + c_2 3^n $$

where $c_1$ and $c_2$ are constants determined by the initial conditions.

### Example: Solving with Initial Conditions

Given the initial conditions $a_0 = 4$ and $a_1 = 10$, we can solve for $c_1$ and $c_2$.

At $n = 0$:

$$ a_0 = c_1 2^0 + c_2 3^0 = c_1 + c_2 = 4 $$

At $n = 1$:

$$ a_1 = c_1 2^1 + c_2 3^1 = 2 c_1 + 3 c_2 = 10 $$

Solving this system of equations:

$$ \begin{aligned} c_1 + c_2 &= 4 \\ 2 c_1 + 3 c_2 &= 10 \end{aligned} $$

We find:

$$ c_1 = 2, \quad c_2 = 2 $$

Thus, the solution to the difference equation is:

$$ a_n = 2 \cdot 2^n + 2 \cdot 3^n $$

### Higher-Order Difference Equations

A $k$-th order difference equation has the form:

$$ a_n = \beta_1 a_{n-1} + \beta_2 a_{n-2} + \dots + \beta_k a_{n-k} $$

The characteristic equation for such a difference equation is:

$$ \lambda^k - \beta_1 \lambda^{k-1} - \dots - \beta_k = 0 $$

Once we find the $k$ roots $\lambda_1, \lambda_2, \dots, \lambda_k$, the general solution is:

$$ a_n = c_1 \lambda_1^n + c_2 \lambda_2^n + \dots + c_k \lambda_k^n $$

The constants $c_1, c_2, \dots, c_k$ are determined by the initial conditions.

### Example: Fibonacci Sequence

The Fibonacci sequence is a classic example of a difference equation:

$$ a_n = a_{n-1} + a_{n-2} $$

with initial conditions $a_0 = 2$ and $a_1 = 3$.

The characteristic equation is:

$$ \lambda^2 - \lambda - 1 = 0 $$

Solving this quadratic equation:

$$ \lambda_1 = \frac{1 - \sqrt{5}}{2}, \quad \lambda_2 = \frac{1 + \sqrt{5}}{2} $$

Thus, the general solution is:

$$ a_n = c_1 \left( \frac{1 - \sqrt{5}}{2} \right)^n + c_2 \left( \frac{1 + \sqrt{5}}{2} \right)^n $$

Using the initial conditions:

$$ c_1 + c_2 = 2 $$

$$ c_1 \left( \frac{1 - \sqrt{5}}{2} \right) + c_2 \left( \frac{1 + \sqrt{5}}{2} \right) = 3 $$

Solving for $c_1$ and $c_2$, we find:

$$ c_1 = \frac{3 - \sqrt{5}}{2}, \quad c_2 = \frac{3 + \sqrt{5}}{2} $$

Thus, the general term of the Fibonacci sequence is:

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

### Relation to Differential Equations

A $k$-th order linear ordinary differential equation has a similar form to the $k$-th order difference equation:

$$ y^{(k)} = \beta_1 y^{(k-1)} + \dots + \beta_k y $$

The solution for the differential equation is found using the same characteristic equation:

$$ \lambda^k - \beta_1 \lambda^{k-1} - \dots - \beta_k = 0 $$

Once the roots are found, the general solution is expressed as a sum of exponentials, analogous to the powers of $\lambda$ in the difference equation solution.