Unit 2 - Notes

MTH401

Unit 2: Recurrence Relations

1. Fundamentals of Recurrence Relations

Definition

A recurrence relation for the sequence $\{a_n\}$ is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequence, namely $a_0, a_1, \dots, a_{n-1}$ , for all integers $n$ with $n \geq n_0$ , where $n_0$ is a nonnegative integer.

A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

Classification of Recurrence Relations

To solve a relation, one must first classify it based on:

Order: The difference between the highest and lowest subscripts of the terms present in the equation.
- Example: $a_n = a_{n-1} + a_{n-2}$ is of order 2 ( $n - (n-2) = 2$ ).
Linearity: It is linear if and previous terms appear to the first power and are not multiplied together.
- Linear: $a_n = 3a_{n-1} + 5$
- Non-linear: $a_n = (a_{n-1})^2$ or $a_n = a_{n-1} \cdot a_{n-2}$
Homogeneity: It is homogeneous if every term in the equation involves some . If there is a constant or a function of independent of , it is non-homogeneous.
- Homogeneous: $a_n - 3a_{n-1} = 0$
- Non-homogeneous: $a_n - 3a_{n-1} = n^2$
Coefficients: Constant coefficients (numbers) vs. variable coefficients (functions of $n$ ).

2. Modelling with Recurrence Relations

Modelling involves translating a real-world problem into a mathematical recurrence.

Classic Examples

1. Compound Interest

Problem: An investment of $1000 yields 5% interest per year. Let $P_n$ be the amount after $n$ years.
Model:

Initial condition: $P_0 = 1000$
Relation: The amount next year equals this year's amount plus interest.
$P_n = P_{n-1} + 0.05P_{n-1}$
$P_n = 1.05 P_{n-1}$

2. The Tower of Hanoi

Problem: Find the number of moves $H_n$ required to move $n$ disks from one peg to another, following standard rules.
Model:
To move $n$ disks:

Move the top $n-1$ disks to the auxiliary peg ( $H_{n-1}$ moves).
Move the largest disk to the target peg (1 move).
Move the $n-1$ disks from the auxiliary peg to the target peg ( $H_{n-1}$ moves).
Recurrence:
$H_n = 2H_{n-1} + 1$
With initial condition $H_1 = 1$ .

3. Fibonacci (Rabbit Breeding)

Problem: A pair of rabbits produces a new pair every month starting from the second month. How many pairs exist at month $n$ ?
Model:

F_n = F_{n-1} + F_{n-2}

With

F_0 = 0, F_1 = 1

(or

F_1=1, F_2=1

depending on indexing).

3. Homogeneous Linear Recurrence Relations with Constant Coefficients

General Form

A linear homogeneous recurrence relation of degree $k$ with constant coefficients is of the form:

a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}

where

c_1, c_2, \dots, c_k

are real numbers and

c_k \neq 0

Method of Solution: Characteristic Equation

Step 1: Rewrite the relation as:

a_n - c_1 a_{n-1} - c_2 a_{n-2} - \dots - c_k a_{n-k} = 0

Step 2: Assume a solution of the form $a_n = r^n$ ( $r \neq 0$ ). Substitute into the equation and divide by $r^{n-k}$ to obtain the Characteristic Equation:

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

Step 3: Solve for the roots ( $r_1, r_2, \dots, r_k$ ) of the characteristic equation.

Case A: Distinct Real Roots

If all roots $r_1, r_2, \dots, r_k$ are distinct, the general solution is:

a_n = \alpha_1 (r_1)^n + \alpha_2 (r_2)^n + \dots + \alpha_k (r_k)^n

The constants

\alpha_i

are determined using initial conditions.

Case B: Repeated Real Roots

If a root $r_1$ has multiplicity $m$ (it is repeated $m$ times), the part of the general solution corresponding to this root is:

(\alpha_1 + \alpha_2 n + \alpha_3 n^2 + \dots + \alpha_m n^{m-1}) r_1^n

Case C: Complex Conjugate Roots

If roots are complex numbers $a \pm bi$ , express them in polar form $R(\cos \theta \pm i \sin \theta)$ .
The solution is:

a_n = R^n (A \cos(n\theta) + B \sin(n\theta))

4. Method of Inverse Operator

This method allows for solving Non-Homogeneous Linear Recurrence Relations with Constant Coefficients.
General form:

c_0 a_n + c_1 a_{n-1} + \dots + c_k a_{n-k} = f(n)

where

f(n) \neq 0

The total solution is $a_n = a_n^{(h)} + a_n^{(p)}$ , where:

$a_n^{(h)}$ is the homogeneous solution (found by setting $f(n)=0$ ).
$a_n^{(p)}$ is the particular solution.

Shift Operator Definitions

Define the shift operator $E$ such that:

$E a_n = a_{n+1}$
$E^k a_n = a_{n+k}$
$E^{-1} a_n = a_{n-1}$

Rewrite the recurrence using $E$ .
Example: $a_n - 5a_{n-1} + 6a_{n-2} = f(n)$
Adjust indices to highest $n$ : $a_{n+2} - 5a_{n+1} + 6a_{n} = f(n+2)$
Operator form: $(E^2 - 5E + 6)a_n = f'(n)$
Let $\phi(E)$ be the polynomial in $E$ . Then:

a_n^{(p)} = \frac{1}{\phi(E)} f(n)

Rules for Solving $\frac{1}{\phi(E)} f(n)$

Case 1: Exponential Form $f(n) = A \cdot k^n$

If $f(n) = k^n$ where $k$ is a constant:

a_n^{(p)} = \frac{1}{\phi(E)} k^n = \frac{k^n}{\phi(k)}

Condition:

\phi(k) \neq 0

Exception (Case of Failure):
If $\phi(k) = 0$ , then $k$ is a root of the characteristic equation.
If $k$ is a root of multiplicity $m$ :

a_n^{(p)} = n^m \frac{k^n}{\phi^{(m)}(k)} \cdot (\text{scaling factor depending on operator definition})

Note: A simpler practical rule for $(E-k)^m y_n = k^n$ is to use the standard undetermined coefficient result $C n^m k^n$ .

Case 2: Polynomial Form $f(n) = A_0 + A_1 n + \dots + A_p n^p$

Rewrite $\frac{1}{\phi(E)}$ by substituting $E = 1 + \Delta$ (where $\Delta$ is the forward difference operator).
Alternatively, treat $\frac{1}{\phi(E)}$ as an algebraic fraction.
Expand $[\phi(E)]^{-1}$ in increasing powers of $\Delta$ (or $(E-1)$ ) up to the degree of the polynomial $f(n)$ .
Apply the expanded operator to $f(n)$ .

Case 3: Product Form $f(n) = k^n \cdot V(n)$

Where $V(n)$ is a polynomial in $n$ :

\frac{1}{\phi(E)} (k^n V(n)) = k^n \frac{1}{\phi(kE)} V(n)

After shifting

k^n

out, solve for the remaining polynomial part using the method in Case 2.

5. Generating Functions

A generating function is a formal power series whose coefficients correspond to a sequence of numbers.

Definition (Ordinary Generating Function - OGF)

For a sequence $a_0, a_1, a_2, \dots$ , the generating function $G(x)$ is defined as:

G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots

Important Series Expansions

Geometric Series:

$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1 + x + x^2 + \dots \quad (|x| < 1)$
Corresponds to sequence $\{1, 1, 1, \dots\}$ .
Generalised Binomial Theorem:

$\frac{1}{(1-x)^n} = \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k$
Specifically, $\frac{1}{(1-x)^2} = \sum (n+1) x^n$ .
Exponential:

$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}$

Shifts in Generating Functions

If $G(x)$ generates $\{a_n\}$ :

$x G(x)$ generates $\{0, a_0, a_1, a_2, \dots\}$ (Right shift).
$\frac{G(x) - a_0}{x}$ generates $\{a_1, a_2, a_3, \dots\}$ (Left shift).

6. Solution of Recurrence Relation using Generating Functions

This method is powerful because it converts the recurrence relation into an algebraic equation involving $G(x)$ .

The Algorithm

Define: Let $G(x) = \sum_{n=0}^{\infty} a_n x^n$ .
Multiply: Multiply the entire recurrence relation by $x^n$ .
Sum: Sum the equation over all valid $n$ (usually $n \geq k$ where $k$ is the order of the recurrence).
Substitute: Express all infinite sums in terms of and initial conditions.
- $\sum_{n=k}^{\infty} a_n x^n = G(x) - a_0 - a_1 x - \dots - a_{k-1} x^{k-1}$
- $\sum_{n=k}^{\infty} a_{n-1} x^n = x(G(x) - a_0 - \dots - a_{k-2} x^{k-2})$
- $\sum_{n=k}^{\infty} a_{n-2} x^n = x^2(G(x) - a_0 - \dots)$
Solve: Solve the resulting algebraic equation for $G(x)$ .
Expand: Express $G(x)$ as a power series (usually using Partial Fractions and known series expansions) to identify the coefficient of $x^n$ , which is $a_n$ .

Worked Example

Solve: $a_n - 5a_{n-1} + 6a_{n-2} = 0$ for $n \geq 2$ , with $a_0 = 1, a_1 = 4$ .

1. Multiply by $x^n$ and sum from $n=2$ to $\infty$ :

\sum_{n=2}^{\infty} a_n x^n - 5 \sum_{n=2}^{\infty} a_{n-1} x^n + 6 \sum_{n=2}^{\infty} a_{n-2} x^n = 0

2. Convert to $G(x)$ :

First term: $G(x) - a_0 - a_1 x = G(x) - 1 - 4x$
Second term: $-5x \sum_{n=2}^{\infty} a_{n-1} x^{n-1} = -5x(G(x) - a_0) = -5x(G(x) - 1)$
Third term: $+6x^2 \sum_{n=2}^{\infty} a_{n-2} x^{n-2} = 6x^2 G(x)$

3. Assemble Equation:

(G(x) - 1 - 4x) - 5x(G(x) - 1) + 6x^2 G(x) = 0

4. Group $G(x)$ terms:

G(x)(1 - 5x + 6x^2) - 1 - 4x + 5x = 0

G(x)(1 - 5x + 6x^2) = 1 - x

G(x) = \frac{1-x}{1 - 5x + 6x^2}

5. Partial Fractions:
Factor denominator: $1 - 5x + 6x^2 = (1-2x)(1-3x)$ .

\frac{1-x}{(1-2x)(1-3x)} = \frac{A}{1-2x} + \frac{B}{1-3x}

Solving for constants:

1-x = A(1-3x) + B(1-2x)

Set $x = 1/2$ : $0.5 = A(1 - 1.5) \Rightarrow 0.5 = -0.5A \Rightarrow A = -1$
Set $x = 1/3$ : $2/3 = B(1 - 2/3) \Rightarrow 2/3 = 1/3B \Rightarrow B = 2$

G(x) = \frac{2}{1-3x} - \frac{1}{1-2x}

6. Expand to find $a_n$ :
Using $\frac{1}{1-rx} = \sum r^n x^n$ :

G(x) = 2 \sum (3x)^n - 1 \sum (2x)^n

G(x) = \sum (2 \cdot 3^n - 2^n) x^n

Final Solution:

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