Chapter 5

Induction and Recursion

MAD101

Ly Anh Duong

duongla3@fe.edu.vn
 Table of Contents
1 Mathematical Induction

▶ Mathematical Induction

▶ Recursive

▶ Recursive Algorithms

▶ Problems
 Introduction
1 Mathematical Induction

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 3 / 65

 Principle of Mathematical Induction
1 Mathematical Induction
To prove that P (n) is true for all positive integers n, where P (n) is a propositional
function, we complete two steps:
• Basis step: We verify that the predicate P (n) is true with some initial values of
n; e.g. P (1), P (2), P (3), . . ..
• Inductive step: Show that the conditional statement P (k) → P (k + 1) is true
for all positive integers k.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 4 / 65

 Examples.
1 Mathematical Induction

1. Prove that:
n(n + 1)
1 + 2 + 3 + .... + n − 1 + n = .
2
2. Conjecture a formula for the sum of the first n positive odd integers. Then
prove your conjecture using the induction method.
3. Prove that:
20 + 21 + .... + 2n = 2n+1 − 1.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 5 / 65

 Solution
1 Mathematical Induction

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 6 / 65

 Solution
1 Mathematical Induction

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 7 / 65

 Solution
1 Mathematical Induction

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 8 / 65

 Strong Induction
1 Mathematical Induction

To prove P(n) is true for all positive integers n, where P(n) is a propositional
function, two steps are performed:
• Basis step: Verifying P (1) is true.
• Inductive step: Show [P (1) ∧ P (2) ∧ ... ∧ P (k)] → P (k + 1) is true for all
k ≥ 1.
Example 1. Prove that if n is an integer greater than 1, then n can be written as
the product of primes.
Example 2. Prove that every amount of postage of 12 cents or more can be
formed using just 4-cents and 5-cents stamps.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 9 / 65

 Solution. Example 1:
1 Mathematical Induction

Let P (n): “n can be written as the product of prime”.

• Basis step:
P (2) = 2
P (3) = 3
P (4) = 4 = 2.2
...
• Inductive step:
— Suppose P (n) is true for all n ≤ k.
— Show P (j) is true with n = k + 1:
(i). If k + 1 is a prime, then P (k + 1) is true.
(ii). If k + 1 is a composite, then k + 1 = ab, 2 ≤ a ≤ b < k + 1. Because a, b < k + 1,
according to hypothesis, a and b can be written as a product of primes. Hence,
k + 1 can be written as a product of primes.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 10 / 65

 Solution. Example 2
1 Mathematical Induction
Let P (n) : “n cents can be formed using just 4-cent and 5-cent stamps”.
• Basis step:
— P (12) is true: 12 = 3.4
— P (13) is true: 13 = 2.4 + 1.5
— P (14) is true: 14 = 1.4 + 2.5
— P (15) is true: 15 = 3.5
— ..................
• Inductive step:
— - Suppose that P (n) holds true with n = k (k > 15). It means that k = 4r + 5s
for some positive integers r and s. Now we need to prove that P (n) also holds
true with n = k + 1.
— - Obviously, we have
k + 1 = (4r + 5s) + (5 − 4) = 4(r − 1) + 5(s + 1)
which finishes the proof.
Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 11 / 65
 Table of Contents
2 Recursive

▶ Mathematical Induction

▶ Recursive

▶ Recursive Algorithms

▶ Problems
 Introduction
2 Recursive

Fibonacci Numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

n 1 2 3 4 5 6 7
Fn 1 1 2 3 5 8 13
1. Find F8 .
2. Find F16 if F18 = 2584, F19 = 4181.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 13 / 65

 Introduction
2 Recursive

Fibonacci Numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

n 1 2 3 4 5 6 7
Fn 1 1 2 3 5 8 13
1. Find F8 .
2. Find F16 if F18 = 2584, F19 = 4181.
Solution. F8 = 21; F16 = 987.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 13 / 65

 Introduction
2 Recursive

Fibonacci Numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .

n 1 2 3 4 5 6 7
Fn 1 1 2 3 5 8 13
1. Find F8 .
2. Find F16 if F18 = 2584, F19 = 4181.
Solution. F8 = 21; F16 = 987.
In general, this infinite sequence can be formulated by: F1 = F2 = 1 and

Fn = Fn−1 + Fn−2 ∀ n ≥ 3.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 13 / 65

 Introduction
2 Recursive

Sometimes, it is difficult to define an object explicitly. However, it may be easy to

define this object in terms of itself. This process is called recursion.
Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 14 / 65
 Recursive definition of Fibonacci numbers
2 Recursive

Example. (Fibonacci Numbers)

Procedure Fibo(n: positive integer)
if n = 1 or n = 2
return 1
else
return Fibo(n − 1)+Fibo(n − 2)

What is output value if input n = 5?

• Basis step F1 = 1, F2 = 1
• Recursive step Fn = Fn−1 + Fn−2 , n ≥ 3.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 15 / 65

 Recursively Defined Functions (hàm đệ quy)
2 Recursive

We use two steps to define a function with the set of non negative integers as its
domain:
• Basis step: Specify the value of the function at zero.
• Recursive step: Give a rule for finding its value at an integer from its values
at smaller assessment integers.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 16 / 65

 Example.
2 Recursive

Give an algorithm to find pseudo-random numbers if

x1 = 1, xn+1 = (3xn + 17) mod 22 ∀n ≥ 1.

Procedure pseudo(n: positive integer)

if n = 0
return 1
else
return (3*pseudo(n − 1)+17) mod 22

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 17 / 65

 Example.
2 Recursive

Procedure sum(n:n ≥ 1, integer)

if n = 1
return 1
else
return sum(n − 1)+n
If input n = 4, what is the value of output?

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 18 / 65

 Example.
2 Recursive

Procedure sum(n:n ≥ 1, integer)

if n = 1
return 1
else
return sum(n − 1)+n
If input n = 4, what is the value of output?
1 + 2 + 3 + 4 = 10

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 18 / 65

 Example.
2 Recursive

Procedure sum(n: n ≥ 1, integer)

if n = 1
return 5
else
return sum(n − 1)

If input n = 4, what is the value of output?

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 19 / 65

 Example.
2 Recursive

Procedure sum(n: n ≥ 1, integer)

if n = 1
return 5
else
return sum(n − 1)

If input n = 4, what is the value of output? −→ 5.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 19 / 65

 Example.
2 Recursive

Find the recursive algorithm of f (n) = 5n + 1, n ≥ 1

• Basis step: f (1) = 6
• Recursive step: f (n) = f (n − 1) + 5
Hence, the algorithm:
Procedure f(n: n ≥ 1, integer)
if n = 1
return 6
else
return f(n − 1)+5

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 20 / 65

 Exercises
2 Recursive

1. an = 5n − 2, ∀n ≥ 1.
2. an = n, ∀n ≥ 1.
3. f (n) = 1 + 2 + 3 + ... + n, ∀n ≥ 1.
4. f (n) = 2022, ∀n ≥ 1.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 21 / 65

 Examples.
2 Recursive

1. Give the recursive definition of an (where a is a non zero real number and n is
a non negative integer).
2. Suppose that f is defined recursively by f (0) = 3, f (n + 1) = 2f (n) + 3. Find
f (1), f (2), f (3) and f (4).
n
3. Give a recursive definition of ak .
P
k=0

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 22 / 65

 Solutions
2 Recursive
1. Let f (n) = an . Then it yields
f (0) = 1, f (n) = af (n − 1) ∀n ≥ 1.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 23 / 65

 Solutions
2 Recursive
1. Let f (n) = an . Then it yields
f (0) = 1, f (n) = af (n − 1) ∀n ≥ 1.
E.g. Choose a = 2, we have
f (1) = 2.f (0) = 2.1 = 2
f (2) = 2f (1) = 2.2 = 4
f (3) = 2f (2) = 2.4 = 8
f (4) = 2f (3) = 2.8 = 16
f (5) = 2f (4) = 2.16 = 32
f (6) = 2f (5) = 2.32 = 64
........................

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 23 / 65

 Solutions
2 Recursive

2.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 24 / 65

 Solutions
2 Recursive
3. The first part of the recursive definition is
0
ak = a0 .
X

k=0

The second part is

n+1 n
!
ak = + ak+1 .
X X
ak
k=0 k=0
n
Thus, we can set f (n) = ak and obtain the following recursive relation
X

k=0

f (n + 1) = f (n) + an+1 for any n ≥ 0.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 25 / 65

 Recursively Defined Sets (tập đệ quy)
2 Recursive

,→ Recursive definitions of sets have two parts:

• Basis step: An initial collection of elements is specified.
• Recursive step: Rules for forming new elements in the set from those already
known to be in the set are provided.

Examples.
Consider the subset S of the set of integers recursively defined by:
• Basis step: 3 ∈ S
• Recursive step: If x ∈ S and y ∈ S, then x + y ∈ S.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 26 / 65

 Recursively Defined Sets (tập đệ quy)
2 Recursive

,→ Recursive definitions of sets have two parts:

• Basis step: An initial collection of elements is specified.
• Recursive step: Rules for forming new elements in the set from those already
known to be in the set are provided.

Examples.
Consider the subset S of the set of integers recursively defined by:
• Basis step: 3 ∈ S
• Recursive step: If x ∈ S and y ∈ S, then x + y ∈ S.
→ S = {3, 6, 9, 12, 15, 18, 21, ...}

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 26 / 65

 Examples.
2 Recursive

Find S if
a. 1 is in S, if x is in S then x + 1 and x + 2 are in S;
b. 1 is in S, if x is in S then x + 3 is in S;
c. 1, 2 are in S, if x is in S then x + 3 is in S.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 27 / 65

 Examples.
2 Recursive

Find S if
a. 1 is in S, if x is in S then x + 1 and x + 2 are in S;
b. 1 is in S, if x is in S then x + 3 is in S;
c. 1, 2 are in S, if x is in S then x + 3 is in S.
Solution.
a. S = {1, 2, 3, ...};

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 27 / 65

 Examples.
2 Recursive

Find S if
a. 1 is in S, if x is in S then x + 1 and x + 2 are in S;
b. 1 is in S, if x is in S then x + 3 is in S;
c. 1, 2 are in S, if x is in S then x + 3 is in S.
Solution.
a. S = {1, 2, 3, ...};
b. S = {1, 4, 7, 10, ...};

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 27 / 65

 Examples.
2 Recursive

Find S if
a. 1 is in S, if x is in S then x + 1 and x + 2 are in S;
b. 1 is in S, if x is in S then x + 3 is in S;
c. 1, 2 are in S, if x is in S then x + 3 is in S.
Solution.
a. S = {1, 2, 3, ...};
b. S = {1, 4, 7, 10, ...};
c. S = {1, 2, 4, 5, 7, 8, ...}.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 27 / 65

 Examples.
2 Recursive

Give a recursive definition of each of these sets:

a. A = {2, 5, 8, 11, 14, . . .};
b. B = {. . . , −5, −1, 3, 7, 10, . . .};
c. C = {3, 12, 48, 192, 768, . . .}.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 28 / 65

 Examples.
2 Recursive

Give a recursive definition of each of these sets:

a. A = {2, 5, 8, 11, 14, . . .};
b. B = {. . . , −5, −1, 3, 7, 10, . . .};
c. C = {3, 12, 48, 192, 768, . . .}.
Solution.
a. 2 ∈ A, x ∈ A → x + 3 ∈ A;

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 28 / 65

 Examples.
2 Recursive

Give a recursive definition of each of these sets:

a. A = {2, 5, 8, 11, 14, . . .};
b. B = {. . . , −5, −1, 3, 7, 10, . . .};
c. C = {3, 12, 48, 192, 768, . . .}.
Solution.
a. 2 ∈ A, x ∈ A → x + 3 ∈ A;
b. 3 ∈ B, x ∈ B → x + 4 ∈ B ∧ x − 4 ∈ B;

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 28 / 65

 Examples.
2 Recursive

Give a recursive definition of each of these sets:

a. A = {2, 5, 8, 11, 14, . . .};
b. B = {. . . , −5, −1, 3, 7, 10, . . .};
c. C = {3, 12, 48, 192, 768, . . .}.
Solution.
a. 2 ∈ A, x ∈ A → x + 3 ∈ A;
b. 3 ∈ B, x ∈ B → x + 4 ∈ B ∧ x − 4 ∈ B;
c. 3 ∈ C, x ∈ C → 4x ∈ C.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 28 / 65

 P∗
The set of strings
2 Recursive

P∗
The set of strings over the fintite set (alphabet) is defined recursively by
P
P∗
• BASIS STEP: λ ∈ (where λ is the empty string containing no symbols).
P∗ P∗
• RECURSIVE STEP: If w ∈ and x ∈ , then wx ∈ .
P

Examples.
1. = {1}
P
P∗
• P∗0 = {λ}
• P∗1 = {λ, 1}
• P2∗ = {λ, 1, 11}
• P∗3 = {λ, 1, 11, 111}
• 4 = {λ, 1, 11, 111, 1111}
........................

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 29 / 65

 Examples.
2 Recursive

2. = {0, 1}
P
P∗
• P0 = {λ}
∗
• P1 = {λ, 0, 1}
∗
• P2 = {λ, 0, 1, 00, 01, 10, 11}
∗
• 3 = {λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111}
........................

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 30 / 65

 Strings Concatenation (nối các xâu)
2 Recursive

Example. The concatenation of w1 = abra and w2 = cadabra is

w1 w2 = abracadabra.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 31 / 65

 Length of a String
2 Recursive

The length of a string can be recursively defined by

• l(λ) = 0
P∗
• l(wx) = l(w) + 1 if w ∈ and x ∈ .
P

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 32 / 65

 Table of Contents
3 Recursive Algorithms

▶ Mathematical Induction

▶ Recursive

▶ Recursive Algorithms

▶ Problems
 Definition
3 Recursive Algorithms

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

instance of the same problem with smaller input.
Examples. Find 4!
0! = 1
1! = 1.0! = 1.1 = 1
2! = 2.1! = 2.1 = 2
3! = 3.2! = 3.2 = 6
4! = 4.3! = 4.6 = 24

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 34 / 65

 Recursive Algorithm for Computing n!
3 Recursive Algorithms

Example. Using the algorithm to compute 5!

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 35 / 65

 Solution.
3 Recursive Algorithms

• 5! = 5.4!
• 4! = 4.3!
• 3! = 3.2!
• 2! = 2.1!
• 1! = 1.0!
• 0! = 1(Basis step)
• Recursive steps
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 36 / 65
 Recursive Algorithm for Computing an
3 Recursive Algorithms

Example. Find output value if a = 3, n = 4

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 37 / 65

 Solution.
3 Recursive Algorithms

• 34 = 3.33
• 33 = 3.32
• 32 = 3.31
• 31 = 3.30
• 30 = 1 (Basis step)
• Recursive step
31 =3
32 =9
33 = 27
34 = 81

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 38 / 65

 Recursive Algorithm for Computing gcd(a,b)
3 Recursive Algorithms

Example. Find output value if input a = 5, b = 8

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 39 / 65

 Solution.
3 Recursive Algorithms

• gcd(5, 8) = gcd(8 mod 5, 5) = gcd(3, 5)

• gcd(3, 5) = gcd(5 mod 3, 3) = gcd(2, 3)
• gcd(2, 3) = gcd(3 mod 2, 2) = gcd(1, 2)
• gcd(1, 2) = gcd(2 mod 1, 1) = gcd(0, 1)
• return 1
Hence, gcd(5, 8) = 1

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 40 / 65

 Recursive Modular Exponentiation
3 Recursive Algorithms

Example. Find 25 mod 3

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 41 / 65

 Solution.
3 Recursive Algorithms

b = 2, n = 5, m = 3
n = 5 odd: mpower(2, 5, 3) = (mpower(2, 2, 3)2 mod m.2 mod m) mod m
n = 2 even: mpower(2, 2, 3) = (mpower(2, 1, 3)2 ) mod 3
n = 1 odd: mpower(2, 1, 3) = (mpower(2, 0, 3)2 mod 3.2 mod 3) mod 3
mpower(2, 0, 3) = 1 (Basis step)
Recursive steps
• mpower(2, 1, 3) = 2
• mpower(2, 2, 3) = 1
• mpower(2, 5, 3) = 2
Hence, 25 mod 3 = 2

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 42 / 65

 Recursive Linear Search Algorithm
3 Recursive Algorithms

Example. List all the steps used to search for 9 in the sequence 2, 3, 4, 5, 6, 8, 9, 11

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 43 / 65

 Solution.
3 Recursive Algorithms

2 3 4 5 6 8 9 11
a1 a2 a3 a4 a5 a6 a7 a8
→ i = 1, j = 8, x = 9
• a1 = 9(!) → Search(2, 8, 9)
• a2 = 9(!) → Search(3, 8, 9)
• a3 = 9(!) → Search(4, 8, 9)
• a4 = 9(!) → Search(5, 8, 9)
• a5 = 9(!) → Search(6, 8, 9)
• a6 = 9(!) → Search(7, 8, 9)
• a7 = 9(ok)
• return 7

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 44 / 65

 Recursive Binary Search Algorithm
3 Recursive Algorithms

Example. To search for 19 in the list 1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 45 / 65

 Solution.
3 Recursive Algorithms

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16

→ i = 1, j = 16, x = 19
• m := ⌊(1 + 16)/2⌋ = 8 : 19 > 10 ∧ 16 > 8 → binary search(9, 16, 19)
• m := ⌊(9 + 16)/2⌋ = 12 : 19 > 16 ∧ 16 > 12 → binary search(13, 16, 19)
• m := ⌊(13 + 16)/2⌋ = 14 : 19 = 19
• return 14

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 46 / 65

 Recursive Merge Sort
3 Recursive Algorithms

Example. Use the merge sort to put the terms of the list 8, 2, 4, 6, 9, 7, 10, 1, 5, 3 in
increasing order.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 47 / 65

 Recursive Merge Sort
3 Recursive Algorithms

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 48 / 65

 Recursive Merge Sort
3 Recursive Algorithms

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 49 / 65

 Recursive Merge Sort two sorted lists
3 Recursive Algorithms

Example. Merging the Two Sorted Lists 2, 3, 5, 6 and 1, 4.

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 50 / 65

 Recursive Merge Sort two sorted lists
3 Recursive Algorithms

Theorem. The number of comparisons needed to merge sort a list with n elements
is O(nlogn).

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 51 / 65

 Table of Contents
4 Problems

▶ Mathematical Induction

▶ Recursive

▶ Recursive Algorithms

▶ Problems
 Mathematical Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 53 / 65

 Mathematical Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 54 / 65

 Mathematical Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 55 / 65

 Strong Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 56 / 65

 Strong Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 57 / 65

 Recursive Definitions and Structural Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 58 / 65

 Recursive Definitions and Structural Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 59 / 65

 Recursive Definitions and Structural Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 60 / 65

 Recursive Definitions and Structural Induction
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 61 / 65

 Recursive Algorithms
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 62 / 65

 Recursive Algorithms
4 Problems

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 63 / 65

5. Consider the following algorithm:

Procedure F (a1 , a2 , . . . , an : integers )

if n = 0 return 0
else return an + F (a1 , a2 , . . . , an−1 )

Find F (1, 3, 5) and F (1, 2, 3, 5, 9).

Ly Anh Duong Chapter 5 Induction and Recursion duongla3@fe.edu.vn 64 / 65

 Q&A
Thank you for listening!