Recurrence Relations and Counting: Solving Linear Recurrences

We present the method of characteristic equations for solving linear recurrences with constant coefficients, treat the case of repeated roots, discuss nonhomogeneous recurrences, establish the equivalence with generating functions, and introduce matrix exponentiation and the Kitamasa method.

Folio Official

March 1, 2026

1 Linear Recurrences with Constant Coefficients

Definition 1 (Linear recurrence with constant coefficients).

A sequence

(a_{n})_{n \geq 0}

satisfies a homogeneous linear recurrence of order $d$ with constant coefficients if there exist constants

c_{1}, \dots, c_{d}

(with

c_{d} \neq = 0

) such that

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d} (n \geq d) .

Definition 2 (Characteristic equation).

The characteristic equation of the above recurrence is

t^{d} - c_{1} t^{d - 1} - c_{2} t^{d - 2} - \dots - c_{d} = 0.

2 The Case of Distinct Roots

Theorem 3.

If the characteristic equation has

d

distinct roots

r_{1}, r_{2}, \dots, r_{d}

, then the general solution of the recurrence is

a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots + α_{d} r_{d}^{n},

where

α_{1}, \dots, α_{d}

are constants determined by the initial conditions.

Proof.

We verify that

a_{n} = r^{n}

is a solution if and only if

r^{d} = c_{1} r^{d - 1} + \dots + c_{d}

, which is precisely the characteristic equation. Since the recurrence is linear, any linear combination of solutions is again a solution. The

d

free constants are uniquely determined by

d

initial conditions, which is guaranteed by the nonvanishing of the Vandermonde determinant

\prod_{i < j} (r_{j} - r_{i}) \neq = 0

. □

3 The Case of Repeated Roots

Theorem 4.

If a root

r

of the characteristic equation has multiplicity

m

, then

r^{n}, n r^{n}, n^{2} r^{n}, \dots, n^{m - 1} r^{n}

are all solutions of the recurrence.

Proof.

The cleanest proof uses OGFs. Factor the characteristic polynomial as

p (t) = (t - r)^{m} q (t)

. In the partial fraction decomposition of

A (x) = g (x) / p (1/ x) x^{d}

, the factor

(1 - r x)^{- m}

appears. Since

[x^{n}] (1 - r x)^{- j} = (j - 1 n + j - 1) r^{n}

is a polynomial in

n

of degree

j - 1

multiplied by

r^{n}

, the

j = 1, \dots, m

contributions yield solutions of the form

n^{j - 1} r^{n}

(up to scalar multiples). □

4 Nonhomogeneous Recurrences

Definition 5 (Nonhomogeneous linear recurrence).

A recurrence of the form

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d} + f (n)

is called nonhomogeneous. The function

f (n)

is the nonhomogeneous term.

Theorem 6.

The general solution of a nonhomogeneous recurrence is the sum of the general solution of the associated homogeneous recurrence and one particular solution of the nonhomogeneous recurrence.

Proof.

a_{n}

and

a_{n}^{'}

are two solutions of the nonhomogeneous recurrence, then their difference

a_{n} - a_{n}^{'}

satisfies the homogeneous recurrence. Hence every solution of the nonhomogeneous equation takes the form "particular solution + homogeneous solution." □

Example 7.

Solve

a_{n} = 2 a_{n - 1} + 3^{n}

with

a_{0} = 1

. The characteristic equation

t - 2 = 0

gives the homogeneous solution

α \cdot 2^{n}

. Trying a particular solution of the form

a_{n} = C \cdot 3^{n}

, we find

C \cdot 3^{n} = 2 C \cdot 3^{n - 1} + 3^{n}

, which simplifies to

C (3 - 2) = 3

, so

C = 3

. The general solution is

a_{n} = α \cdot 2^{n} + 3^{n + 1}

. Applying

a_{0} = 1

gives

α + 3 = 1

, hence

α = - 2

. The answer is

a_{n} = - 2^{n + 1} + 3^{n + 1}

5 Equivalence with Generating Functions

Remark 8.

The OGF of a sequence satisfying a linear recurrence of order

d

with constant coefficients is a rational function

A (x) = P (x) / Q (x)

, where

de g Q = d

and

de g P \leq d - 1

. Conversely, any sequence whose OGF is a rational function satisfies such a recurrence. Partial fraction decomposition and the characteristic equation approach are two perspectives on the same underlying operation.

6 Matrix Exponentiation

Theorem 9.

The

n

-th term of a linear recurrence

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d}

of order

d

can be computed using the

n

-th power of a

d \times d

matrix:

a_{n} a_{n - 1} ⋮ a_{n - d + 1} = c_{1} 10 ⋮ 0 c_{2} 010 \dots \dots \dots ⋱ \dots c_{d - 1} 001 c_{d} 00 ⋮ 0^{n - d + 1} a_{d - 1} a_{d - 2} ⋮ a_{0} .

Proof.

This is immediate once the recurrence is rewritten as a vector transition: denoting the companion matrix by

M

, we have

v_{n} = M v_{n - 1} = M^{n - d + 1} v_{d - 1}

. □

Remark 10 (Complexity of matrix exponentiation).

The matrix power

M^{n}

can be computed in

O (d^{3} lo g n)

operations via repeated squaring. This is highly efficient when

d

is small and

n

is very large.

Remark 11 (The Kitamasa method).

The Kitamasa method computes

a_{n}

for a linear recurrence of order

d

O (d^{2} lo g n)

time, or

O (d lo g d lo g n)

when combined with the Fast Fourier Transform. The key idea is to compute

x^{n} mod p (x)

, where

p (x)

is the characteristic polynomial, using repeated squaring in polynomial arithmetic, and then to express

a_{n}

as a linear combination of

a_{0}, \dots, a_{d - 1}

Combinatorics Discrete Mathematics Textbook Recurrence Relations Matrix Exponentiation

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Recurrence Relations and Counting: Solving Linear Recurrences

Folio Official

March 1, 2026

1 Linear Recurrences with Constant Coefficients

Definition 1 (Linear recurrence with constant coefficients).

A sequence

(a_{n})_{n \geq 0}

satisfies a homogeneous linear recurrence of order $d$ with constant coefficients if there exist constants

c_{1}, \dots, c_{d}

(with

c_{d} \neq = 0

) such that

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d} (n \geq d) .

Definition 2 (Characteristic equation).

The characteristic equation of the above recurrence is

t^{d} - c_{1} t^{d - 1} - c_{2} t^{d - 2} - \dots - c_{d} = 0.

2 The Case of Distinct Roots

Theorem 3.

If the characteristic equation has

d

distinct roots

r_{1}, r_{2}, \dots, r_{d}

, then the general solution of the recurrence is

a_{n} = α_{1} r_{1}^{n} + α_{2} r_{2}^{n} + \dots + α_{d} r_{d}^{n},

where

α_{1}, \dots, α_{d}

are constants determined by the initial conditions.

Proof.

We verify that

a_{n} = r^{n}

is a solution if and only if

r^{d} = c_{1} r^{d - 1} + \dots + c_{d}

, which is precisely the characteristic equation. Since the recurrence is linear, any linear combination of solutions is again a solution. The

d

free constants are uniquely determined by

d

initial conditions, which is guaranteed by the nonvanishing of the Vandermonde determinant

\prod_{i < j} (r_{j} - r_{i}) \neq = 0

. □

3 The Case of Repeated Roots

Theorem 4.

If a root

r

of the characteristic equation has multiplicity

m

, then

r^{n}, n r^{n}, n^{2} r^{n}, \dots, n^{m - 1} r^{n}

are all solutions of the recurrence.

Proof.

The cleanest proof uses OGFs. Factor the characteristic polynomial as

p (t) = (t - r)^{m} q (t)

. In the partial fraction decomposition of

A (x) = g (x) / p (1/ x) x^{d}

, the factor

(1 - r x)^{- m}

appears. Since

[x^{n}] (1 - r x)^{- j} = (j - 1 n + j - 1) r^{n}

is a polynomial in

n

of degree

j - 1

multiplied by

r^{n}

, the

j = 1, \dots, m

contributions yield solutions of the form

n^{j - 1} r^{n}

(up to scalar multiples). □

4 Nonhomogeneous Recurrences

Definition 5 (Nonhomogeneous linear recurrence).

A recurrence of the form

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d} + f (n)

is called nonhomogeneous. The function

f (n)

is the nonhomogeneous term.

Theorem 6.

The general solution of a nonhomogeneous recurrence is the sum of the general solution of the associated homogeneous recurrence and one particular solution of the nonhomogeneous recurrence.

Proof.

a_{n}

and

a_{n}^{'}

are two solutions of the nonhomogeneous recurrence, then their difference

a_{n} - a_{n}^{'}

satisfies the homogeneous recurrence. Hence every solution of the nonhomogeneous equation takes the form "particular solution + homogeneous solution." □

Example 7.

Solve

a_{n} = 2 a_{n - 1} + 3^{n}

with

a_{0} = 1

. The characteristic equation

t - 2 = 0

gives the homogeneous solution

α \cdot 2^{n}

. Trying a particular solution of the form

a_{n} = C \cdot 3^{n}

, we find

C \cdot 3^{n} = 2 C \cdot 3^{n - 1} + 3^{n}

, which simplifies to

C (3 - 2) = 3

, so

C = 3

. The general solution is

a_{n} = α \cdot 2^{n} + 3^{n + 1}

. Applying

a_{0} = 1

gives

α + 3 = 1

, hence

α = - 2

. The answer is

a_{n} = - 2^{n + 1} + 3^{n + 1}

5 Equivalence with Generating Functions

Remark 8.

The OGF of a sequence satisfying a linear recurrence of order

d

with constant coefficients is a rational function

A (x) = P (x) / Q (x)

, where

de g Q = d

and

de g P \leq d - 1

6 Matrix Exponentiation

Theorem 9.

The

n

-th term of a linear recurrence

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d}

of order

d

can be computed using the

n

-th power of a

d \times d

matrix:

a_{n} a_{n - 1} ⋮ a_{n - d + 1} = c_{1} 10 ⋮ 0 c_{2} 010 \dots \dots \dots ⋱ \dots c_{d - 1} 001 c_{d} 00 ⋮ 0^{n - d + 1} a_{d - 1} a_{d - 2} ⋮ a_{0} .

Proof.

This is immediate once the recurrence is rewritten as a vector transition: denoting the companion matrix by

M

, we have

v_{n} = M v_{n - 1} = M^{n - d + 1} v_{d - 1}

. □

Remark 10 (Complexity of matrix exponentiation).

The matrix power

M^{n}

can be computed in

O (d^{3} lo g n)

operations via repeated squaring. This is highly efficient when

d

is small and

n

is very large.

Remark 11 (The Kitamasa method).

The Kitamasa method computes

a_{n}

for a linear recurrence of order

d

O (d^{2} lo g n)

time, or

O (d lo g d lo g n)

when combined with the Fast Fourier Transform. The key idea is to compute

x^{n} mod p (x)

, where

p (x)

is the characteristic polynomial, using repeated squaring in polynomial arithmetic, and then to express

a_{n}

as a linear combination of

a_{0}, \dots, a_{d - 1}

Combinatorics Discrete Mathematics Textbook Recurrence Relations Matrix Exponentiation

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Recurrence Relations and Counting: Solving Linear Recurrences

1 Linear Recurrences with Constant Coefficients

2 The Case of Distinct Roots

3 The Case of Repeated Roots

4 Nonhomogeneous Recurrences

5 Equivalence with Generating Functions

6 Matrix Exponentiation

Share your expertise with the world

More from Folio Official

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Recurrence Relations and Counting: Solving Linear Recurrences

1 Linear Recurrences with Constant Coefficients

2 The Case of Distinct Roots

3 The Case of Repeated Roots

4 Nonhomogeneous Recurrences

5 Equivalence with Generating Functions

6 Matrix Exponentiation

Share your expertise with the world

More from Folio Official

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs