Recurrence Relations: short notes (Engineering Mathematics)

Introduction

A recurrence relation defines each term of a sequence from earlier terms: $a_n = a_{n-1} + a_{n-2}$ , $T(n) = 2T(n/2) + n$ . Recurrences arise whenever a problem of size $n$ is reduced to smaller instances of itself: counting strings by their last symbol, counting moves in the Tower of Hanoi, or measuring the running time of a recursive algorithm.

The topics are modelling with recurrences and solving linear recurrences with constant coefficients exactly. Divide-and-conquer recurrences and the master theorem, which give asymptotic answers, are treated in Recurrences and the Master Theorem; Generating Functions give a second method for the recurrences here.

Prerequisites

Counting: sum and product rules, binomial coefficients.
Solving quadratic equations; geometric series $\sum_{i=0}^{n-1} r^i = (r^n - 1)/(r - 1)$ for $r \ne 1$ .

Core concepts

Terminology

A recurrence of order $k$ expresses $a_n$ using $a_{n-1}, \ldots, a_{n-k}$ . It determines the sequence uniquely once $k$ initial conditions (for example $a_0, \ldots, a_{k-1}$ ) are given.
Linear with constant coefficients: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n)$ , with constants $c_i$ and $c_k \ne 0$ .
Homogeneous if $f(n) = 0$ ; otherwise non-homogeneous, and $f(n)$ is the forcing term.
A closed form gives $a_n$ directly as a function of $n$ .

Modelling: three standard recurrences

Tower of Hanoi. To move $n$ discs, move $n - 1$ discs aside, move the largest, then move the $n - 1$ discs back on top: $H_n = 2H_{n-1} + 1$ , $H_1 = 1$ . Closed form $H_n = 2^n - 1$ .
Binary strings of length $n$ with no two consecutive 0s. A valid string ends in 1 (preceded by any valid string of length $n - 1$ ) or in 10 (preceded by any valid string of length $n - 2$ ): $a_n = a_{n-1} + a_{n-2}$ , $a_1 = 2$ , $a_2 = 3$ . So $a_n = F_{n+2}$ , with Fibonacci numbers $F_1 = F_2 = 1$ .
Regions formed by $n$ lines in general position (no two parallel, no three concurrent). The $n$ -th line crosses the other $n - 1$ lines at distinct points and is cut into $n$ pieces, each splitting a region: $L_n = L_{n-1} + n$ , $L_0 = 1$ , so $L_n = 1 + n(n+1)/2$ .

Method 1: unrolling (iteration)

For first-order recurrences, substitute repeatedly and sum.

a_n = c\,a_{n-1} + d \;\Rightarrow\; a_n = c^n a_0 + d\,(c^{n-1} + \cdots + c + 1) = c^n a_0 + d\,\frac{c^n - 1}{c - 1} \quad (c \ne 1),

and $a_n = a_0 + nd$ when $c = 1$ . Similarly, $a_n = a_{n-1} + g(n)$ gives $a_n = a_0 + \sum_{i=1}^{n} g(i)$ .

Unrolling a recurrence and the characteristic-root cases — Figure 1. Left: the Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$ unrolled level by level into $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$ . Right: the three cases of characteristic roots and the general solution for each.

Method 2: characteristic equation (homogeneous case)

For $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ , try $a_n = r^n$ . Dividing by $r^{n-k}$ gives the characteristic equation

r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0 .

Roots of the characteristic equation	General solution
Distinct roots $r_1, \ldots, r_k$	$a_n = \alpha_1 r_1^n + \cdots + \alpha_k r_k^n$
Root $r$ of multiplicity $m$	contributes $(\beta_0 + \beta_1 n + \cdots + \beta_{m-1} n^{m-1})\, r^n$
Simple conjugate pair $\rho e^{\pm i\theta}$ (real coefficients)	$\rho^n(\gamma_1\cos(n\theta)+\gamma_2\sin(n\theta))$ ; multiplicity $m$ gives $\rho^n[P_{m-1}(n)\cos(n\theta)+Q_{m-1}(n)\sin(n\theta)]$ , with real polynomials of degree at most $m-1$

The constants $\alpha_i$ (or $\beta_j$ ) are fixed by the $k$ initial conditions, which give $k$ linear equations.

Second-order summary. For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ with characteristic equation $r^2 - c_1 r - c_2 = 0$ : distinct roots $r_1 \ne r_2$ give $a_n = \alpha r_1^n + \beta r_2^n$ ; a double root $r_0$ gives $a_n = (\alpha + \beta n) r_0^n$ .

Fibonacci (Binet's formula). $F_n = F_{n-1} + F_{n-2}$ , $F_0 = 0$ , $F_1 = 1$ . Roots $\varphi = (1 + \sqrt{5})/2$ and $\psi = (1 - \sqrt{5})/2$ :

F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} .

Since $|\psi| < 1$ , $F_n$ is the integer nearest to $\varphi^n/\sqrt{5}$ , so $F_n = \Theta(\varphi^n)$ with $\varphi \approx 1.618$ .

Method 3: non-homogeneous recurrences

For $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + f(n)$ :

a_n = a_n^{(h)} + a_n^{(p)},

where $a_n^{(h)}$ is the general solution of the homogeneous part and $a_n^{(p)}$ is any one particular solution. Apply the initial conditions after adding the two parts.

Trial forms for the particular solution, where $s$ is the multiplicity of $b$ as a characteristic root ( $s = 0$ if $b$ is not a root):

Forcing term $f(n)$	Try $a_n^{(p)}$
Constant $d$	$A\, n^{s}$ with $b = 1$
Polynomial of degree $t$	$n^{s}(A_t n^t + \cdots + A_0)$ with $b = 1$
$d\, b^n$	$A\, n^{s} b^n$
$(\text{polynomial of degree } t)\, b^n$	$n^{s}(A_t n^t + \cdots + A_0)\, b^n$

The factor $n^{s}$ handles resonance, when the forcing term already solves the homogeneous recurrence.

Worked examples

Example 1: distinct roots

Solve $a_n = 5a_{n-1} - 6a_{n-2}$ , $a_0 = 1$ , $a_1 = 0$ .

Characteristic equation $r^2 - 5r + 6 = 0$ , roots 2 and 3, so $a_n = \alpha 2^n + \beta 3^n$ . Initial conditions: $\alpha + \beta = 1$ and $2\alpha + 3\beta = 0$ , so $\beta = -2$ , $\alpha = 3$ :

a_n = 3 \cdot 2^n - 2 \cdot 3^n .

Check: $a_2 = 5 \cdot 0 - 6 \cdot 1 = -6$ and $3 \cdot 4 - 2 \cdot 9 = -6$ .

Example 2: repeated root

Solve $a_n = 4a_{n-1} - 4a_{n-2}$ , $a_0 = 1$ , $a_1 = 6$ .

$r^2 - 4r + 4 = (r - 2)^2$ , double root 2, so $a_n = (\alpha + \beta n) 2^n$ . $a_0 = \alpha = 1$ ; $a_1 = 2(1 + \beta) = 6$ , so $\beta = 2$ :

a_n = (1 + 2n)\, 2^n .

Check: $a_2 = 4 \cdot 6 - 4 \cdot 1 = 20 = 5 \cdot 4$ .

Example 3: non-homogeneous, no resonance

Solve $a_n = 3a_{n-1} + 2^n$ , $a_0 = 1$ .

Homogeneous: $A \cdot 3^n$ . Particular: try $C\, 2^n$ : $C 2^n = 3C 2^{n-1} + 2^n$ , so $C = \tfrac{3}{2}C + 1$ , $C = -2$ . General: $a_n = A\,3^n - 2^{n+1}$ ; $a_0 = A - 2 = 1$ , $A = 3$ :

a_n = 3^{n+1} - 2^{n+1} .

Check: $a_1 = 3 + 2 = 5 = 9 - 4$ .

Example 4: resonance

Solve $a_n = 2a_{n-1} + 2^n$ , $a_0 = 1$ .

2 is a root of $r - 2 = 0$ with multiplicity 1, so try $C n 2^n$ : $C n 2^n = 2C(n-1)2^{n-1} + 2^n$ , giving $C n = C(n - 1) + 1$ , so $C = 1$ . General: $a_n = A 2^n + n 2^n$ ; $a_0 = A = 1$ :

a_n = (n + 1)\, 2^n .

Example 5: polynomial forcing

$T(n) = T(n-1) + n$ , $T(0) = 0$ . Unrolling: $T(n) = 1 + 2 + \cdots + n = n(n+1)/2 = \Theta(n^2)$ . Likewise $T(n) = T(n-1) + 1$ gives $\Theta(n)$ , and $T(n) = 2T(n-1) + 1$ gives $\Theta(2^n)$ .

Example 6: a three-term counting recurrence

Count the ternary strings (digits 0, 1, 2) of length $n$ that do not contain "00". Ending in 1 or 2: $2a_{n-1}$ . Ending in 0: the previous symbol is 1 or 2, giving $2a_{n-2}$ . So $a_n = 2a_{n-1} + 2a_{n-2}$ , $a_1 = 3$ , $a_2 = 8$ ; then $a_3 = 22$ , $a_4 = 60$ . Roots $1 \pm \sqrt{3}$ .

Important properties and observations

The solution space of a homogeneous linear recurrence of order $k$ is a vector space of dimension $k$ ; $k$ initial values pin down one solution.
For a homogeneous linear recurrence with constant coefficients, if one root $r_{\max}$ has strictly the largest modulus (every other root is smaller in modulus), has multiplicity $m$ , and the coefficient of $n^{m-1} r_{\max}^n$ is nonzero, then $\lvert a_n \rvert = \Theta(n^{m-1} \lvert r_{\max} \rvert^n)$ ; for a simple root this is $\Theta(\lvert r_{\max} \rvert^n)$ . Example 2 gives $\Theta(n 2^n)$ . For a non-homogeneous recurrence, compare with the particular solution, which can dominate: Example 4 is $\Theta(n 2^n)$ although its only root 2 is simple, and Example 5 is $\Theta(n^2)$ although its only root 1 is simple. Example 1 has $a_n \to -\infty$ like $-2 \cdot 3^n$ , so the bound is stated for $\lvert a_n \rvert$ . With two roots of equal modulus, such as $\pm 2$ , terms can cancel: $a_n = 2^n + (-2)^n$ solves $a_n = 4a_{n-2}$ with nonzero coefficients, but $a_n = 0$ for every odd $n$ , so it is not $\Theta(2^n)$ . Non-real roots of a real recurrence come in conjugate pairs of equal modulus, so a strictly dominant root is real. If the largest modulus belongs to a conjugate pair, the rule does not apply and the terms can oscillate: $a_n = 2a_{n-1} - 2a_{n-2}$ , $a_0 = 0$ , $a_1 = 1$ (roots $1 \pm i$ ) gives 0, 1, 2, 2, 0, −4, −8, −8, 0.
Linear recurrences with constant coefficients solve exactly. Divide-and-conquer recurrences such as $T(n) = aT(n/b) + f(n)$ are usually solved asymptotically (master theorem, recursion tree); substituting $n = b^k$ turns them into constant-coefficient recurrences in $k$ .
Always verify a closed form against two or three terms computed directly from the recurrence.

GATE examination perspective

Solve or evaluate. Find $a_n$ or a specific term; the characteristic equation is the standard route. Watch repeated roots.
Modelling questions. Count strings or tilings by conditioning on the last symbol or block. Get the initial conditions right; check them carefully.
Particular solutions. Use the trial table, multiplying by $n^s$ under resonance.
Asymptotics. Assume $c>0$ and a nonnegative fixed base cost: $T(n) = T(n-1) + c$ is linear, $+n$ is quadratic, $2T(n-1) + c$ is exponential.
Trap: applying initial conditions to the homogeneous part before adding the particular solution.

Summary

Order- $k$ linear recurrence + $k$ initial values determine the sequence.
Characteristic equation $r^k = c_1 r^{k-1} + \cdots + c_k$ : distinct roots $\sum \alpha_i r_i^n$ ; root of multiplicity $m$ : $(\beta_0 + \cdots + \beta_{m-1}n^{m-1}) r^n$ .
Non-homogeneous: $a_n = a_n^{(h)} + a_n^{(p)}$ ; multiply the trial form by $n^s$ under resonance.
Hanoi $2^n - 1$ ; no-"00" binary strings $F_{n+2}$ ; Fibonacci $\Theta(\varphi^n)$ .
Unrolling turns $T(n) = T(n-1) + n$ into $n(n+1)/2$ and $T(n) = 2T(n-1) + 1$ into $2^n - 1$ .
Apply initial conditions only after adding the particular solution to the homogeneous one.

Counting: prerequisite. The counting arguments that produce recurrences.
Generating Functions: dependent. Solve recurrences with power series.
Recurrences and the Master Theorem: dependent. Divide-and-conquer recurrences in algorithm analysis.
Dynamic Programming Fundamentals: related. Recurrences evaluated bottom-up.

Recurrence Relations

Introduction

Prerequisites

Core concepts

Terminology

Modelling: three standard recurrences

Method 1: unrolling (iteration)

Method 2: characteristic equation (homogeneous case)

Method 3: non-homogeneous recurrences

Worked examples

Example 1: distinct roots

Example 2: repeated root

Example 3: non-homogeneous, no resonance

Example 4: resonance

Example 5: polynomial forcing

Example 6: a three-term counting recurrence

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Terminology

Modelling: three standard recurrences

Method 1: unrolling (iteration)

Method 2: characteristic equation (homogeneous case)

Method 3: non-homogeneous recurrences

Worked examples

Example 1: distinct roots

Example 2: repeated root

Example 3: non-homogeneous, no resonance

Example 4: resonance

Example 5: polynomial forcing

Example 6: a three-term counting recurrence

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps