MTL180: Discrete Mathematical Structures 1st Semester, 2024-2025

Lecture 18 — 14/10/2024
Lecturer: Prof Minati De Scribe: Team 18

Scribed by:

1. Keshav Rai (2022MT61968)

2. Viha Singla (2022MT61972)

3. Tushar Goyal (2022MT11266)

4. Harsh Chaudhary (2022MT11261)

5. Aman Divya (2022MT11293)

6. Aayushi Singh (2022MT11955)

7. Rahul (2023MT60686)

8. Mayank Singh (2022MT61985)

1 Overview

In the last lecture, we explored distributing objects into boxes and the recurrence aspects of permu-
tations and combinations. We then delved into recurrence relations, covering foundational examples
like the Fibonacci sequence, factorials, and the Tower of Hanoi problem. Various problems involv-
ing recurrence relations were discussed, such as determining the number of sequences that avoid
specific patterns and computing Catalan numbers for valid parentheses arrangements.

2 Order k Linear Recurrence Relations

An order k linear recurrence relation has the form:

an = c1 an−1 + c2 an−2 + · · · + ck an−k + f (n),

where c1 , c2 , . . . , ck are real numbers and ck ̸= 0. Additionally, it is assumed that ck+i = 0 for
all i > 0. Here, f (n) is a function that determines whether the recurrence is homogeneous or
non-homogeneous:

• If f (n) = 0, the recurrence is homogeneous.

• If f (n) ̸= 0, the recurrence is non-homogeneous.

In this lecture, we focus on solving linear homogeneous recurrence relations.

1
3 Linear Homogeneous Recurrence Relations

3.1 Definition

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence

relation of the form:
an = c1 an−1 + c2 an−2 + · · · + ck an−k ,
where c1 , c2 , . . . , ck are real numbers, and ck ̸= 0.

3.2 Solving Linear Homogeneous Recurrence Relations

The basic approach for solving linear homogeneous recurrence relations is to look for solutions of
the form an = rn , where r is a constant. Substituting into the recurrence relation yields:

rn = c1 rn−1 + c2 rn−2 + · · · + ck rn−k .

Dividing both sides by rn−k and simplifying gives the characteristic equation:

rk − c1 rk−1 − c2 rk−2 − · · · − ck = 0.

The solutions of this equation are called the characteristic roots of the recurrence relation.

3.3 Cases for Characteristic Roots

We distinguish two primary cases based on the nature of the characteristic roots:

3.3.1 Case 1: Distinct Roots

Let c1 , c2 , . . . , ck be real numbers. Suppose that the characteristic equation

rk − c1 rk−1 − · · · − ck = 0

has k distinct roots r1 , r2 , . . . , rk . Then a sequence {an } is a solution of the recurrence relation if
and only if:
an = α1 r1n + α2 r2n + · · · + αk rkn
for n = 0, 1, 2, . . ., where α1 , α2 , . . . , αk are constants.

3.3.2 Case 2: Multiple Roots

If the characteristic equation has repeated roots, say a root r with multiplicity t, then for each such
root, the general solution includes terms of the form:

an = (α1 + α2 n + · · · + αt nt−1 )rn .

2
4 Examples and Solutions

4.1 Example 1: Fibonacci Sequence

fn = fn−1 + fn−2 , f0 = 0, f1 = 1
Characteristic Equation: Substituting fn = rn , we get:

r2 − r − 1 = 0

Solving, we find the roots: √

1± 5
r=
2
√ √
1+ 5 1− 5
Let r1 = 2 and r2 = 2 . The general solution is:

fn = α1 r1n + α2 r2n

Using initial conditions f0 = 0 and f1 = 1, solve for α1 and α2 :

α1 + α2 = 0, α1 r1 + α2 r2 = 1

Thus, α1 = √1 and α2 = − √15 , giving:

5
√ !n √ !n !
1 1+ 5 1− 5
fn = √ −
5 2 2

4.2 Example 2:

hn = 2hn−1 + hn−2 − 2hn−3 , h0 = 1, h1 = 2, h2 = 0

Characteristic Equation:
r3 − 2r2 − r + 2 = 0
Solving for r, we find roots r = 1, −1, 2. The general solution is:

hn = α1 · 1n + α2 · (−1)n + α3 · 2n

Using initial conditions, solve for α1 , α2 , α3 .

4.3 Example 3:

hn = 4hn−1 − 4hn−2 , h0 = 1, h1 = 3
Characteristic Equation: Substituting hn = rn , we get:

r2 − 4r + 4 = 0

Solving for Roots: The characteristic equation can be rewritten as:

(r − 2)2 = 0

3
This root r = 2 has multiplicity 2. For this case, the general solution is:

hn = (α1 + α2 n) · 2n

Using the initial conditions h0 = 1 and h1 = 3, we solve for α1 and α2 :

α1 = 1, 2α1 + 2α2 = 3 =⇒ α2 = 0.5

Thus, the solution is:

hn = (1 + 0.5n) · 2n

4.4 Example 4:

Consider the recurrence relation:

hn = −hn−1 + 3hn−2 + 5hn−3 + 2hn−4 , h0 = 1, h1 = 0, h2 = 1, h3 = 2

Characteristic Equation:
The characteristic equation for this recurrence is:

r4 + r3 − 3r2 − 5r − 2 = 0

Factoring, we get:
(r + 1)3 (r − 2) = 0

Solving for Roots:

From the factored form, we get the following roots:

r = −1 (with multiplicity 3), r=2 (with multiplicity 1)

General Solution:
The general solution for this recurrence relation is:

hn = (α1 + α2 n + α3 n2 )(−1)n + α4 2n

where α1 , α2 , α3 , α4 are constants to be determined.

Using Initial Conditions:
We use the initial conditions h0 = 1, h1 = 0, h2 = 1, and h3 = 2 to solve for α1 , α2 , α3 , α4 .
1. For n = 0:
h0 = (α1 + α2 · 0 + α3 · 02 )(−1)0 + α4 20 = α1 + α4 = 1
α1 + α4 = 1 (Equation 1)

2. For n = 1:

h1 = (α1 + α2 · 1 + α3 · 12 )(−1)1 + α4 21 = −(α1 + α2 + α3 ) + 2α4 = 0

4
 −(α1 + α2 + α3 ) + 2α4 = 0 (Equation 2)

3. For n = 2:

h2 = (α1 + α2 · 2 + α3 · 22 )(−1)2 + α4 22 = α1 + 2α2 + 4α3 + 4α4 = 1

α1 + 2α2 + 4α3 + 4α4 = 1 (Equation 3)

4. For n = 3:

h3 = (α1 + α2 · 3 + α3 · 32 )(−1)3 + α4 23 = −(α1 + 3α2 + 9α3 ) + 8α4 = 2

−(α1 + 3α2 + 9α3 ) + 8α4 = 2 (Equation 4)

Solve for α2 , α3 , α4 using substitution or matrix methods. Once these are found, substitute back
to get α1 .
Final Solution:
Once you have solved for the constants α1 , α2 , α3 , α4 , the general solution is:

hn = (α1 + α2 n + α3 n2 )(−1)n + α4 2n

5 Most General Solution

In cases where the characteristic equation has roots q1 , q2 , . . . , qt with multiplicities s1 , s2 , . . . , st ,

such that s1 + s2 + . . . + st = k (where k is the order of the recurrence relation), the general solution
takes the form:
j −1
t sX
X
an = αji ni qjn
j=1 i=0

For a root qj with multiplicity sj , the terms associated with this root in the general solution are:

(αj0 + αj1 n + αj2 n2 + · · · + αj(sj −1) nsj −1 )qjn

6 Conclusion

In this lecture, we explored methods to solve linear homogeneous recurrence relations with constant
coefficients. We focused on constructing characteristic equations, solving for roots, and finding the
constants for the general solution. We covered examples with distinct roots, repeated roots, and
provided a generalized approach for cases with roots of varied multiplicities.

References
[1] K. H. Rosen, Discrete Mathematics and Its Applications, 7th ed., New York, NY: McGrawHill,
2012