Unit 2: Recurrence Relations

I. Foundations and Governing Framework

A recurrence relation defines each term of a sequence through one or more preceding terms. Together with sufficient initial conditions, it converts a local rule into a uniquely determined sequence and provides a discrete model for processes that evolve in stages.

A. Defining Properties and Conventions

The study of recurrence relations depends on identifying the sequence, its order, its coefficients, and the information required to determine its terms.

• Sequence notation: A sequence is written as (a_0,a_1,a_2,\ldots), where (a_n) denotes the term indexed by the non-negative integer (n).
• Initial conditions: An order-(k) recurrence usually requires (k) independent starting values, such as (a_0,a1,\ldots,a{k-1}).
• Order: The order is the largest backward displacement appearing in the relation; a relation involving (an) and (a{n-2}) has order two.
• Linear relation: A recurrence is linear when sequence terms occur only to the first power and are not multiplied together.
• Homogeneous relation: A linear relation is homogeneous when its right-hand side is zero after all sequence terms are collected on one side.
• Constant coefficients: Coefficients are constant when they do not depend on (n), as in (3a{n-1}-2a{n-2}).
• Closed-form solution: A closed form expresses (a_n) directly as a function of (n), avoiding the calculation of all preceding terms.
• Verification convention: A proposed solution must satisfy both the recurrence relation and every given initial condition.

II. Recurrence Relations — Definition and Classification

A. Recurrence relation

A recurrence relation is an equation that defines a sequence term using earlier terms of the same sequence.

• General order-(k) form: A recurrence may be represented as:

F(n, a_n, a_(n-1), ..., a_(n-k)) = 0

• (F) is a specified function.
• (n) is the sequence index.
• (a_n) is the current term.
• (k) is the order of the recurrence.

• Explicit form: If the current term is isolated, the relation has the form:

a_n = f(n, a_(n-1), ..., a_(n-k))

Here (f) is the rule used to calculate (a_n).

• Linear form: An order-(k) linear recurrence can be written as:

a_n + c_1 a_(n-1) + ... + c_k a_(n-k) = g(n)

Here (c_1,\ldots,c_k) are coefficients and (g(n)) is the forcing term.

• Classification:

  1. If (g(n)=0), the relation is homogeneous.
  2. If (g(n)\ne0), it is non-homogeneous.
  3. If every (c_i) is independent of (n), it has constant coefficients.
  4. If a coefficient depends on (n), it has variable coefficients.

• Concrete example: The recurrence below generates the Fibonacci sequence:

a_n = a_(n-1) + a_(n-2),  n >= 2
a_0 = 0,  a_1 = 1

It gives (a_2=1), (a_3=2), and (a_4=3). The relation alone is insufficient without both initial values.

III. Mathematical Modelling — Translating Processes into Sequences

A. Modelling with recurrence relations

Modelling with recurrence relations represents the state of a discrete process at stage (n) in terms of its state at earlier stages.

• Modelling procedure:

  1. Define the sequence variable and its unit.
  2. Identify how one stage changes into the next.
  3. Translate that change into an equation.
  4. state the valid range of (n).
  5. Supply enough initial conditions.
  6. Check that computed terms agree with the process.

• Population or finance model: If a quantity grows by a fixed proportion (r) per period and receives an addition (d), then:

P_n = (1 + r)P_(n-1) + d

Here (P_n) is the quantity after (n) periods, (r) is the proportional growth rate per period, and (d) is the fixed addition per period.

• Counting model: If a valid object of size (n) is formed either by extending an object of size (n-1) in (p) ways or one of size (n-2) in (q) ways, then:

a_n = p a_(n-1) + q a_(n-2)

Here (a_n) counts valid objects of size (n), while (p) and (q) count the corresponding extensions.

• Worked model: A bank balance starts at 1,000 units, earns 5% annually, and receives 200 units at each year-end:

B_0 = 1000
B_n = 1.05B_(n-1) + 200

Thus (B_1=1250) and (B_2=1512.50). The model assumes a constant annual rate and fixed year-end deposits.

• Limitations: A recurrence is only as accurate as its assumptions; varying rates, random events, capacity limits, or timing differences require a modified relation.

IV. Homogeneous Equations — The Characteristic-Root Method

A. Homogeneous linear recurrence relations with constant coefficients

A homogeneous linear recurrence with constant coefficients is solved by converting shifts of the sequence into powers of an algebraic variable.

• Standard form:

a_n + c_1 a_(n-1) + ... + c_k a_(n-k) = 0

Here (k) is the order and (c_1,\ldots,c_k) are constants with (c_k\ne0).

• Trial solution: Substituting (a_n=r^n), where (r) is a constant, produces the characteristic equation:

r^k + c_1 r^(k-1) + ... + c_k = 0

• Distinct roots: If the characteristic roots (r_1,\ldots,r_k) are distinct, then:

a_n = A_1 r_1^n + ... + A_k r_k^n

The constants (A_1,\ldots,A_k) are determined from the initial conditions.

• Repeated roots: If a root (r) has multiplicity (m), its contribution is:

(A_0 + A_1 n + ... + A_(m-1)n^(m-1))r^n

• Complex roots: Conjugate roots (r=\rho(\cos θ \mathbin{+/-} i\sin θ)) produce real terms involving (\rho^n\cos(nθ)) and (\rho^n\sin(nθ)), where (\rho) is the modulus and (θ) is the argument.

• Worked example: For (an=5a{n-1}-6a_{n-2}), (a_0=1), and (a_1=4):

r^2 - 5r + 6 = 0
(r - 2)(r - 3) = 0
a_n = A2^n + B3^n

From (A+B=1) and (2A+3B=4), (A=-1) and (B=2). Therefore:

a_n = -2^n + 2(3^n)

V. Non-Homogeneous Equations — Inverse-Operator Technique

A. Method of inverse operator to solve the non-homogeneous recurrence relation with constant coefficient

The inverse-operator method treats a recurrence as an algebraic equation in a shift operator and applies the inverse polynomial operator to the forcing term.

• Shift operator: Define the backward-shift operator (E^{-1}) by:

E^(-1)a_n = a_(n-1)

Consequently, (E^{-j}an=a{n-j}), where (j) is a non-negative integer.

• Operator form: The recurrence becomes:

P(E^(-1))a_n = g(n)

Here (P) is the characteristic operator polynomial and (g(n)) is the non-homogeneous term.

• Complete solution:

a_n = a_n^(h) + a_n^(p)
a_n^(p) = [1 / P(E^(-1))]g(n)

Here (a_n^{(h)}) is the complementary homogeneous solution and (a_n^{(p)}) is a particular solution.

• Exponential forcing: If (g(n)=b^n), then (E^{-1}b^n=b^{-1}b^n). Provided (P(b^{-1})\ne0):

a_n^(p) = b^n / P(b^(-1))

• Resonance: If (P(b^{-1})=0), the trial overlaps the homogeneous solution and must be multiplied by a sufficient power of (n).

• Worked example: Consider (an-2a{n-1}=3^n). Its operator equation is:

(1 - 2E^(-1))a_n = 3^n

Since (E^{-1}3^n=3^{-1}3^n):

a_n^(p) = 3^n / (1 - 2/3) = 3^(n+1)

The homogeneous solution is (C2^n), so the general solution is (a_n=C2^n+3^{n+1}), where (C) is fixed by an initial condition.

VI. Generating Functions — Encoding Sequences as Power Series

A. Generating functions

A generating function packages an entire sequence into a formal power series whose algebraic properties reflect relationships among sequence terms.

• Ordinary generating function: For the sequence ({an}{n\ge0}), define:

A(x) = sum from n=0 to infinity of a_n x^n

Here (A(x)) is the generating function and (x) is a formal variable.

• Coefficient interpretation: The notation ([x^n]A(x)=a_n) means that (a_n) is the coefficient of (x^n) in (A(x)).

• Basic identities:

1 / (1 - x) = 1 + x + x^2 + ...
1 / (1 - cx) = sum from n=0 to infinity of c^n x^n

Here (c) is a constant.

• Shifting terms:

sum from n=1 to infinity of a_(n-1)x^n = xA(x)

Index shifts are the main mechanism for translating a recurrence into an equation involving (A(x)).

• Usefulness: Generating functions transform recurrence relations, convolution sums, and counting constructions into algebraic operations such as multiplication, differentiation, and partial-fraction decomposition.

• Formal character: In discrete mathematics, convergence is often unnecessary; the series may be manipulated formally because its coefficients, rather than its numerical value at (x), are the primary concern.

VII. Generating-Function Solution Method — From Recurrence to Coefficients

A. Solution of recurrence relation using generating functions

A recurrence is solved using generating functions by summing its terms, isolating the generating function, and extracting the coefficient of (x^n).

• Standard procedure:

  1. Define (A(x)=\sum_{n\ge0}a_nx^n).
  2. Multiply the recurrence by (x^n).
  3. Sum over the recurrence’s valid range.
  4. Separate missing initial terms.
  5. solve algebraically for (A(x)).
  6. Expand (A(x)) or use partial fractions to recover (a_n).

• Worked example: Let (an=3a{n-1}) for (n\ge1), with (a_0=2). Multiplication by (x^n) and summation give:

sum from n=1 to infinity of a_n x^n
= 3 sum from n=1 to infinity of a_(n-1)x^n

Using (A(x)-a_0) on the left and (3xA(x)) on the right:

A(x) - 2 = 3xA(x)
A(x) = 2 / (1 - 3x)

Applying the geometric-series identity:

A(x) = 2 sum from n=0 to infinity of 3^n x^n

Therefore the coefficient of (x^n) is:

a_n = 2(3^n)

• Partial fractions: When (A(x)) has several linear denominator factors, decomposing it into terms of the form (C/(1-rx)) converts each part directly into coefficients (Cr^n).

• Scope: The method is especially effective for linear recurrences and counting sequences, but coefficient extraction may become difficult when the resulting generating function has complicated or non-factorable denominators.