Recursion and Induction
Imran Shafi
Email: Imran.shafi@umt.edu.pk
Lecture Contents
Principles of Mathematical Induction
Mathematical Induction Formal Definition
Mathematical Induction Examples
Recursion & Recursive Functions
Recursive Set Definitions
Recursive Functions
Recursive Languages
Principle of Mathematical Induction
Principle of Mathematical Induction
If for any statement involving a positive integer n, the
following are true:
1.The statement holds for n=1 (basic step), and
2.Whenever the statement holds for n=k, it must also hold
for n=k+1 (inductive step),
the statement holds for all positive integer n (conclusion)
Mathematical Induction Formally
Let P(n) be a propositional function defined for all positive
integers n. P(n) is true for every positive integer n if
1. Basis Step:
The proposition P(1) is true
2. Inductive Step:
If P(k) is true then P(k + 1) is true for all integers k 1
i.e. k p(k) P(k + 1)
Mathematical Induction Variation
Let P(n) be a propositional function defined for all positive
integers n. P(n) is true for every positive integer n if
1. Basis Step:
The proposition P(n0) is true
2. Inductive Step:
If P(k) is true then P(k + 1) is true for all integers k n0
i.e. k p(k) P(k + 1)
Mathematical Induction: Example
Use Mathematical Induction to prove that
1+2+ 3+⋯+𝑛=
𝑛(𝑛+ 1) for all integers n
Solution:
2 1
Step 1: (prove that theorem is true for n = 1)
Putting n = 1 on both sides
1 = 1(1+1)/2
1=1 hence theorem is true for n = 1
Show that theorem is true for n = k + 1 if it is true for n = k
We assume that theorem is true for n = k i.e.
1+2+3+……+k = k (k+1)/2 is true
Mathematical Induction: Example
Use Mathematical Induction to prove that
𝑛(𝑛+ 1) for all integers n
1+2+ 3+⋯+𝑛=
Solution: 2 1
To prove that theorem is true for n = k+1
We add (k+1)th term on both side of equation i.e.
1+2+3+………+k+(k+1) = k(k+1)/2+(k+1)
= (k(k+1)+2(k+1))/2
= ((k+1)(k+1+1))/2
i.e. n is true for n = k + 1
It proves that theorem must be true for all values of n ϵ N
Mathematical Induction … Exercise … Do it yourself
Use mathematical induction to prove that
1+3+5+…+(2n -1) = n2 for all integers n 1
Mathematical Induction … Exercise … Do it yourself
Use mathematical induction to prove that
1+2+22 + … + 2n = 2n+1 - 1 for all integers n 0
Mathematical Induction … Exercise … Do it yourself
Use Mathematical Induction to prove that
2 2 2 2 𝑛(𝑛+1)(2 𝑛+1) for all integers n
1 +2 +3 +⋯+𝑛 =
6 1
Mathematical Induction … Exercise … Do it yourself
Use Mathematical Induction to prove that
for all integers n
1 1 1 𝑛
+ +⋯+ =
1⋅2 2⋅ 3 𝑛(𝑛+1) 𝑛+1 1
Mathematical Induction … Exercise … Do it yourself
Use Mathematical Induction to prove that
Mathematical Induction … Exercise … Do it yourself
Use Mathematical Induction to prove that
( )( )( ) for all integers n
1 1 1 𝑛 +1
1 − 2 ⋅ 1− 2 ⋯ 1 − 2 =
2 3 𝑛 2 𝑛
2
Mathematical Induction … Exercise … Do it yourself
Use Mathematical Induction to prove that
for all integers n
𝑛
∑ 𝑖 (𝑖 !)=(𝑛+1)! − 1
𝑖 =1 1
Mathematical Induction … Exercise … Do it yourself
Use mathematical induction to prove that 2n < n! for every integer n
with n ≥ 4.
Mathematical Induction … More Exercises
Use mathematical induction to prove the following:
1. n < 2n for all positive integers n.
2. 2n < n! for all n ≥4.
3. n3-n is divisible by 3 for all positive integers n.
4. 7n+2 + 82n+1 is divisible by 57 for every non-negative integer n.
5. 5n - 1 is divisible by 4 for all non-negative integers n.
6. 2n+1 > n+2 for all n ≥1.
Mathematical Induction … More Exercises
Use mathematical induction to prove the following for all positive integer values of n:
LHS RHS
13 + 23 + 33 + … + n3 =
2 + 5 + 8 + … + (3n-1) =
1 · 2 + 2 · 3 + 3 · 4 + · · · + n.(n + 1) =
3n > N2
1 + 4 + 7 + … + (3n-2) =
Recursion & Recursive Functions
A function is defined in terms of itself.
Recursion is an important tool to define sequences, sets, languages
and functions.
A recursive problem is one that has recursive structure i.e. a
repetitive structure
With every recursive call to recursive function the original problem
is reduced
Sets Definition …………
The sequence {an} of positive odd numbers {1, 3, 5, …} is
defined as
an = 2*n+1 for n = 0, 1, 2, 3,…..
Set of integer squares {1, 4, 9, 16,…….} is defined as
an = n2 for n = 1, 2, 3,…..
Set of power of two {1, 2, 4, 8,…….} is defined as
an = 2n for n = 0, 1, 2, 3,…..
Recursive Definitions
The set of positive odd numbers is defined recursively as
a0 = 1
an+1 = an+2 for n = 0, 1,2,3, ………
Set of integer squares is defined recursively as
a0 = 1
an = 2*n+1+ an-1 for n = 0,1,2,3,…..
Set of power of two {1,2,4,8,…….} is defined as
a0 = 1
an = 2* an-1 for n = 0, 1, 2,3,…..
Recursive Definitions
The set of positive odd numbers is defined recursively
as
a0 = 1
an+1 = an+2 for n = 0, 1,2,3, ………
Set of integer squares is defined recursively as
a0 = 1
an = 2*n+1+ an-1 for n = 0,1,2,3,…..
Set of power of two {1,2,4,8,…….} is defined as
a0 = 1
an = 2* an-1 for n = 0, 1, 2,3,…..
Defining Recursive Functions
Use following method to define recursions:
1. Define base case(s)
2. Define recursive cases by using previous cases
Example:
Base cases:
a0=0, a1=1
Recursive cases:
an = an-1 + an-2
Results:
0, 1, 1, 2, 3, 5, 8, ………….
Defining Recursive Functions …. Problems
Define recursively (power=xy where x is real value and y is a
positive integer)
Defining Recursive Functions …. Problems
Define recursively: n!
1, 2, 6, 24, 120, …………
Defining Recursive Functions …. Problems
Define recursively: an
proc a_power_n(a, n){
if n = 0 then return 1
else return a * a_power_n(a, n-1)
}
Defining Recursive Functions …. Problems
Give a recursive algorithm to compute the greatest common
divisor of two non-negative integers a and b such that a < b.
proc gcd(a, b){
if a = 0 then return b
else if b mod a = 0 return a
else return gcd(b mod a, a)
}
Defining Recursive Functions …. Do it yourself
Define the recursive algorithm for linear search problem
Defining Recursive Functions …. Do it yourself
Define the recursive algorithm for binary search problem
Recursive Languages
Alphabet
Regular Expression
Regular Languages
