---
type: theoretical
---



A recurrence relation is an equation that defines a sequence based on its earlier terms, along with initial values.

- The recurrence relation $a_n = a_{n-1} + 4$ with initial condition $a_1 = 3$ defines the sequence: $3, 7, 11, 15, \ldots$.

### Techniques for Finding Explicit Formulas

1. ***Backtracking*** involves repeatedly substituting the recurrence relation into itself until a pattern emerges. 

    - For the recurrence relation $a_n = a_{n-1} + 4$, we repeatedly substitute:
      - $a_n = a_{n-1} + 4$
      - $a_n = (a_{n-2} + 4) + 4 = a_{n-2} + 2 \cdot 4$
      - $a_n = ((a_{n-3} + 4) + 4) + 4 = a_{n-3} + 3 \cdot 4$
      - $\ldots$
      - $a_n = a_{n-(n-1)} + (n-1) \cdot 4 = a_1 + (n-1) \cdot 4 = 3 + (n-1) \cdot 4$
    
    - So, the explicit formula for the sequence is:
      $$
      a_n = 3 + (n-1) \cdot 4
      $$

2. ***Characteristic Equation*** applies to linear homogeneous recurrence relations.

    - A **LHR** relation of degree $k$ is of the form:
      $$
      s_n = a_1 s_{n-1} + a_2 s_{n-2} + \ldots + a_k s_{n-k},
      $$
      where $a_i \in \mathbb{R}$ are constants. [^1]

    - The ***characteristic equation*** is:
      $$
      x^k - a_1 x^{k-1} - a_2 x^{k-2} - \ldots - a_k = 0
      $$

    - The roots of the characteristic equation determine the explicit formula for the sequence.

---

### Solving Linear Homogeneous Recurrence Relations of Degree 2

For $s_n = a s_{n-1} + b s_{n-2}$, the characteristic equation is $x^2 - ax - b = 0$. Let $r_1$ and $r_2$ be the roots:

1. **In case of distinct roots** ($r_1 \neq r_2$):
   - The general solution is:
     $$
     s_n = c_1 r_1^n + c_2 r_2^n,
     $$
     where $c_1$ and $c_2$ are constants determined by initial conditions.

2. **In case of repeated roots** ($r_1 = r_2 = r$):
   - The general solution is:
     $$
     s_n = r^n (c_1 + c_2 n),
     $$
     where $c_1$ and $c_2$ are constants determined by initial conditions. [^2]

---

## Example - Fibonacci Sequence

The Fibonacci sequence is defined as:
$$
f_n = 
\begin{cases}
0, & \text{if } n = 0, \\
1, & \text{if } n = 1, \\
f_{n-1} + f_{n-2}, & \text{if } n \geq 2.
\end{cases}
$$

- The characteristic equation is:
  $$
  x^2 - x - 1 = 0
  $$

- The roots are:
  $$
  r_1 = \frac{1 + \sqrt{5}}{2}, \quad r_2 = \frac{1 - \sqrt{5}}{2}.
  $$

- Since $r_1 \neq r_2$, the explicit formula is:
  $$
  f_n = c_1 r_1^n + c_2 r_2^n.
  $$

- Using the initial conditions:
  - $f_0 = 0 = c_1 + c_2$
  - $f_1 = 1 = c_1 \left(\frac{1 + \sqrt{5}}{2}\right) + c_2 \left(\frac{1 - \sqrt{5}}{2}\right)$

- Solving this system, we get:
  $$
  c_1 = \frac{1}{\sqrt{5}}, \quad c_2 = -\frac{1}{\sqrt{5}}.
  $$

- Therefore, the explicit formula for the Fibonacci sequence is:
  $$
  f_n = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2}\right)^n.
  $$

---

## Verifying Explicit Formulas

The correctness of an explicit formula for a recurrence relation can be proven using ***strong mathematical induction***. For example, the explicit Fibonacci formula is verified by [Induction](Mathematical%20Proofs%20(Induction).md).


## Footnotes

[^1]: Linear homogeneous recurrence relations are equations where each term is a combination of earlier terms, with no added constants.
[^2]: Repeated roots in a characteristic equation require modifying the solution to include a term that grows linearly with $n$.
