Mathematics for Computing – Discrete Mathematics

1
Lecturer: Dr Nguyen Hieu Thao
Email: [Link]@[Link]

Lecture Notes: Induction, Recursion and

Recurrence
(Week 6)1

An induction proof of a universally quantified statement ∀n ∈ Z>0 : P (n) is based on the

principle of mathematical induction: Suppose that (i) P (1) is true (the base case), and (ii)
for all n ≥ 1, if P (n) is true, then P (n + 1) is true (induction step). Then P (n) is true for every
positive integer n.

Example. Prove that the following equation is true for every positive integer n:
n(n + 1)(2n + 1)
12 + 22 + 32 + · · · + n2 = (1)
6
Proof.
• Base case. For n = 1, (1) becomes
1(1 + 1)(2 + 1)
12 = ,
6
which is true.

• Induction hypothesis. Assume that (1) is true for all positive integers n ≤ k (k ≥ 1).

• Induction step. It suffices to show that (1) is true for n = k + 1. That is,
(k + 1)(k + 2)(2k + 3)
12 + 22 + · · · + k 2 + (k + 1)2 = .
6
Indeed,
k(k + 1)(2k + 1)
LHS = + (k + 1)2 (induction hypothesis for n = k)
6
k(k + 1)(2k + 1) + 6(k + 1)2
=
6
(k + 1)(2k 2 + 7k + 6)
=
6
(k + 1)(k + 2)(2k + 3)
= = RHS.
6
That is, the equation (1) is also true for n = k + 1, and hence the proof is complete. 

1 Most of the content of this document is taken from the book [1].
2

A recursive function is a function that invokes itself. Recursive functions are the mathe-
matical foundation of recursion, which is a powerful, elegant, and natural way to solve a large
class of problems using a divide-and-conquer technique in which the problem is decomposed
into subproblems of the same type as the original problem. Each subproblem, in turn, is decom-
posed further until the process yields subproblems that can be solved in a straightforward way.
Finally, solutions to the subproblems are combined to obtain a solution to the original problem.

(a) The factorial function f (n) = n! can be written ‘in terms of itself’ as follows:

f (1) = 1, f (n) = n · f (n − 1), (∀n ≥ 2).

(b) The Tower of Hanoi puzzle consists of three rods (A, B and C) and a number of disks
(say, n) of pairwise different diameters, which can slide onto any rod. The puzzle begins
with the disks stacked on one rod (say, A) in order of decreasing size, the smallest at the
top. The objective of the puzzle is to move the entire stack to the last rod (say, C), obeying
the following rules:

(i) Only one disk may be moved at a time.

(ii) Each move consists of taking the upper disk from

one of the stacks and placing it on top of another
stack or on an empty rod.

(iii) No disk may be placed on top of a disk that is Figure 1: The Tower of Hanoi
puzzle with 8 disks (Wikipedia).
smaller than it.

Solution. Let us define R = {A, B, C} and the set of movements

M = {A → B, A → C, B → A, B → C, C → A, C → B}

and let M ∗ be the sets of all strings on M .

We construct a recursive function H : Z+ × R × R → M ∗ that solves the puzzle as follows:

if R1 6= R2 ,
(
R1 → R2
H(1, R1 , R2 ) =
ε (the null string) if R1 = R2 ,

H(n − 1, R1 , R3 ) + R1 → R2 + H(n − 1, R3 , R2 ) if R1 6= R2 ,
(
H(n, R1 , R2 ) = (∀n ≥ 2).
ε if R1 = R2 ,

In the above, R1 , R2 ∈ R and whenever R1 6= R2 , R3 = R \ {R1 , R2 } and ‘+’ is the

concatenation of strings. Then H(n, A, C) yields a solution to the puzzle with n disks.
 3

(c) Find the largest value of a finite sequence of integers. Given a finite sequence of integers
s of length n ≥ 2, let s− denote the sequence of length n − 1 obtained from s by removing
the last term sn of s. The following recursive function returns the largest value of the
sequence s.
if |s| = 1,
(
s
M (s) =
max {M (s− ), sn } if |s| = n > 1.

(d) The closest-pair problem. Write a recursive function finding a nearest pair from n points.

A recurrence relation for the sequence a0 , a1 , . . . , is an equation that relates an to certain

of its predecessors a0 , a1 , . . ., an−1 . Initial conditions for the sequence a0 , a1 , . . . are explicitly
given values for a finite number of the terms of the sequence. To solve a recurrence relation
involving the sequence a0 , a1 , . . . , is to find an explicit formula for the general term an .

(a) The Fibonacci sequence {fn } is defined by the recurrence relation

f1 = 1, f2 = 1, fn = fn−1 + fn−2 for n ≥ 3.

(b) A linear homogeneous recurrence relation of order k with constant coefficients is a

recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k , ck 6= 0.

Theorem. Consider a second-order, linear homogeneous recurrence relation with constant coef-
ficients below:
an = c1 an−1 + c2 an−2 .

If r1 and r2 are distinct roots of the quadratic equation

r2 − c1 r − c2 = 0,

then
an = br1n + dr2n , n = 0, 1, . . . .
for some constants b, d determined by the initial conditions.
4

Example. Solve the following recurrence relation with the given initial conditions:

an = 2an−1 + 8an−2 with a0 = 4 and a1 = 10.

Solution. We first solve the equation:

t2 − 2t − 8 = 0 ⇔ t1 = 4 ∨ t2 = −2.

Then the recurrence sequence takes the following form:

an = b · 4n + d · (−2)n

where b and d are constant numbers. To find b and d, we then use the initial conditions:
( (
a0 = b + d = 4 b=3
⇔
a1 = 4b − 2d = 10 d = 1.

Hence,
an = 3 · 4n + (−2)n .


References
1. Johnsonbaugh, R.: Discrete Mathematics - Eighth Edition. Pearson Education, New York
(2018).