Mad111 Chap 4

Discrete Mathematics 1
Chapter 4: Induction and Recursions
Department of Mathematics
The FPT university
TrungDT (FUHN) MAD111 Chapter 4 1/1

Chapter 4: Introduction

Topics covered:

Topics covered:
4.1 Mathematical Induction

Topics covered:

4.2 Strong Induction and Well-Ordering

Topics covered:

4.3 Recursive Definitions and Structural Induction

Topics covered:

4.4 Recursive Algorithms

Topics covered:

4.5 Program Correctness


Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

Proof by Induction:

Proof by Induction:
1: Prove that P(1) is true.

Proof by Induction:

2: (Inductive hypothesis) Assume that P(k) is true for some positive
integer k.

Proof by Induction:

integer k.
3: Prove that P(k + 1) is true.

Proof by Induction:

integer k.
4: Conclusion: P(n) is true for all positive integers n.

Proof by Induction:

integer k.

Example 1. Prove that for all positive integers n we have
n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6

n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 2. Prove that n3 − n is divisible by 6 for all integers n ≥ 1.

n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 3. Prove that 2n > n2 for all integers n > 4.

n(n + 1)(2n + 1)
12 + 2 2 + 3 2 + · · · + n 2 =
6
Example 3. Prove that 2n > n2 for all integers n > 4.
Example 4. Let n be a positive integer. Prove that every checkerboard of

size 2n × 2n with one square removed can be titled by triominoes.


Problem. Prove that P(n) is true for all n = 1, 2, . . .

Proof by Strong Induction.



2: (Induction hypothesis) Assume that P(1), P(2), . . . , P(k) are all true
for some k ≥ 1.


for some k ≥ 1.
3: Prove that P(k + 1) is also true.


for some k ≥ 1.


for some k ≥ 1.
Example 1. Prove that every integer greater than 1 can be written as a

product of primes.


for some k ≥ 1.
Example 1. Prove that every integer greater than 1 can be written as a

product of primes.
Example 2. Prove that every postage of 12 cents or more can be formed

using only 4-cent and 5-cent stamps.

Well-Ordering

Well-Ordering
The validity of the Principle of Mathematical Induction follows from the

Well-Ordering property of the set of non-negative integers.

Well-Ordering

Well-Ordering

Well-Ordering

Well-Ordering
Any nonempty set of non-negative integers has a least element.


The Fibonacci {Fn }, n = 1, 2, . . . is defined as follows:

F0 = 0, F1 = 1,

F0 = 0, F1 = 1, and

F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..

F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..
This definition is called recursive definition.

F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n = 2, 3, . . ..
This definition is called recursive definition.

Example 1. Find the nth term of the sequence {xn } defined by recursive
definition:

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .
Example 2. Give a recursive definition for the sequence {xn }, n = 1, 2 . . .

whose nth term is:

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

whose nth term is:
(a) xn = 7 ∗ 5n+1

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n
(d) xn = 2n − 6

definition:
(a) x1 = 5, xn = 3xn−1 for n = 2, 3, . . .

(b) x0 = 2, xn = xn−1 + 1 for n = 1, 2, . . .

whose nth term is:
(a) xn = 7 ∗ 5n+1
(b) xn = n!
(c) xn = (−1)n
(d) xn = 2n − 6

Recursively Defined Sets and Structures

Example 1. Determine the set S defined by:

Basic step: 3 ∈ S

Basic step: 3 ∈ S
Recursive step: If x, y ∈ S then x + y ∈ S

Basic step: 3 ∈ S
Example 2.

Basic step: 3 ∈ S
Example 2.
(a) Give a recursive definition for the set of positive integers that are not
divisible by 3

Basic step: 3 ∈ S
Example 2.
divisible by 3
(b) Give a recursive definition for the set of integers that are not divisible
by 3

Basic step: 3 ∈ S
Example 2.
divisible by 3
(b) Give a recursive definition for the set of integers that are not divisible
by 3

TrungDT (FUHN) MAD111 Chapter 4 10 / 1
Example 3. Recursive definition for the set of full binary trees.

Basic step: A single vertex is a full binary tree.


Recursive step: If T1 and T2 are two full binary trees then there is a
full binary tree, denoted by T1 .T2 , consisting of a root r together
with edges connecting this root to the root of the left subtree T1 and
the root of the right subtree T2 .


Recursive step: If T1 and T2 are two full binary trees then there is a
full binary tree, denoted by T1 .T2 , consisting of a root r together
with edges connecting this root to the root of the left subtree T1 and
the root of the right subtree T2 .

Example 4. Give a recursive definition for:

(a) Leaves of full binary trees.


(b) Height of full binary trees.


(b) Height of full binary trees.

Structural Induction

Let S be a set defined recursively.

Let S be a set defined recursively. To prove that a property P is true for

all elements of S we can use structural induction.


Basic step: Prove that P is true for elements of S defined in the basic
step.


Basic step: Prove that P is true for elements of S defined in the basic
step.
Recursive step: Show that if the property P is true for the elements
used to construct new elements in the recursive step of the definition
of S, then the property P is also true for these new elements.

Example 1.

Example 1. Let T be a full binary tree with the number of vertices n(T )
and the number of leaves l(T ). Prove that n(T ) = 2l(T ) − 1.

and the height h(T ). Prove that n(T ) ≤ 2h(T )+1 − 1.

and the height h(T ). Prove that n(T ) ≤ 2h(T )+1 − 1.

Generalized Induction

Example.

Example.
Given the sequence {am,n } defined recursively as follows:

Example.
a0,0 = 0, and

Example.
a0,0 = 0,
and
am−1,n + 1 if n = 0 v m > 0,
am,n =
am,n−1 + n if n > 0

Example.
a0,0 = 0,
and
am−1,n + 1 if n = 0 v m > 0,
am,n =
am,n−1 + n if n > 0
Prove that am,n = m + n(n + 1)/2 for all m, n ≥ 0.


An algorithm is called recursive if it solves a problem by reducing it to an

instance of the same problem with smaller input


Example 1. A recursive algorithm that computes 5n for n ≥ 0.


Example 1. A recursive algorithm that computes 5n for n ≥ 0.
Procedure power (n: non-negative)

if n = 0 then power (0) := 1
else power (n) := power (n − 1) ∗ 5

Example 2. Write a recursive algorithm to compute n!.

Example 3. Write a recursive algorithm to compute the greatest common

divisor of two non-negative integers.


Example 4. Express the linear search algorithm by a recursive procedure .


Example 5. Express the binary search algorithm by a recursive procedure.


Example 5. Express the binary search algorithm by a recursive procedure.

Recursion and Iteration

Problem. Write a recursive algorithm and an iteration algorithm to

compute the nth Fibonacci number, and compare their complexity via the
number of additions used.




Procedure Iterative Fib (n)
if n = 0 then y := 0
else
x:=0
y:=1
for i := 1 to n − 1 do
z:=x+y
x:=y
y:=z
Print(y )


Procedure Iterative Fib (n) Procedure Fib (n)
if n = 0 then y := 0 if n = 0 then Fib(0) := 0
else else if n = 1 then Fib(1) := 1
x:=0 else
y:=1 Fib(n) := Fib(n − 1) + Fib(n − 2)
for i := 1 to n − 1 do
z:=x+y
x:=y
y:=z
Print(y )

Merge Sort Algorithm

Procedure mergesort (L = a1 , a2 , . . . , an )
if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
L := merge(mergesort(L1 ), mergersort(L2 ))
Print (L)

if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
Print (L)
Theorem

if n > 1 then
m := bn/2c
L1 = a1 , a2 , . . . , am
L2 = am+1 , am+2 , . . . , an
Print (L)
Theorem
The number of comparisons needed to merge sort a list of n elements is
O(n log n).


A program is called correct if it produces correct output for every possible

input.


input. A proof that a program is correct consists of two steps:


Prove that if the program terminates then the answer is correct (this
part is called partial correctness).


Prove that if the program terminates then the answer is correct (this
part is called partial correctness).
Show that the program always terminates.

A program segment S is called partially correct with respect to the initial
assertion p and the final assertion q, if whenever p is true for the input
values and after S terminates then q is true for the output values.

The notation p{S}q (Hoare triple) indicates that the program segment S
is (partially) correct with respect to the initial assertion p and the final
assertion q.

assertion q.
Example. The program segment
y:=2
z:=x+y
is

assertion q.
y:=2
z:=x+y
is
correct with respect to the initial assertion p : x = 1 and the final

assertion q : z = 3

assertion q.
y:=2
z:=x+y
is
correct with respect to the initial assertion p : x = 1 and the final

assertion q : z = 3
is not correct with respect to the initial assertion p : x < 5 and the
final assertion q : z > 10

Rules of Inference for Condition Statements

Consider a program segment


if condition then
S

if condition then
S
To verify the correctness of this program with respect to the initial

assertion p and the final assertion q we use the following rule of inference:

if condition then
S

(p∧ condition){S}q
(p ∧ ¬ condition) → q
∴ p{if condition then S}q



if condition then
S1
else
S2

if condition then
S1
else
S2


if condition then
S1
else
S2

(p∧ condition){S1 }q
(p ∧ ¬ condition) {S2 }q
∴ p{if condition then S1 else S2 }q

Loop Invariants

Loop Invariants
Consider the program segment

Loop Invariants
while condition
S

Loop Invariants
while condition
S
To develope a rule of inference for this type of program, we must choose a

statement that remains true each time S is executed.

Loop Invariants
while condition
S

statement that remains true each time S is executed. Such a statement is
called a loop invariant.

Loop Invariants
while condition
S

If a loop invariant p is chosen then the rule of inference for this program
segment is:

Loop Invariants
while condition
S

segment is:
(p∧ condition){S}p
∴ p{while condition then S} (¬ condition ∧p)

Loop Invariants
while condition
S

segment is:
(p∧ condition){S}p
∴ p{while condition then S} (¬ condition ∧p)

Example 1. Given the program segment:

i := 1
factorial := 1
while i < n
begin
i := i + 1
factorial := factorial ∗ i
end

i := 1
factorial := 1
while i < n
begin
i := i + 1
end
A loop invariant is p : (factorial = i!) ∧ (i ≤ n).

i := 1
factorial := 1
while i < n
begin
i := i + 1
end
A loop invariant is p : (factorial = i!) ∧ (i ≤ n). Therefore when the

program terminates we obtain

i := 1
factorial := 1
while i < n
begin
i := i + 1
end

p ∧ ¬ condition = (factorial = i!) ∧ (i = n),

i := 1
factorial := 1
while i < n
begin
i := i + 1
end

p ∧ ¬ condition = (factorial = i!) ∧ (i = n), then factorial = n!.

Example 2. Find a loop invariant for the program segment

Example 2. Find a loop invariant for the program segment
power := 1
i := 1
while i ≤ n
begin
power := power ∗ x
i := i + 1
end

Mad111 Chap 4

Uploaded by

Copyright:

Available Formats

Mad111 Chap 4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mad111 Chap 4

Uploaded by

Copyright:

Available Formats

Discrete Mathematics 1

Chapter 4: Induction and Recursions

TrungDT (FUHN) MAD111 Chapter 4 1/1

TrungDT (FUHN) MAD111 Chapter 4 2/1

TrungDT (FUHN) MAD111 Chapter 4 2/1

4.1 Mathematical Induction

TrungDT (FUHN) MAD111 Chapter 4 2/1

4.1 Mathematical Induction

TrungDT (FUHN) MAD111 Chapter 4 2/1

4.1 Mathematical Induction

TrungDT (FUHN) MAD111 Chapter 4 2/1

4.1 Mathematical Induction

TrungDT (FUHN) MAD111 Chapter 4 2/1

4.1 Mathematical Induction

TrungDT (FUHN) MAD111 Chapter 4 2/1

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 3/1

Problem. Prove that the statement P(n) is true for all n = 1, 2, . . .

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 3/1

TrungDT (FUHN) MAD111 Chapter 4 4/1

TrungDT (FUHN) MAD111 Chapter 4 4/1

Example 3. Prove that 2n > n2 for all integers n > 4.

TrungDT (FUHN) MAD111 Chapter 4 4/1

Example 3. Prove that 2n > n2 for all integers n > 4.

Example 4. Let n be a positive integer. Prove that every checkerboard of

TrungDT (FUHN) MAD111 Chapter 4 4/1

TrungDT (FUHN) MAD111 Chapter 4 5/1

Problem. Prove that P(n) is true for all n = 1, 2, . . .

TrungDT (FUHN) MAD111 Chapter 4 5/1

Problem. Prove that P(n) is true for all n = 1, 2, . . .

Proof by Strong Induction.

TrungDT (FUHN) MAD111 Chapter 4 5/1

Problem. Prove that P(n) is true for all n = 1, 2, . . .

Proof by Strong Induction.

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 5/1

Problem. Prove that P(n) is true for all n = 1, 2, . . .

Proof by Strong Induction.

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 5/1

Problem. Prove that P(n) is true for all n = 1, 2, . . .

Proof by Strong Induction.

1: Prove that P(1) is true.

TrungDT (FUHN) MAD111 Chapter 4 5/1