�Discrete Mathematics (MAD101)

Lecture notes by PhuongVTM

(phuongvtm11@fe.edu.vn/

minhphuong1105.sphn@gmail.com)

​

Chapter 4:

Induction & Recursion

• Mathematical Induction
• Strong Induction
• Recursive definition
• Structural Induction
• Recursive Algorithm

​

4. 1 Mathematical Induction

• Principle of Induction:

Let P(n) be a propositional function. To prove that P(n) is true, for all n ≥ 0

We need to do 2 steps:

• Basic step: Prove that P(n) is true for the initial value n=0 (depending on the problem)
• Induction step:

Assume that P(k) is true (induction hypothesis)

Prove that P(k+1) is also true.

• Conclusion : By induction, P(n) is true for all n ≥ 0

4. 1 Mathematical Induction

• Example 1: Prove that

1+ 3+ 5+...+ (2n-1) = n² , for all n ≥ 1

Proof: Let P(n): 1+ 3+ 5+...+ (2n-1) = n²

• Basic step: for n = 1, then the left hand side is 1 = 1² , so P(1) is true
• Induction step: Suppose that for some k ≥ 1, P(k) is true. We will prove that P(k+1) is also true, which means : 1+ 3+ 5+...+ (2(k+1)-1) = (k+1)².

Indeed, to prove P(k+1) is true, we compute

1+ 3+ 5+...+ (2(k+1)-1)= 1+ 3+ 5+...+ (2k-1) + (2(k+1)-1)

By induction hypothesis, P(k) is true, meaning that 1+ 3+ 5+...+ (2k-1) = k². So

1+ 3+ 5+...+ (2(k+1)-1) = k² +(2(k+1)-1) = k² +2k +1 =(k+1)².

Hence P(k+1) is also true.

• Conclusion: By Induction principle, P(n) is true for all n ≥ 1.

4. 1 Mathematical Induction

• Example 2: Prove that

n³- n is divisible by 3, for all n ≥ 0

​

• Example 3: Prove that for n > 5, we have n! > 2ⁿ.
• Initial value: n= ?

​

​

4. 1 Mathematical Induction

• Example 4:

​

4. 2 Strong Induction

• Principle of Strong Induction:

Let P(n) be a propositional function. To prove that P(n) is true, for all n ≥ 0

We need to do 2 steps:

• Basic step: Prove that P(n) is true for initial values n=0, n=1, n=2 (depending on the problem)
• Induction step:

Assume that P(0), P(1), …, P(k) are all true (induction hypothesis)

Prove that P(k+1) is also true.

• Conclusion : By induction, P(n) is true for all n ≥ 0

4. 2 Strong Induction

• Example 1: Let (aₙ) be sequence:

a₀=1 , a₁= 3 , aₙ₊₁= 2aₙ -aₙ₋₁ , ∀n ≥ 1.

Prove that ∀n ≥ 0, aₙ= 2n+1.

Proof:

​

4. 2 Strong Induction

• Example 1: Let (aₙ) be sequence:

a₀=1 , a₁= 3 , aₙ₊₁= 2aₙ -aₙ₋₁ , ∀n ≥ 1.

Prove that ∀n ≥ 0, aₙ= 2n+1.

Proof:

• Basic step: Verify for initial values

n=0, a₀=1 = 2.0 +1 (true)

n= 1, a₁= 3 = 2.1 +1 (true)

• Inductive step: Suppose that k ≥ 3 and for each 0 ≤ j≤ k, aⱼ= 2j+1.

We prove that aₖ₊₁= 2(k+1)+1.

Indeed, by inductive hypothesis: aₖ = 2.k +1 and aₖ₋₁= 2.(k-1)+1, so

aₖ₊₁= 2aₖ -aₖ₋₁ = 2.(2k+1)- (2.(k-1) +1) =2k+ 3= 2(k+1) +1.

• Conclusion: Thus aₖ₊₁= 2(k+1)+1 and we can conclude by induction principle that

∀n ≥ 1, aₙ= 2n+1.

4. 2 Strong Induction

• Exercise 2: (Fibonacci)

Let (fₙ) be sequence that is defined as followed:

f₀= 0, f₁=1 fₙ₊₁ = fₙ +fₙ₋₁

Prove that for all n ≥ 2,

​

​

​

4. 2 Strong Induction

• Example 3: Prove that there is always possible to change any amount of n ≥ 12 using two coins of values 3 and 5.

Proof: We use strong induction

​

4. 2 Strong Induction

• Example 3: Prove that there is always possible to change any amount of n ≥ 12 using two coins of values 3 and 5.

Proof: We use strong induction

• Basic step:

n= 12= 4.3, so n can be changed using 4 coins 3

n= 13 = 2.5 +1.3, so n can be changed using 2 coins 5 and 1 coin 3

n= 14= 1.5 +3.3, so n can be changed using 1 coin 5 and 3 coins 3

• Induction step: suppose that for all 14 ≤ i ≤ k, there is always possible to change i using 2 coins 3 and 5. We need to prove that k+1 can also be changed : indeed, we see that

k+1= 3+(k-2)

Now, since 14 ≤ k, 12 ≤ (k-2) <k , by induction hypothesis (k-2) can be changed : (k-2)= x.3 +y.3

This implies: k+1 = 3+ (k-2) = 3+ x.3 +y.5 =(x+1).3 + y.5, so (k+1) can be changed using (x+1) coins 3 and y coins 5.

Conclusion: By induction principle, there is always possible to change any amount of n ≥ 12 using 2 coins of values 3 and 5 !

4. 2 Strong Induction

• Remark: In the example 3, n≥ 12 and the reason for which we need to check the Basic step for n=12,13,14 is that we reduced the input (k+1) by writing

(k+1)= 3+(k-2).

so, to be able to use induction hypothesis, k-2 must be greater than or equal to 12, which means k ≥ 14. That is why n= 12,13, 14 are initial values !

​

Question: How many initial values for which we need to check at the Basic step if we write (k+1)= 5 +(k-4) ?

​

• Your turn: Induction or Strong Induction?
• Prove that 7ⁿ- 1 is divisible by 3 for all integer n >0
• Prove that every integer n>0 can be factorized into product of primes.

4. 1 Mathematical Induction

• Example 4:

​

4.3 Recursive Definition

Use:

• to define a function that can be computed itself recursively
• help using structural induction to prove results about the function.
• Recursive Definition Function
• Basic step: define initial values: f(0) =a₀
• Recursive step: Give a rule/ a formula to compute f(n) from f(n-1), f(n-2)...
• Example 1: Let f(0)= 3 and ∀n ≥ 0, f(n+1)= f(n) +3

Find f(1), f(2),..., f(4), and f(n) ?

​

• Example 2: Give a recursive definition for the following sequences
• xₙ= 6. 11ⁿ for all n ≥ 0
• yₙ= (-1)ⁿ for all n ≥ 0
• ​

​

4.3 Recursive Definition

Answer:

1. x₀ = 6.11⁰= 6

to determine a recursive relation for xₙ, note that:

xₙ= 6. 11ⁿ= 6. 11ⁿ⁻¹ .11 =11.xₙ₋₁, so a recursive definition for the sequence xₙ is

x₀=6 and xₙ = 11.xₙ₋₁ for n ≥ 1

• yₙ= (-1)ⁿ = (-1).(-1)ⁿ⁻¹= (-1).yₙ₋₁ —-> recursive definition for yₙ is

y₀=1 and yₙ = - yₙ₋₁ for n ≥ 1

• we have:

zₙ = 1+2+3+...(n-1)+ n and zₙ₋₁= 1+2+3+...+(n-1), so

zₙ - zₙ₋₁ = (1+2+3+...(n-1)+ n) - (1+2+3+...+(n-1))= n, which implies zₙ = zₙ₋₁ +n

recursive definition for zₙ is : z₁ = 1 (initial value) and zₙ = zₙ₋₁ +n (n > 1)

4.3 Recursive Definition

• Exercise: Give a recursive definition for the following sequences:
• xₙ = n² -2n +3 (n ≥ 0)
• yₙ = 4.3ⁿ⁺² + 2

​

• Example 3: Let f(0)= 1 and f(n)= 2f(n-1)+1, for all n>0. What is general formula for f(n)?

Answer:

The recursive idea helps to reduce the input n to lower and lower inputs :

f(n)= 2f(n-1)+1

= 2 [2.f(n-2)+1] +1 = 2²f(n-2) +2 +1

= 2²[2.f(n-3) +1]+2 +1 = 2³f(n-3) +2² +2 +1

= …

= 2ⁿ.f(0) +2ⁿ⁻¹ + 2ⁿ⁻² +...+ 2 +1

= 2ⁿ +2ⁿ⁻¹ + 2ⁿ⁻² +...+ 2 +1 = (2ⁿ⁺¹ - 1)/(2-1) = 2ⁿ⁺¹ - 1

Conclusion: general formula for f(n) is f(n)= 2ⁿ⁺¹ - 1 (n ≥ 0).

Recall:

rⁿ +r ⁿ⁻¹+...+r+ 1 = (rⁿ⁺¹ -1)/ (r-1)

( r≠ 1)

4.3 Recursive Definition

• Exercise: Find general formula for the following sequence
• a₀= 3 and aₙ = aₙ₋₁ + 3 (n>0)
• b₁= 2 and bₙ= 5bₙ₋₁ (n>1)
• x₀= 1 and xₙ = xₙ₋₁ + n+1 (n>0)
• y₀= 1 and yₙ = 2xₙ₋₁ + 1 (n>0)

​

4.3 Recursively Defined Sets

• Use:
• To represent a set: list all elements of a set (in a certain order)
• To define a (recursive) function on a recursively defined sets.
• To be able to use (general) induction for proving properties
• How to do ?
• Basic step: given some initial elements (generators)
• Recursive step: give a rule to generate the other elements of the set from initial elements
• Example: Give a recursive definition for

S= {3,6, 9, 12….}= the set of all positive multiples of 3

• Basic step: 3 ∈ S
• Recursive step: if x ∈ S and y ∈ S, then x+y ∈ S

4.3 Recursively Defined Sets

• Example: Give a recursive definition of the following sets:
• The set S₁ of all integer that are divisible by 3
• The set S₂ of all positive integer that are not divisible by 3

​

​

4.3 Recursively Defined Sets

• Example: Give a recursive definition of the following sets:
• The set S₁ of all integer that are divisible by 3
• The set S₂ of all positive integer that are not divisible by 3

Answer:

1. Basic step: 0 ∈ S

Recursive step: If x ∈ S, then (x+3) ∈ S and (x-3) ∈ S.

• Basic step: 1, 2 ∈ S

Recursive step: If x ∈ S, then (x+3) ∈ S.

​

​

4.3 Recursively Defined Sets

• Generating strings:
• Let ∑ be the set of alphabet (containing letters or numbers, or both)

The set ∑* of strings over ∑ can be defined recursively

• Basic step: w ∈ ∑*, for all w ∈ ∑
• Recursive step: if s ∈ ∑* and w ∈ ∑, then sw ∈ ∑*

Example: ∑= {0,1}

2. Length of strings:
1. l(w)= 1 for each w ∈ ∑
2. if s ∈ ∑* and w ∈ ∑ , then l(sw)= l(s)+1
3. Reverse:
1. r(w)= w, for each w ∈ ∑
2. if s ∈ ∑* and w ∈ ∑, then r(sw)= wr(s).

4.4 Structural Induction (quy nạp tổng quát)

Induction Structure: Proving properties for recursively defined sets

Recursive definition of a set provides an order/structure on this set, so that we can use induction principle:

To prove a property (P) is true for all elements of a recursively defined set (S):

• Basic step: verify (P) for generators (initial elements) // kiểm tra (P) thoả mãn cho các phần tử sinh (phần tử ban đầu)
• Induction step:

Assume that an element x ∈ S has property (P) // giả sử phần tử x ∈ S có tính

chất (P)

Prove that the next element (the element generated by x) also has property (P)

// chứng minh phần tử tiếp theo (phần tử “sinh" ra bởi x) cũng có tính chất (P)

4.4 Structural Induction (quy nạp tổng quát)

Induction Structure: Proving properties for recursively defined sets

• Example 1: The set S is defined recursively as
• 1, 2 ∈ S
• If x ∈ S, then x +3 ∈ S

Show that for any element x ∈ S, x is not divisible by 3

​

4.4 Structural Induction (quy nạp tổng quát)

Induction Structure: Proving properties for recursively defined sets

• Example 1: The set S is defined recursively as
• 1, 2 ∈ S
• If x ∈ S, then x +3 ∈ S

Show that for any element x ∈ S, x is not divisible by 3

Answer:

• Basic step: we see directly that the initial elements 1, 2 are not divisible by 3
• Induction step: assume that an element x ∈ S is not divisible by 3, then the next element (x+3) is also not divisible by 3 (otherwise (x+3)- 3= x is divisible by 3, contradiction !)

By induction principle, we conclude that for any x ∈ S, x is not divisible by 3 !

4.4 Structural Induction (quy nạp tổng quát)

Induction Structure: Proving properties for recursively defined sets

• Example 2: Let S be the set of ordered pairs of integers defined recursively by
• (0,0) ∈ S
• If (a,b) ∈ S, then (a+2, b+3) ∈ S
• List 5 elements of S
• Show that if (a,b) ∈ S, then 5 | (a+b)

4.4 Structural Induction (quy nạp tổng quát)

Induction Structure: Proving properties for recursively defined sets

• Example 3: Let S be the set of positive integers defined by

Basis step: 5 ∈ S.

Recursive step: If n∈S, then 3n∈ S and n² ∈S.

1. Show that if n ∈ S, then n ≡ 5 (mod 10).
2. Show that there exists an integer m ≡ 5 (mod 10) that does not belong to S.

4.4 Structural Induction (quy nạp tổng quát)

Induction over pairs of integers

• Example 1: Let a₀,₀= 1

​

​

​

​

​

4.5 Structural Induction

QUIZ

1. Given the set S defined as follows
1. 1 ∈ S
2. If x ∈ S and y ∈ S, then x+y ∈ S

What is S ?

1. The set of even positive integers
2. The set of even integers
3. The set of positive integers
4. The set of positive multiple of 3

2. The sequence g(n) is defined as follows

g(0)=0 , g(1)= 1, g(n+1)= g(n) +g(n-1) (mod 3)

Find g(6) ? A. 8 B. 2 C. 3 D. 4

4.5 Structural Induction

QUIZ

3. What can be the recursive definition of the set S of all even positive integers?

1. 0 ∈ S, 2 ∈ S and if x ∈ S and y ∈ S, then x+y ∈ S
2. 0 ∈ S and if x ∈ S and y ∈ S, then x+y ∈ S
3. 2 ∈ S and if x ∈ S and y ∈ S, then x+y ∈ S
4. 2 ∈ S and if x ∈ S then x+2 ∈ S

4. Let a₁,₁ = 5 and

​

​

What is the general formula of aₘ,ₙ

1. 5+ 2m B. 5+ 2n C. 5+2(m+n) D. 1+ 2(m+n)

4.5 Structural Induction

QUIZ

5. Does this recursive definition produce a well-defined function on N?

​

F(n)=1+F(n−2) for n≥2 and F(1)=0.

4.5 Recursive Algorithm

(nguồn: runestone.academy)

4.5 Recursive Algorithm

• Definition: An algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input
• Examples
• Computing n! :

Procedure factorial( n: non-negative integer)

If n=1 then return 1

Else return n. factorial (n-1)

Example: 4! = 4. 3! = 4. 3. 2! = 4.3. 2. 1! = 4.3.2.1 = 24.

4.5 Recursive Algorithm

b) Euclid algorithm

​

procedure gcd(a ≥ b: positive integers)

if b=0, then return a

else return gcd(b, a mod b)

{ output is gcd(a,b) }

​

Question:

Compute gcd(36,14).

What is the base case ?

Which recursive relation is used ?

• Recursion and Iteration (Đệ quy và Lặp)

Example: Compute the Fibonacci sequence

1. Recursive algorithm: b) Iterative algorithm

Using function calls Using loops

(+): easy to understand, easy for implementation (+) require less computations than recursive one

(-) require more computations than iterative one (-) may become tricky and hard to interpret

Which algorithm is recursive, iterative ?

4.5 Recursive Algorithm

• Merge Sort (sắp xếp gộp)

4.5 Recursive Algorithm

• Merge Sort (sắp xếp gộp)

Review:

procedure bubble sort (a₁,a₂,…,a_n :real numbers with n ≥ 2)

for i:= 1 to n-1

for j:=1 to n- i

if a_j > a_j+1 then interchange a_j and a_j+1

{a₁,a₂,…,a_n are sorted}

​

worst case: how many comparisons ?

(n-1)+(n-2)+...+1+0= n(n-1)/2 comparisons ~ O(n^2)

(similarly for Insertion Sort) ~ O(n^2)

​

​

4.5 Recursive Algorithm

• Merge Sort (sắp xếp gộp): 2 bước: chia và gộp lại

Bước 1: Chia L thành 2 dãy con (phân đôi)

​

4.5 Recursive Algorithm

Bước 2: sắp xếp gộp lại

Idea: to merge two sorted lists, T and U, into a single sorted list, we compare the first elements of two lists at each step and place the smaller of the two items we are viewing into the output list L.

​

4.5 Recursive Algorithm

Example: To merge 2 list {2, 3, 5, 6} and {1, 4}

​

4.5 Recursive Algorithm

Question: How many comparisons needed?

4.5 Recursive Algorithm

• Theorem:

The number of comparisons performed by the algorithm MergeSort for an input list of length n is O(n.log₂(n)).

​