Recurrence Relations

Precise definition

A recurrence relation defines sequence terms using earlier terms. An order-$k$ recurrence generally needs $k$ independent initial values to determine one sequence. A linear homogeneous constant-coefficient recurrence has the form $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}$; nonhomogeneous recurrences add a forcing term.

Notation and mathematical language

The index range matters: $a_n=3a_{n-1}$ for $n\ge1$ plus $a_0=2$ yields $a_n=2\cdot3^n$. A closed form gives $a_n$ directly as a function of $n$. For $a_n=ra_{n-1}$, repeated substitution produces a geometric sequence.

Conceptual picture

A recurrence describes local evolution, while a closed form describes the term at any index without computing all predecessors. A computation tree can expose repeated work in a naive recursive algorithm; dynamic programming stores previously computed terms while preserving the same mathematical recurrence.

Conditions and key results

Initial conditions are part of the definition: without enough of them, many sequences satisfy the same recurrence. Candidate closed forms must satisfy both the recurrence and every initial value. Characteristic-root methods apply to linear homogeneous recurrences with constant coefficients, not arbitrary nonlinear recurrences.

A reliable strategy

1. Identify the order, valid index range, forcing term, and all initial conditions.
2. Generate several terms carefully to reveal growth and catch indexing errors.
3. Solve by iteration, characteristic equation, or another method suited to the recurrence class.
4. Verify the candidate algebraically in the recurrence and separately against every initial condition.

Fully worked example

Interpretation and application

Recurrences model compound growth, population generations, algorithm running times, and combinatorial structures. A recurrence is exact relative to its model; measured data may only approximately follow it, so model fit and causal interpretation require separate evidence.

Common mistakes

Verification and reasonableness

• Substitute the closed form into both sides and simplify them independently.
• Check every supplied initial term, not only the recurrence.
• Compare the first several values from the formula with direct iteration as an error-detection step.

Practice

1. Find the next three terms if $a_0=1$ and $a_n=a_{n-1}+3$.
2. Solve $a_n=5a_{n-1}$ with $a_0=2$.
3. Why does a second-order recurrence usually need two initial values?

Further deduction

For $a_n=5a_{n-1}-6a_{n-2}$, try $a_n=r^n$ to obtain $r^2-5r+6=0$, whose roots are $2$ and $3$. Therefore candidates have form $a_n=A2^n+B3^n$. If $a_0=1$ and $a_1=4$, then $A+B=1$ and $2A+3B=4$, so $B=2$, $A=-1$, and $a_n=-2^n+2\cdot3^n$. Substitution and both initial values complete the verification. A repeated characteristic root changes the form: if $(r-r_0)^2$ occurs, the independent solutions are $r_0^n$ and $nr_0^n$, so the general term is $(A+Bn)r_0^n$ rather than two copies of the same sequence.

Generating functions offer another solution route by encoding $(a_n)$ as $A(x)=\sum_{n\ge0}a_nx^n$. Shifting the recurrence becomes multiplication by powers of $x$, and initial terms appear as correction terms. Algebraic decomposition of $A(x)$ then recovers coefficients.

Related topics

• Mathematical Induction
• Characteristic Equation
• Algorithms