Recurrence Relations and Generating Functions

Introduction and Context

Many discrete processes are defined not by a direct formula for the nth term, but by describing how each term depends on earlier terms. Such descriptions are called recurrence relations. They arise naturally in algorithm analysis, population models, financial projections, coding theory, data structures, digital signal processing, and sequential decision systems.

For example, the running time of an algorithm that divides a problem into smaller subproblems may satisfy a recurrence such as

\[

T(n)=2T(n/2)+n.

\]

A sequence describing a population that grows by a fixed proportion may satisfy

\[

a_n=1.05a_{n-1}.

\]

Recurrence relations therefore provide a bridge between discrete mathematics and computational practice.

Generating functions offer a complementary method. They encode an entire sequence as the coefficients of a formal power series. Algebraic operations on the generating function can then reveal a closed form, establish identities, or derive efficient computational procedures.

This chapter develops the principal methods for solving linear recurrence relations: iteration, characteristic equations, and generating functions. It also explains modeling assumptions, applications, limitations, and the relevance of these methods to artificial intelligence and machine learning.

Learning Objectives

After studying this chapter, you should be able to:

1. Define recurrence relations, initial conditions, order, and linearity.

2. Model sequential and recursive processes using recurrences.

3. Solve first-order recurrences by iteration and summation.

4. Solve homogeneous linear recurrences using characteristic equations.

5. Handle repeated and complex characteristic roots.

6. Solve nonhomogeneous recurrences using particular solutions.

7. Use ordinary generating functions to solve recurrences and derive identities.

8. Interpret recurrence solutions in algorithmic and applied contexts.

9. Evaluate assumptions, limitations, and computational implications of recurrence models.

1. Fundamental Concepts

A sequence is an ordered list of values \(a_0,a_1,a_2,\ldots\). A recurrence relation defines one or more terms using previous terms. A recurrence must normally be accompanied by initial conditions to determine a unique sequence.

For example,

\[

a_n=3a_{n-1}+2,\qquad a_0=1

\]

is a first-order recurrence. The recurrence alone permits many sequences, but the initial condition selects one:

\[

a_1=5,\quad a_2=17,\quad a_3=53.

\]

The order of a recurrence is the number of previous terms needed. The relation

\[

a_n=2a_{n-1}-a_{n-2}

\]

is second order and requires two initial values, normally \(a_0\) and \(a_1\).

A recurrence is linear if each sequence term occurs only to the first power and terms are not multiplied together. Thus,

\[

a_n-4a_{n-1}+3a_{n-2}=0

\]

is linear, whereas

\[

a_n=(a_{n-1})^2+1

\]

is nonlinear. A linear recurrence is homogeneous if its right-hand side is zero, and nonhomogeneous otherwise.

A general constant-coefficient linear recurrence of order \(k\) has the form

\[

a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}+f(n),

\]

where the \(c_i\) are constants and \(f(n)\) is a specified forcing term. The recurrence is usually considered for \(n\ge k\), together with \(k\) initial values.

2. Modeling with Recurrences

The quality of a recurrence solution depends first on the quality of the model. A useful modeling process is:

1. Define precisely what \(a_n\) represents.

2. Identify the time or size index \(n\).

3. Describe how the current state depends on previous states.

4. State initial conditions and their units.

5. Check boundary cases and the intended domain.

6. Interpret the resulting solution in the original context.

Example: Savings with Regular Deposits

Suppose an account earns interest at rate \(r\) per period and receives a deposit \(d\) at the end of each period. If \(A_n\) is the balance after the nth deposit and \(A_0

e 0\) is the initial balance, then

\[

A_n=(1+r)A_{n-1}+d.

\]

Here, \(r\) and \(d\) must refer to the same time period. The model assumes a constant rate, no withdrawals, and deposits made at the specified time.

Example: Recursive Algorithm

A binary divide-and-conquer algorithm may split an input into two subproblems of half the size and spend \(cn\) additional operations to combine results:

\[

T(n)=2T(n/2)+cn.

\]

The base case, such as \(T(1)=b\), is essential. Without it, the recurrence does not determine actual running times.

3. First-Order Recurrences and Iteration

Consider the first-order linear recurrence

\[

a_n=ra_{n-1}+g_n,

\qquad a_0=A.

\]

Repeated substitution gives

\[

a_n=r^nA+r^{n-1}g_1+r^{n-2}g_2+\cdots+rg_{n-1}+g_n.

\]

Equivalently,

\[

a_n=r^nA+\sum_{j=1}^{n}r^{n-j}g_j.

\]

This formula is valid for integer \(n\ge 1\), constant multiplier \(r\), and a specified forcing sequence \(g_j\).

Constant Forcing

If \(g_n=b\), then

\[

a_n=ra_{n-1}+b.

\]

For \(r\ne 1\), the geometric-sum formula gives

\[

a_n=r^nA+b\frac{r^n-1}{r-1}.

\]

An equivalent form is

\[

a_n=r^n\left(A+\frac{b}{r-1}\right)-\frac{b}{r-1}.

\]

If \(r=1\), the recurrence becomes \(a_n=a_{n-1}+b\), so

\[

a_n=A+nb.

\]

The case \(r=1\) must be treated separately because the expression with denominator \(r-1\) is undefined.

Worked Example 1: Iteration

Solve

\[

a_n=2a_{n-1}+3,

\qquad a_0=4.

\]

Here \(r=2\), \(b=3\), and \(A=4\). Therefore,

\[

a_n=2^n(4)+3\frac{2^n-1}{2-1}

=4\cdot2^n+3(2^n-1)

=7\cdot2^n-3.

\]

Checking the first terms: \(a_1=11\), and the formula gives \(7(2)-3=11\); \(a_2=25\), and the formula gives \(7(4)-3=25\).

4. Homogeneous Linear Recurrences and Characteristic Equations

Consider a second-order homogeneous recurrence

\[

a_n=pa_{n-1}+qa_{n-2}.

\]

To find solutions of the form \(a_n=\lambda^n\), substitute:

\[

\lambda^n=p\lambda^{n-1}+q\lambda^{n-2}.

\]

Dividing by \(\lambda^{n-2}\), when \(\lambda\ne0\), gives the characteristic equation

\[

\lambda^2-p\lambda-q=0.

\]

Its roots determine the form of the sequence.

More generally, for

\[

a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k},

\]

the characteristic polynomial is

\[

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

\]

Distinct Real Roots

If the second-order characteristic equation has distinct roots \(r_1\) and \(r_2\), then

\[

a_n=C_1r_1^n+C_2r_2^n.

\]

The constants \(C_1,C_2\) are determined by the two initial conditions.

Repeated Roots

If a root \(r\) has multiplicity two, the independent solutions are \(r^n\) and \(nr^n\). Thus,

\[

a_n=(C_1+C_2n)r^n.

\]

For a root of multiplicity \(m\), the corresponding terms are

\[

r^n,\; nr^n,\; n^2r^n,\ldots,n^{m-1}r^n.

\]

Complex Roots

If the characteristic roots are \(re^{i\theta}\) and \(re^{-i\theta}\), a real-valued solution can be written as

\[

a_n=r^n\bigl(C_1\cos(n\theta)+C_2\sin(n\theta)\bigr).

\]

The magnitude factor \(r^n\) controls growth or decay, while the trigonometric terms describe oscillation.

Worked Example 2: Distinct Roots

Solve

\[

a_n=5a_{n-1}-6a_{n-2},

\qquad a_0=2,

\quad a_1=5.

\]

The characteristic equation is

\[

\lambda^2-5\lambda+6=0=(\lambda-2)(\lambda-3).

\]

Therefore,

\[

a_n=C_1 2^n+C_2 3^n.

\]

Using the initial values:

\[

C_1+C_2=2,

\]

\[

2C_1+3C_2=5.

\]

Subtracting twice the first equation from the second gives \(C_2=1\), so \(C_1=1\). Hence,

\[

\boxed{a_n=2^n+3^n}.

\]

5. Nonhomogeneous Recurrences

For a linear recurrence

\[

L(a_n)=f(n),

\]

the complete solution is

\[

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

\]

where \(a_n^{(h)}\) solves the associated homogeneous recurrence and \(a_n^{(p)}\) is one particular solution of the nonhomogeneous equation.

The method of undetermined coefficients is useful when \(f(n)\) has a standard form, such as a constant, polynomial, exponential, or sinusoidal function. If the proposed particular form overlaps with a homogeneous solution, it must be multiplied by a sufficient power of \(n\).

Worked Example 3: Constant Forcing

Solve

\[

a_n=3a_{n-1}+2,

\qquad a_0=1.

\]

The homogeneous recurrence has solution \(a_n^{(h)}=C3^n\). For a constant forcing term, try \(a_n^{(p)}=K\). Substitution gives

\[

K=3K+2,

\]

so \(K=-1\). Therefore,

\[

a_n=C3^n-1.

\]

Using \(a_0=1\), we obtain \(C-1=1\), hence \(C=2\). Thus,

\[

\boxed{a_n=2\cdot3^n-1}.

\]

6. Generating Functions

The ordinary generating function of a sequence \(a_0,a_1,a_2,\ldots\) is the formal power series

\[

A(x)=\sum_{n=0}^{\infty}a_nx^n.

\]

In discrete mathematics, this may be treated formally, without requiring numerical convergence. When numerical convergence is relevant, the radius of convergence must also be considered.

Generating functions are useful because shifts in a sequence correspond to multiplication by powers of \(x\), and recurrence equations become algebraic equations.

Important identities include

\[

\sum_{n=0}^{\infty}a_{n+1}x^n=\frac{A(x)-a_0}{x},

\]

and

\[

\sum_{n=0}^{\infty}a_{n+2}x^n=\frac{A(x)-a_0-a_1x}{x^2}.

\]

Also, for \(|x|<1\), or formally as a power series,

\[

\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}.

\]

Differentiation gives

\[

\sum_{n=1}^{\infty}nx^n=\frac{x}{(1-x)^2}.

\]

Worked Example 4: Generating Function for a First-Order Recurrence

Solve

\[

a_n=2a_{n-1}+1,

\qquad a_0=0.

\]

Let

\[

A(x)=\sum_{n=0}^{\infty}a_nx^n.

\]

Multiply the recurrence by \(x^n\) and sum for \(n\ge1\):

\[

\sum_{n\ge1}a_nx^n

=2\sum_{n\ge1}a_{n-1}x^n+\sum_{n\ge1}x^n.

\]

Since \(a_0=0\), this becomes

\[

A(x)=2xA(x)+\frac{x}{1-x}.

\]

Therefore,

\[

A(x)(1-2x)=\frac{x}{1-x},

\]

so

\[

A(x)=\frac{x}{(1-x)(1-2x)}.

\]

Partial fractions give

\[

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

\]

Using \(1/(1-cx)=\sum_{n\ge0}c^nx^n\), we obtain

\[

a_n=2^n-1.

\]

This agrees with direct iteration.

7. Fibonacci Numbers as a Generating-Function Model

The Fibonacci sequence is defined by

\[

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

\qquad F_0=0,

\quad F_1=1.

\]

Let \(F(x)=\sum_{n\ge0}F_nx^n\). Summing the recurrence for \(n\ge2\) gives

\[

F(x)-x=xF(x)+x^2F(x).

\]

Hence,

\[

F(x)=\frac{x}{1-x-x^2}.

\]

The denominator is the characteristic polynomial expressed in generating-function form. Its roots are related to the golden ratio \(\varphi=(1+\sqrt5)/2\) and its conjugate \(\psi=(1-\sqrt5)/2\). Consequently,

\[

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

\]

Although this closed form is mathematically useful, direct floating-point computation can lose accuracy for large \(n\). Integer-based dynamic programming or matrix exponentiation is often preferable in software.

8. Asymptotic Growth and Stability

The characteristic root of greatest absolute value usually governs the long-term growth of a constant-coefficient linear recurrence. If the dominant root has magnitude greater than one, the sequence generally grows exponentially; if all roots have magnitude less than one, it generally decays; roots of magnitude one may produce bounded oscillations or polynomially growing terms when repeated.

For the recurrence

\[

a_n=5a_{n-1}-6a_{n-2},

\]

the roots are 2 and 3, so the \(3^n\) term dominates. In the solution \(a_n=2^n+3^n\), the ratio \(a_{n+1}/a_n\) approaches 3.

This analysis is important in algorithmic complexity and numerical stability. A recurrence with a dominant multiplier slightly greater than one can produce large values after many iterations, while a multiplier slightly below one can cause information to fade. In machine learning, repeated state updates in recurrent neural networks exhibit analogous behavior: effective eigenvalues larger than one may lead to exploding gradients, while values smaller than one may contribute to vanishing gradients. The analogy is informative, although neural networks are generally nonlinear and parameter-dependent, so elementary linear recurrence theory is not a complete model of their training dynamics.

9. Applied Case: An Illustrative Cache-Analysis Scenario

Background

Consider an illustrative software service that processes requests in batches. A monitoring team wants to estimate the number of cache entries examined at depth \(n\) in a recursive diagnostic procedure. At each depth, the procedure examines three times the entries examined at the previous depth and adds two fixed metadata checks.

Problem

Let \(a_n\) denote the number of examination operations at depth \(n\). Suppose

\[

a_n=3a_{n-1}+2,

\qquad a_0=1.

\]

The team wants a formula and an interpretation for large \(n\).

Analysis and Solution

The recurrence is first-order linear with constant forcing. From the earlier method,

\[

a_n=C3^n-1.

\]

Using \(a_0=1\), we obtain \(C=2\), so

\[

\boxed{a_n=2\cdot3^n-1}.

\]

At depth 4,

\[

a_4=2(3^4)-1=2(81)-1=161.

\]

Outcome

The dominant factor is \(3^n\), indicating exponential growth. A modest increase in recursion depth therefore creates a substantial operational burden. The model suggests introducing memoization, limiting depth, pruning redundant branches, or replacing exhaustive exploration with a heuristic search.

Learning Points

The recurrence makes the growth mechanism explicit, while the closed form supports capacity planning. However, the model assumes every branch behaves identically and that no cache hit, duplicate elimination, or resource limit changes the process. Measurements should therefore be used to validate the model before operational decisions are made.

10. Computational Methods and Best Practices

A recurrence can often be evaluated in several ways:

• Naive recursion: mirrors the definition but may recompute the same terms many times.
• Memoization: stores previously computed values and is usually efficient for overlapping subproblems.
• Bottom-up dynamic programming: computes values in order and typically uses \(O(n)\) time for a fixed-order recurrence.
• Space optimization: for an order-\(k\) recurrence, only the most recent \(k\) values may be needed, reducing storage to \(O(k)\).
• Matrix exponentiation: represents a fixed-order recurrence as a matrix power and can compute the nth term in \(O(\log n)\) matrix multiplications, subject to the cost of matrix operations.

For example, Fibonacci numbers can be computed using the matrix identity

\[

\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix}

=

\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n}

\begin{pmatrix}1\\0\end{pmatrix}.

\]

The identity is valid for integer \(n\ge0\). Fast exponentiation then reduces the number of matrix multiplications from linear in \(n\) to logarithmic in \(n\).

Best practice includes checking initial conditions, verifying the first few generated terms, identifying dominant growth, and selecting arithmetic types that avoid overflow. In production systems, assumptions and boundary behavior should be documented, and theoretical predictions should be compared with observed data.

11. Limitations and Responsible Use

Elementary recurrence models often assume constant coefficients, regular time steps, complete information, and deterministic behavior. Real systems may contain noise, delays, changing parameters, feedback, missing observations, or resource constraints. A recurrence fit to historical data can fail when the underlying process changes.

In AI and ML applications, recurrence-based forecasts should not be treated as automatically causal. A strong fit does not prove that one variable causes another. Data governance also matters: when sequences represent people, health events, finances, or behavior, privacy, fairness, consent, and security requirements apply. Models used for consequential decisions should be validated across relevant populations and monitored for drift.

Chapter Summary

Recurrence relations define sequences through earlier terms and are fundamental to discrete modeling and algorithm analysis. Initial conditions are required to select a unique sequence. First-order recurrences can be solved by repeated substitution, summation, or geometric-series formulas. Homogeneous constant-coefficient recurrences are solved through characteristic equations; distinct roots produce sums of exponentials, repeated roots introduce polynomial factors in \(n\), and complex roots produce oscillatory solutions. Nonhomogeneous recurrences combine a homogeneous solution with a particular solution.

Generating functions encode sequence terms as coefficients of formal power series. By translating shifts into algebraic expressions, they convert recurrence problems into equations involving power series. Partial fractions then frequently reveal explicit formulas. Dominant characteristic roots describe long-term growth and have implications for algorithmic complexity, stability, and recurrent computational systems. Practical use requires careful modeling, validation, attention to numerical behavior, and awareness of changing real-world conditions.

Key Terms

Recurrence relation: A rule defining sequence terms from earlier terms.

Initial condition: A specified starting value or set of values.

Order: The number of previous terms required by a recurrence.

Linear recurrence: A recurrence in which sequence terms occur only linearly.

Homogeneous recurrence: A linear recurrence with zero forcing term.

Nonhomogeneous recurrence: A recurrence with a nonzero forcing term.

Characteristic equation: The polynomial equation used to solve a homogeneous constant-coefficient recurrence.

Characteristic root: A solution of the characteristic equation.

Repeated root: A characteristic root occurring with multiplicity greater than one.

Particular solution: One solution of a nonhomogeneous recurrence.

General solution: The sum of the homogeneous and particular solutions.

Generating function: A formal power series whose coefficients are sequence terms.

Ordinary generating function: The series \(A(x)=\sum_{n\ge0}a_nx^n\).

Formal power series: A power series manipulated algebraically without requiring convergence.

Dominant root: A characteristic root with greatest absolute value.

Iteration: Repeated substitution of a recurrence into itself.

Memoization: Storing previously computed results to avoid repeated work.

Dynamic programming: Systematic computation using stored subproblem solutions.

Asymptotic growth: The behavior of a sequence as its index becomes large.

Review Questions

Short Answer Questions

1. What information, in addition to a recurrence relation, is normally required to determine a unique sequence?

2. Distinguish between a homogeneous and a nonhomogeneous linear recurrence.

3. What is the characteristic equation of \(a_n=4a_{n-1}-3a_{n-2}\)?

4. Define the ordinary generating function of a sequence.

5. Why does a repeated characteristic root introduce factors involving powers of \(n\)?

Long Answer Questions

1. Solve \(a_n=4a_{n-1}+3\) with \(a_0=2\), and verify the result using the first two terms.

2. Solve \(a_n=7a_{n-1}-12a_{n-2}\), with \(a_0=1\) and \(a_1=5\), using the characteristic-equation method.

3. Explain how generating functions transform a second-order recurrence into an algebraic equation.

4. Compare naive recursion, memoization, bottom-up dynamic programming, and matrix exponentiation for computing recurrence sequences.

5. Discuss the assumptions and limitations involved in using a recurrence to forecast a real operational process.

Analytical / Application Questions

1. A recursive search examines four times as many states at each level and adds five administrative checks. Formulate and solve a recurrence when the initial level examines two states. Interpret the growth.

2. A sequence satisfies \(a_n=2a_{n-1}-a_{n-2}\), with \(a_0=3\) and \(a_1=5\). Use the characteristic roots to determine a closed form and explain its long-term behavior.

3. Design a computational strategy for finding the millionth Fibonacci number. Discuss time complexity, memory, integer-size issues, and why ordinary floating-point Binet evaluation may be unreliable.

Multiple Choice Questions with Answers

Question 1

What additional information is required to determine a unique sequence from a recurrence relation?

A. A generating function only

B. Initial conditions

C. A characteristic root only

D. A probability distribution

Correct Answer: B. Initial conditions

Question 2

Which recurrence is homogeneous?

A. a_n=2a_{n-1}+3

B. a_n=a_{n-1}^2

C. a_n=5a_{n-1}-6a_{n-2}

D. a_n=3n+a_{n-1}

Correct Answer: C. a_n=5a_{n-1}-6a_{n-2}

Question 3

The characteristic equation for a_n=5a_{n-1}-6a_{n-2} is:

A. λ²+5λ+6=0

B. λ²-5λ-6=0

C. λ²-5λ+6=0

D. λ²+5λ-6=0

Correct Answer: C. λ²-5λ+6=0

Question 4

Solve a_n=2a_{n-1}+1 with a_0=0.

A. 2^n+1

B. 2^n-1

C. 2n-1

D. n^2-1

Correct Answer: B. 2^n-1

Question 5

If a characteristic root r has multiplicity two, which form is required for the general solution?

A. C_1r^n+C_2

B. C_1r^n+C_2n^2

C. (C_1+C_2n)r^n

D. C_1\cos(nr)+C_2\sin(nr)

Correct Answer: C. (C_1+C_2n)r^n

Question 6

The ordinary generating function of a sequence a_0,a_1,... is:

A. Σ a_n+n x

B. Σ a_n x^n

C. Π a_n x^n

D. Σ x/a_n

Correct Answer: B. Σ a_n x^n

Question 7

For the recurrence a_n=3a_{n-1}+2 with a_0=1, the closed form is:

A. 3^n+2

B. 2·3^n−1

C. 3n+2

D. 2^n−3

Correct Answer: B. 2·3^n−1

Question 8

What usually determines the dominant long-term growth of a constant-coefficient linear recurrence?

A. The smallest-index initial condition only

B. The characteristic root with greatest absolute value

C. The number of terms already computed

D. The constant term in every case

Correct Answer: B. The characteristic root with greatest absolute value

Question 9

Which computational method stores previously computed values to avoid repeated recursive work?

A. Memoization

B. Random sampling

C. Differentiation

D. Partial factoring

Correct Answer: A. Memoization

Question 10

The generating function for the Fibonacci sequence with F_0=0 and F_1=1 is:

A. 1/(1-x-x²)

B. x/(1-x-x²)

C. x/(1+x+x²)

D. (1-x)/x

Correct Answer: B. x/(1-x-x²)