Discrete Mathematics

Unit-II-Chapter-1
Mathematical Reasoning, Induction, and Recursion:
Proof Strategy
 Proof: A Proof is a valid argument that establishes the truth of a mathematical statement, e.g.,
theorem
 A proof can use hypotheses, axioms, and previously proven theorems
 Axiom : A statement that is assumed to be true
 Theorem: A statement that has been proven to be true
 Hypothesis, premise: An assumption (often unproven) defining the structures about which we are
reasoning
 Lemma: A minor theorem used as a stepping-stone to proving a major theorem.
 Corollary: A minor theorem proved as an easy consequence of a major theorem.
 Conjecture: A statement whose truth value has not been proven. (A conjecture may be widely
believed to be true, regardless.)
 Formal proofs: can be extremely long and difficult to follow
 Informal proofs: easier to understand and some of the steps may be skipped, or axioms are not
explicitly stated
BE III Sem-DM - CSE - 2020-21 - MJCET 2
Proof Methods
For proving implications p → q, we have:
Trivial proof: Prove q by itself.
Direct proof: Assume p is true, and prove q.
Indirect proof:
 Proof by Contraposition (¬q → ¬p):Assume ¬q, and prove ¬p.
 Proof by Contradiction: Assume p ∧ ¬q, and show this leads to a contradiction.
(i.e. prove (p ∧ ¬q) → F)
Vacuous proof: Prove ¬p by itself.

BE III Sem-DM - CSE - 2020-21 - MJCET 3

Direct Proof Example
 Definition: An integer n is called odd iff n=2k+1 for some integer k; n is even iff
n=2k for some k.
 Theorem: Every integer is either odd or even, but not both.
 This can be proven from even simpler axioms.
 Theorem: (For all integers n) If n is odd, then n2 is odd.
 Proof:
If n is odd, then n = 2k + 1 for some integer k.
Thus, n2 = (2k + 1) 2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
Therefore n2 is of the form 2j + 1 (with j the integer 2k2 + 2k), thus n2 is odd.

BE III Sem-DM - CSE - 2020-21 - MJCET 4

Indirect Proof Example: Proof by Contraposition
Theorem: (For all integers n) If 3n + 2 is odd, then n is odd.
Proof: p  q  q  p
(Contrapositive: If n is even, then 3n + 2 is even)
Suppose that the conclusion is false, i.e., that n is even.
Then n = 2k for some integer k.
Then 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
Thus 3n + 2 is even, because it equals 2j for an integer j = 3k + 1. So 3n +
2 is not odd.
We have shown that ¬(n is odd) → ¬(3n + 2 is odd),thus its contrapositive
(3n + 2 is odd) → (n is odd) is also true
BE III Sem-DM - CSE - 2020-21 - MJCET 5
Vacuous Proof Example
Show ¬p (i.e. p is false) to prove p → q is true.
Show that P(0) is true when P(n) is “If n>1, then n2>n” and the
domain consists of all integers
“If 0>1, then 02>0”. Since the hypothesis 0>1 is false, the
implication is automatically true

BE III Sem-DM - CSE - 2020-21 - MJCET 6

Trivial Proof Example
Show q (i.e. q is true) to prove p → q is true.
Let P(n) be “If a and b are positive integers with a ≥ b, then an ≥bn
where the domain consists of all integers. Show that the
proposition P(0) is true.
The proposition P(0) is “If a ≥ b, then a0 ≥b0”. Since a0 =b0=1, the
conclusion of P(0) is true, hence the conditional statement P(0) is
true

BE III Sem-DM - CSE - 2020-21 - MJCET 7

Proof by Contradiction
 A method for proving p.
 Assume ¬p, and prove both q and ¬q for some proposition q. (Can be anything!)
 Thus ¬p → (q ∧ ¬q)
 (q ∧ ¬q) is a trivial contradiction, equal to F
 Thus ¬p → F, which is only true if ¬p = F
 Thus p is true

BE III Sem-DM - CSE - 2020-21 - MJCET 8

Rational Number
Definition: The real number r is rational if there exist integers p and
q with q ≠ 0 such that r = p/q.
A real number that is not rational is called irrational.

BE III Sem-DM - CSE - 2020-21 - MJCET 9

Proof by Contradiction Example
 Theorem: Prove that √2 is irrational.
 Proof: Let p be the proposition “√2 is irrational”
 ┐p: √2 is rational, and thus √2= a/b where a and b have no common factors
 Thus by squaring both sides 2=a2/b2, 2b2=a2, and thus a2 is even
 a2 is even and so a is even (can easily show if n2 is even, then n is even). Let a=2c for
some integer c, 2b2=a2=4c2, and thus b2=2c2, and b2 is even
 Since b2 is even, b must be even
 ┐p leads to √2= a/b where a and b have no common factors, and both a and b are even
(and thus a common factor), a contradiction
 That is, the statement “√2 is irrational” is true

BE III Sem-DM - CSE - 2020-21 - MJCET 10

Proof by Contradiction
Proving implication p → q by contradiction
First assume the negation of the conclusion i.e ¬q,
Then use premise p and negation of conclusion to arrive at a
contradiction, i.e. (p∧ ¬q ) → F
p → q ≡ (( p∧ ¬q ) → F)
How does this relate to the proof by contraposition?
Proof by Contraposition (¬q → ¬p):
Assume ¬q, and prove ¬p.
BE III Sem-DM - CSE - 2020-21 - MJCET 11
Proof by Contradiction Example: Implication
Theorem: (For all integers n) If 3n + 2 is odd, then n is odd.
Proof: Let p be “3n+2 is odd” and q be “n is odd”
To construct a proof by contradiction, assume both p and ┐q are both true i.e;
assume that the conclusion is false, i.e., that n is even, and that 3n + 2 is odd.
Since n is even, let n=2k, then 3n+2= = 3(2k) + 2 =6k+2= 2(3k+1). So 3n+2
is even, because it equals 2j for an integer j = 3k + 1. i.e. ┐p,
This contradicts the assumption “3n + 2 is odd”.
Both p and ┐p are true, so we have a contradiction
This completes the proof by contradiction, proving that if 3n + 2 is odd, then
n is odd.

BE III Sem-DM - CSE - 2020-21 - MJCET 12

Forward and Backward Reasoning
 Forward reasoning: Use the premises, axioms, previous theorems in a sequence
of steps to show that the conclusion follows. This also includes indirect proofs.
Issue: We might not know which premise, axiom, or theorem to use to derive the
relevant conclusion.
 Backward reasoning: For proving a statement q, we try to find a statement p
such that p is true and p → q.

BE III Sem-DM - CSE - 2020-21 - MJCET 13

Backward Reasoning Example
 Given two positive integers a and b, their arithmetic mean is (a+b)/2 and their
geometric mean is sqrt ab. when we compare the arithmetic and geometric means of
pairs of distinct positive real numbers, we find that the arithmetic mean is always
greater than the geometric mean.
 Sol: To prove that (a+b)/2> √ab
 ⇒(a+b)2 /4>ab​
 ⇒(a+b) 2 > 4ab
 ⇒a2+2ab+b2>4ab
 ⇒a2 -2ab+b2>0
 ⇒(a-b)2>0
 Because (a-b)2>0 when a!=b, it follows that the final equality is true. Since all the
inequalities are equivalent, it follows that (a+b)/2> √ab when a!=b.
BE III Sem-DM - CSE - 2020-21 - MJCET 14
Proof by Cases Example
Show that there are no solutions in integers x and y of x2+3y2=8
Sol: x2>8 when |x|≥3, and 3y2>8 when |y|≥2. The only values for
x are -2,-1,0,1,2 and for y are -1, 0, 1
So, possible values for x2 are, 0, 1, and 4. The possible values for
3y2 are 0 and 3
No pair of x and y can be solution

BE III Sem-DM - CSE - 2020-21 - MJCET 15

Conjecture: Fermat’s Last Theorem
“The equation x n + y n = z n has no non zero integer solutions for
x, y and z when where n is an integer.”
 Although x 2 + y 2 = z 2 has an infinite number of solutions ,but x n + y n = z n
has no nontrivial whole number solutions for n > 2.
 For example, we can easily check to see that 32 + 42 = 52 and 52 + 122 = 132.
 Try as you may you cannot come up with integer values for x, y, and z such
that
x 3 + y 3 = z 3.

BE III Sem-DM - CSE - 2020-21 - MJCET 16

Sequences and Summations
A sequence or series is just like an ordered n-tuple, except:
 Each element in the sequence has an associated index number.
 A sequence or series may be infinite.
A summation is a compact notation for the sum of the terms in a
(possibly infinite) sequence.

BE III Sem-DM - CSE - 2020-21 - MJCET 17

Sequences
Ordered list of elements
e.g., 1, 2, 3, 5, 8 is a sequence with 5 elements
1, 3, 9, 27, 81, …, …, is an infinite sequence
Sequence {an}: It is a function from a subset of the set of
integers (usually either the set of {0, 1, 2, …} or the set {1, 2, 3,
…}) to a set S
Use an to denote the image of the integer n
Call an a term of the sequence

BE III Sem-DM - CSE - 2020-21 - MJCET 18

Sequences
Example: {an} where an=1/n
a1, a2, a3, a4, … starts with 1, ½, 1/3, ¼,…
When the elements of an infinite set can be listed, the set is called countable
Will show that the set of positive rational numbers is countable, but the set of real numbers is not
Geometric progression: A sequence of the form a, ar, ar2, ar3,…, arn
where the initial term a and common ratio r are real numbers
Can be written as f(x)=a ∙ rx
The sequences {bn} with bn=(-1)n, {cn} with cn=2∙5n, {dn} with dn=6 ∙(1/3)n are geometric
progression
bn : 1, -1, 1, -1, 1, …
cn: 2, 10, 50, 250, 1250, …
dn: 6, 2, 2/3, 2/9, 2/27, …

BE III Sem-DM - CSE - 2020-21 - MJCET 19

Arithmetic progression
Arithmetic progression: a sequence of the form a, a+d, a+2d,
…, a+nd where the initial term a and the common difference d
are real numbers
Can be written as f(x)=a+dx
{sn} with sn=-1+4n, {tn} with tn=7-3n
{sn}: -1, 3, 7, 11, …
{tn}: 7, 4, 1, 02, …

BE III Sem-DM - CSE - 2020-21 - MJCET 20

Strings
Sequences of the form a1, a2, …, an are often used in computer
science
These finite sequences are also called strings
The length of the string S is the number of terms
The empty string, denoted by 𝝺, is the string has no terms
The string abcd is a string of length four

BE III Sem-DM - CSE - 2020-21 - MJCET 21

Special integer sequences
Finding some patterns among the terms
Are terms obtained from previous terms
By adding the same amount or an amount depends on the
position in the sequence?
By multiplying a particular amount?
By combining previous terms in a certain way?
In some cycle?

BE III Sem-DM - CSE - 2020-21 - MJCET 22

Recognizing Sequences
Find formulas for the sequences with the following first 5 terms
1, ½, ¼, 1/8, 1/16
 Recognize that the denominators are powers of 2. The sequence with an=1/2n-1 is a match. G.P with a=1 and

r=1/2
1, 3, 5, 7, 9
 Note that each term is obtained by adding 2 to the previous term. The sequence with an=2n-1 is a match.
A.P with a=1 and d=2
1, -1, 1, -1, 1
 Terms alternate b/w 1 and -1. The sequence with an=(-1)n+1 is a match. G.P with a=1 and r=-1
How can we produce the terms of a sequence if the first 10 terms are
1, 2, 2, 3, 3, 3, 4, 4, 4, 4
 Possible match: next five terms would all be 5,the following six terms would all be 6, and so on.
5, 11, 17, 23, 29, 35, 41, 47, 53, 59
 Possible match: nth term is 5 + 6(n – 1) = 6n – 1

BE III Sem-DM - CSE - 2020-21 - MJCET 23

Useful Sequences
Conjecture a simple formula for {an} if the first 10 terms of the
sequence are 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047

BE III Sem-DM - CSE - 2020-21 - MJCET 24

Summations
The sum of terms: am, am+1, …, an from {an}
n

a 
n
j , or jm
aj
jm

to represent am+am+1+…+an
 Here j is the index of summation (can be replaced arbitrarily by i or k)
 The index runs from the lower limit m to upper limit n
 The usual laws for arithmetic applies

 (axj  by j )  a j 1 x j  b j 1 y j wherea, b are real numbers

n n n
j 1

BE III Sem-DM - CSE - 2020-21 - MJCET 25

Summation Examples
 Express the sum of the first 100 terms of the sequence {a n} where an=1/n, n=1, 2, 3, …
1

100
j 1
j

5
 What is the value of j 1
j2

 j  1  2  3  4  5  1  4  9  16  25  55
5 2 2 2 2 2 2
j 1
 What is the value of  (1) 8
k 4
k

 (1)  (1)
8
k 4
k 4
 (1) 5  (1) 6  (1) 7  ( 1)8  1  (1)  1  (1)  1  1
 Shift Index:
5 4

 j  (k 1)
j 1
2

k 0
2
by setting j  k 1, or k  j 1

BE III Sem-DM - CSE - 2020-21 - MJCET 26

Geometric series
 Geometric series: sum of terms of a geometric progression. If a and r are real
numbers and r≠0, then
n
arn1  a Let S   ar j
 if r  1 j 0
n

 ar j   r 1 n
rS   ar j 1
Multiply both sides by r
j 0  if r 1 j 0
 (n 1)a n 1
  ar k
k 1
n
  ar k  ( ar n1  a )
k 0

 S  (ar n 1  a)
ar n 1  a
S
r 1

BE III Sem-DM - CSE - 2020-21 - MJCET 27

Double summations
Often used in programs

4 3 4

 ij   ( i  2 i  3i ) First expand the inner summation and then

i  1 j 1
4
i 1
compute the outer summation
  6 i  6  12  18  24  60
i 1

Can also use summation to add values of a function or of a set

 f (s)
sS

s  0  2  4  6
s{0 , 2 , 4}

BE III Sem-DM - CSE - 2020-21 - MJCET 28

Useful Summation Formulae

BE III Sem-DM - CSE - 2020-21 - MJCET 29

Examples 100

Find k
k 50
2
Using the formula of k2 = (n(n+1)(2n+1))/6
100 100 49
100101 201 49 50  99
   
k 2

k 50
 k 2
 k 2

k 1 k 1 6

6
 338350 40425 297925

Let x be a real number with |x|<1, Find 

n0
xn

a=1 and r=x

 ar n 1  a if r  1
n
 k
x k 1  1 
x k 1  1  1 1
 ar j   r  1 ,  x 
n
, x n
 limk   
j 0  (n  1)a if r  1 n 0 x 1 n 0 x 1 x 1 1  x

30
Cardinality
The sets A and B have the same cardinality, |A|=|B|, if and
only if there is a one-to-one correspondence from A to B
Countable: A set that is either finite or has the same
cardinality as the set of positive integers
A set that is not countable is called uncountable
When an infinite set S is countable, we denote the cardinality
of S by ℕ0, i.e., |S|= ℕ0

31
Example
Is the set of odd positive integers countable?
f(n)=2n-1 from Z+ to the set of odd positive integers
One-to-one: suppose that f(n)=f(m) then 2n-1=2m-1, so n=m
Onto: suppose t is an odd positive integer, then t is 1 less than an
even integer 2k where k is a natural number. Hence t=2k-1=f(k)

32
Infinite Set
An infinite set is countable if and only if it is possible to list
the elements of the set in a sequence
The reason being that a one-to-one correspondence f from the
set of positive integers to a set S can be expressed by
a1, a2, …, an, …where a1=f(1),a2=f(2),…an=f(n)
For instance, the set of odd integers, an=2n-1

33
Example
Is the set of positive rational numbers countable?
Every positive rational number is p/q
First consider p+q=2, then p+q=3, p+q=4, …
1, ½, 2,3,1/3, ¼, 2/3, 3/2, 4, 5,…
Because all positive rational
numbers are listed once,
the set is countable

34
Example
Is the set of real numbers uncountable?
Proof by contradiction
Suppose the set is countable, then the subset of all real
numbers that fall between 0 and 1 would be countable (as any
subset of a countable set is also countable)
The real numbers can then be listed in some order, say, r1, r2,
r3, …

35
Example contd..
So r1  0.d11d12d13d14 , where d ij  {0,1,2,3,4,5,6,7,8,9}
r2  0.d 21d 22d 23d 24 
r3  0.d 31d 32d 33d 34 
r4  0.d 41d 42d 43d 44 
r  0.23794101...(for example)
Form a new real number with
r  0.d1d 2 d 3 d 4 
• Every real number has a unique decimal expansion
4 if d ii  4 • The real number r is not equal to r1, r2, … as its decimal expansion of ri
di  
5 if d ii  4 in the i-th place differs from others
r1  0.23794102  • So there is a real number between 0 and 1 that is not in the list
r2  0.44590138 • So the assumption that all real numbers between 0 and 1 can be listed
r3  0.09118764  must be false
r4  0.80553900  • So all the real numbers between 0 and 1 cannot be listed
r  0.4544... • The set of real numbers between 0 and 1 is uncountable
36
Mathematical Induction
A powerful, rigorous technique for proving that a statement
P(n) is true for every positive integer n, no matter how large.
Essentially a “domino effect” principle.
Based on a predicate-logic inference rule:
P(1)
∀k≥1 [P(k)→P(k+1)] “The First
Principle
∴ ∀ n≥1 P(n) of Mathematical
Induction”

BE III Sem-DM - CSE - 2020-21 - MJCET 37

The “Domino Effect”
 Premise #1: Domino #1 falls.
 Premise #2: For every k∈Z+, if domino #k falls, then so does domino #k+1.
 Conclusion: All of the dominoes fall down!

BE III Sem-DM - CSE - 2020-21 - MJCET 38

Principle of Mathematical Induction:
To prove that a statement P(n) is true for all positive integers n,
we complete two steps:
Basis step: Show that P(1) is true
Inductive step: Show that for all positive integers k, if P(k) is true,
then P(k+1) is true. That is, we show P(k)P(k+1) for all positive
integers k
The assumption P(k) is true is called the inductive hypothesis
Proof technique:
[P(1)  k (P(k )  P(k 1))]  nP(n)
BE III Sem-DM - CSE - 2020-21 - MJCET 39
Mathematical Induction Example
Show that 1+2+… +n=n(n+1)/2, if n is a positive integer
 Let P(n) be the proposition that 1+2+… +n=n(n+1)/2
 Basis step: P(1) is true, because 1=1*(1+1)/2
 Inductive step: Assume P(k) is true for an arbitrary k. That is, 1+2+…
+k=k(k+1)/2
 We must show that 1+2+…+k+(k+1)=(k+1)(k+2)/2
 From P(k), 1+2+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2 which means
P(k+1) is true
 We have completed the basis and inductive steps, so by mathematical induction
we know that P(n) is true for all positive integers n. That is 1+2+…+n=n(n+1)/2

BE III Sem-DM - CSE - 2020-21 - MJCET 40

Example 2
Conjecture a formula for the sum of the first n positive odd
integers. Then prove the conjecture using mathematical
induction
 1=1, 1+3=4, 1+3+5=9, 1+3+5+7=16, 1+3+5+7+9=25
It is reasonable to conjecture the sum of first n odd integers is n2,
that is, 1+3+5+…+(2n-1)=n2
We need a method to prove whether this conjecture is correct or not

BE III Sem-DM - CSE - 2020-21 - MJCET 41

Example 2 contd..
Let P(n) denote the proposition the sum of the first n positive odd integers
is n2
 Basis step: P(1)= n2 = 12=1
 Inductive step: Assume that p(k) is true, i.e., 1+3+5+…+(2k-1)=k2
 We must show 1+3+5+…+(2k-1)+ (2k+1)=(k+1)2 is true for P(k+1)
 Thus,[1+3+5+…+(2k-1)]+(2k+1)=k2 +(2k+1)=(k+1)2 which means P(k+1) is
true
 (Note p(k+1) means 1+3+5+…+(2k+1)=(k+1)2)
We have completed both the basis and inductive steps. That is, we have
shown P(1) is true and P(k)P(k+1)
Consequently, P(n) is true for all positive integers n
BE III Sem-DM - CSE - 2020-21 - MJCET 42
Example 3
Use mathematical induction to show that 1+2+22+…+2n=2n+1-1 for all
non negative integers
Let P(n) be the proposition: 1+2+22+…+2n=2n+1-1
Basis step: P(0)=20+1-1=1
Inductive step: Assume P(k) is true, i.e., 1+2+22+…+2k=2k+1-1. It must be
shown that P(k+1) is true, i.e., 1+2+22+…+2k+1=2(k+1)+1-1 =2k+2-1
It follows
(1+2+22+…+2k)+2k+1=(2k+1-1)+2k+1=2*2k+1-1=2k+2-1 which means P(k+1) is
true
We have completed both the basis and inductive steps. By induction, we
show that 1+2+22+…+2n=2n+1-1
BE III Sem-DM - CSE - 2020-21 - MJCET 43
Example
In the previous step, P(0) is the basis step as the theorem is true ∀n
P(n) for all non-negative integers
To use mathematical induction to show that P(n) is true for
n=b, b+1, b+2, … where b is an integer other than 1, we show
that P(b) is true, and then P(k)P(k+1) for k=b, b+1, b+2, …
Note that b can be negative, zero, or positive

44
Example 4
Use Mathematical induction to prove the formula for the sum of a
finite number of terms of a geometric progression
n
ar n1  a
 ar j  a  ar  ar 2  ...  ar n 
j 0 r 1
if r  1
ar 1  a
 Basis step: P(0) is true as r 1
a
k
ar k 1  a
 Inductive step: Assume that P(k) is true, i.e.,  ar j 
j 0 r 1
if r  1
Show P(k+1) is true
k 1

 ar
j 0
j
 a  ar  ...  ar k  ar k 1

ar k 1  a
  ar k 1
r 1
ar k 1  a  ar k  2  ar k 1

r 1
k 2
ar  a

r 1
So P(k+1) is true. By induction, P(n) is true for all nonnegative integers

45
Example 5
 Use Mathematical induction to show that n<2n for n>0
 Basis step: P(1) is true as 1<21=2
 Inductive step: Assume P(k) is true, i.e., k<2k
We need to show P(k+1) is true i.e., s.t. k+1<2k+1
Adding 1 to both sides of k<2k , and noting that 1≤2k
k+1<2k+1≤2k+2k=2k+1
Thus P(k+1) is true
 We complete both basis and inductive steps, and shown that p(n) is true for all
positive integers n

46
Example 6
Use induction to show that 2n<n! for n ≥ 4
 Let P(n) be the proposition, 2n<n! for n ≥ 4
 Basis step: P(4) is true as 24=16<4!=24
 Inductive step: Assume P(k) is true, i.e., 2k<k! for k ≥ 4. We need to show
that P(k+1) is true i.e., 2k+1<(k+1)! for k ≥ 4
 Multiplying both sides of the inequality 2k<k! by 2
2. 2k<2 k!
2k+1<(k+1) .k! = (k+1)!
This shows P(k+1) is true when P(k) is true
 We have completed basis and inductive steps. By induction, we have shown
that P(n) is true for n ≥ 4
47
Example 7
Show that n3-n is divisible by 3 when n is positive
 Basis step: P(1) is true as 1-1=0 is divisible by 3
 Inductive step: Assume P(k) is true; i.e., k3-k is divisible by 3.
 We must show that P(k+1) is true. i.e.,S.T. (k+1)3-(k+1) is divisible by 3
(k+1)3-(k+1)=k3+3k2+3k+1-(k+1)
=(k3-k)+3(k2+k)
As both terms are divisible by 3, (k+1)3-(k+1) is divisible by 3
 We have completed both the basis and inductive steps. By induction, we
have shown that n3-n is divisible by 3 when n is positive

48
Example 8
Show that if S is a finite set with n elements, then S has 2n subsets
 Let P(n) be the proposition that a set with n elements has 2 n subsets
 Basis step: P(0) is true as a set with zero elements, the empty set, has exactly 2 0=1
subset, Since it has one subset, i.e., itself
 Inductive step: Assume P(k) is true, i.e., S has 2k subsets if |S|=k.
 It must be shown that P(k+1) is true, i.e., S has 2 k+1 subsets if |S|=k+1
 Let T be a set with k+1 elements. So, T=S⋃{a}, and |S|=k
 For each subset X of S, there are exactly two subsets of T, i.e., X and X ⋃{a}
 Because there are 2k subsets of S, there are 2⋅2k=2k+1 subsets of T. This finishes the
inductive step

49
Example 9
Use mathematical induction to show one of the De Morgan’s law:
n n
 Aj   Aj
j 1 j 1
where A1, A2, …, An are subsets of a universal set U, and n≥2
 Let P(n) be the identity for n sets
 Basis step: The statement P(2) asserts that A1  A2  A1  A2 ( De Morgan’s Law )
k k
 Inductive step: Assume is true for k≥2. To carry out the
j 1
Aj   Aj
j 1

inductive step it must be shown that this equality is valid for any k+1
subsets of U.  A  (  A )  A
k 1 k
j j k 1
j 1 j 1

k
 (  A j )  A k  1 ByDemorgan ' slaw
j 1
k
 (  A j )  A k 1
j 1
k 1
  Aj
j 1

50
Strong induction(Second Principle of Induction)
 Strong induction: To prove P(n) is true for all positive integers n, where P(n) is a
propositional function, we complete two steps
 Basis step: We show that the proposition P(1) is true
 Inductive step: We show that the conditional statement
 [P(1)∧P(2) ∧… ∧P(k)]→P(k+1) is true for all positive integers k
 The inductive step here makes use of the stronger hypothesis that all of P(1), P(2),…,P(k) are true, not just P(k).
 Mathematical induction and strong induction are equivalent
 Any proof using mathematical induction can also be considered to be a proof by strong
induction (induction  strong induction)
 It is more awkward to convert a proof by strong induction to one with mathematical induction
(strong induction  induction)
P(1)
∀k≥1: (P(1) ∧ P(2) ∧ ・・・ ∧ P(k)) → P(k+1)
∴∀n≥1: P(n)
51
Strong Induction Example
Show that every integer n >1 can be written as a product of primes
Let P(n) = “n can be written as the product of primes”
Basis step: P(2) is true, since 2 can be written as the product of one prime, itself.
Inductive step: Let k≥2. Assume P(j) is true ∀2 ≤ j ≤ k.
Show that P(k+1) is true. There are two cases to consider, namely, when k+1 is
prime and when k+1 is composite.
1) Consider k + 1 as prime, then P(k+1) is true
2) Else k + 1 is composite=ab, where 2 ≤ a ≤ b ≤ k+1.
By Inductive Hypothesis, both a and b can be written as the product of primes
Thus if k+1 is composite, it can be written as the product of primes

52
Strong Induction Example2
Prove that every amount of postage of 12 cents or more can be formed
using just 4-cent and 5-cent stamps.
 P(n) = “Postage of n cents can be formed using 4-cent and 5-cent stamps” for n ≥ 12.
 Basis step: Postage of 12,13,14 and 15 cents can be formed using three 4-cent stamps, two
4-cent stamps and one 5-cent stamp, one 4-cent stamp and two 5-cent stamps and three 5-
cent stamps respectively
12 = 3⋅4
13 = 2⋅4 + 1⋅5
14 = 1⋅4 + 2⋅5
15 = 3⋅5
So ∀12 ≤ i ≤ 15, P(i).
53
Strong Induction Example2 contd…
Inductive step: Let k ≥15, assume ∀12 ≤ i ≤ k, P(i).
Note 12 ≤ k - 3 ≤ k, so P(k - 3).(by inductive hypothesis)
This means we can form postage of k – 3 cents using just 4-cent
and 5-cent stamps.
Add a 4-cent stamp to get postage for k + 1,i.e. P(k + 1) is true
(postage of k + 1 cents can be formed using 4-cent and 5-cent
stamps).
Therefore, by the 2nd principle of mathematical induction
P(n) is true for all integers n with n ≥ 12.
54
Well-ordering property
Every non-empty subset of the set of positive integers has a least element
Use the well-ordering property to prove the division algorithm. Recall that the
division algorithm states that if a is an integer and d is a positive integer, then
there are unique integers q and r with 0 ≤ r < d and a = dq + r.
 Solution: Let S be the set of nonnegative integers of the form a − dq, where q is
an integer. This set is nonempty because −dq can be made as large as desired
(taking q to be a negative integer with large absolute value). By the well-ordering
property, S has a least element r = a − dq0.
 The integer r is nonnegative. It is also the case that r < d. If it were not, then there
would be a smaller nonnegative element in S, namely, a − d(q 0 + 1). To see this,
suppose that r ≥ d. Because a = dq0 + r, it follows that a − d(q0 + 1) = (a − dq0) − d
= r − d ≥ 0. Consequently, there are integers q and r with 0 ≤ r < d.
55
Recursive Definitions and Structural
Induction
In induction, we prove all members of an infinite set satisfy
some predicate P by:
Proving the truth of the predicate for larger members in terms of that
of smaller members.
In recursive definitions, we similarly define a function, a
predicate, a set, or a more complex structure over an infinite
domain (universe of discourse) by:
Defining the function, predicate value, set membership, or structure
of larger elements in terms of those of smaller ones.
56
Recursion
Recursion is the general term for the practice of defining an object in terms of
itself or of part of itself.
An inductive proof establishes the truth of P(k+1) recursively in terms of P(k).
There are also recursive algorithms, definitions, functions, sequences, sets,
and other structures.
Recursively defined functions: Uses two steps to define a function with the
set of non-negative integers as its domain
Basis step: Specify the value for the function at zero
Recursive step: Give a rule for finding its value at an integer from its values at
smaller integers
Such a definition is called a recursive or inductive definition
57
Recursively Defined Functions
Simplest case: One way to define a function f:N→S (for any
set S) or series an= f(n) is to:
Define f(0)
For n > 0, define f(n) in terms of f(0),…,f(n−1)
Example: Define the series an = 2n where n is a nonnegative
integer recursively:
an looks like 20, 21, 22, 23,…
Let a0 = 1
For n > 0, let an = 2⋅an–1
58
Example
Suppose we define f(n) for all n∈N recursively by:
Let f(0)=3
For all n>0, let f(n)=2f(n-1)+3. Find f(1), f(2), f(3), and f(4)
f(1)=2f(0)+3=2*3+3=9
f(2)=2f(1)+3=2*9+3=21
f(3)=2f(2)+3=2*21+3=45
f(4)=2f(3)+3=2*45+3=93

59
Recursive Definition of Factorial
Give an inductive definition of the factorial function f(n)=n!
Note that (n+1)!=(n+1)∙n!
We can define f(0)=1 and f(n+1)=(n+1)f(n) or f(n)= n.f(n-1)
To determine a value, e.g., f(5)=5!, we can use the recursive function
f(5)=5∙f(4)
=5∙4∙f(3)
=5∙4∙3∙f(2)
=5∙4∙3∙2∙f(1)
=5∙4∙3∙2∙1∙f(0)
=5∙4∙3∙2∙1∙1=120

60
Example
n

 Given a recursive definition of ak

k 0 0
 The first part of the recursive definition ak  a0
k 0
n1 n
 The second part is a  (a )  a
k 0
k
k 0
k n1

61
Example – Fibonacci numbers
 Fibonacci numbers f0, f1, f2, are defined by the equations, f0=0, f1=1, and fn=fn-1+fn-2
for n=2, 3, 4, …
 By definition
f2=f1+f0=1+0=1
f3=f2+f1=1+1=2
f4=f3+f2=2+1=3
f5=f4+f3=3+2=5
f6=f5+f4=5+3=8

62
A Lower Bound on Fibonacci Numbers
Theorem: For all integers n≥3, fn > αn−2, where α = (1 + 51/2)/2 ≈ 1.61803.
Proof. (Using strong induction.) Let P(n) = (fn > αn−2).
Basis step:For n = 3, note that αn−2 = α < 2 = f3.
For n = 4, αn−2 = α2
= (1 + 2 ・ 51/2 + 5)/4
= (3 + 51/2)/2
≈ 2.61803 (= α + 1)
< 3 = f4.
Inductive step: For k≥4, assume P(j) is true, fj> α j−2 for 3≤j≤k, Now prove P(k+1) is true. i.e. fk+1 =αk−1
fk+1 = fk + fk−1 > αk−2 + αk−3 (By inductive hypothesis, fk−1 > αk−3 and fk > αk−2).
Note that α2 = α + 1. Since (3 + 51/2)/2 = (1 + 51/2)/2 + 1
Thus, αk−1 = α2αk−3 = (α + 1)αk−3
= ααk−3 + αk−3 = αk−2 + αk−3.
So, fk+1 = fk + fk−1 > αk−2 + αk−3 = αk−1. Thus P(k+1) is true. This completes the proof
63
Recursively Defined Sets and Structures
An infinite set S may be defined recursively, by giving:
 A small finite set of base elements of S.
 A rule for constructing new elements of S from previously-established elements.
 Implicitly, S has no other elements but these.
Example: Let 3∈S, and let x+y∈S if x,y∈S. What is S?
 3 ∈ S (basis step)
 6 (= 3 + 3) is in S (first application of recursive step)
 9 (= 3 + 6) and 12 (= 6 + 6) are in S (second application of the recursive step)
 15 (= 3 + 12 or 6 + 9), 18 (= 6 + 12 or 9 + 9), 21 (= 9 + 12), 24 (= 12 + 12) are in S (third application
of the recursive step)
 … so on
 Therefore, S = {3, 6 , 9 , 12, 15, 18, 21, 24,…}
 = set of all positive multiples of 3
64
The Set of All Strings
 Given an alphabet Σ, the set Σ* of all strings over Σ can be recursively defined by:
 Basis step: λ ∈ Σ * (λ : empty string). The basis step defines that the empty string belongs to string
 Recursive step: (w∈Σ * ∧ x∈Σ) → wx∈Σ *
 The recursive step states that new strings are produced by adding a symbol from ∑ to the end of strings
in ∑*
 At each application of the recursive step, strings containing one additional symbol are generated
 Example: If Σ = {0, 1} then
 λ∈ Σ * (basis step)
 0 and 1 are in Σ * (first application of recursive step)
 00, 01, 10, and 11 are in Σ * (second application of the recursive step)
 … so on
 Therefore, Σ * consists of all finite strings of 0’s and 1’s together with the empty string

65
Concatenation
 Two strings can be combined via the operation of concatenation
 Let ∑ be a set of symbols and ∑* be the set of strings formed from symbols in ∑
 We can define the concatenation for two strings by recursive steps
 Basis step: If w∊∑*, then w∙𝜆=w, where 𝜆 is the empty string
 Recursive step: If w1∊∑*, w2∊∑* and x ∊∑, then w1 ∙ (w2 x)=(w1 ∙ w2)x
 Oftentimes w1 ∙ w2 is rewritten as w1w2
 e.g., w1=abra, and w2=cadabra, w1w2=abracadabra
 Length of a string: Give a recursive definition of l(w), the length of a string w
 The length of a string is defined by
 l(𝜆)=0
 l(wx)=l(w)+1 if w∊∑* and x∊∑

66
Well-formed formulae
 We can define the set of well-formed formulae for compound statement forms involving
T, F, proposition variables and operators from the set {┐, ˄, ˅, →, ↔}
 Basis step: T, F, and s, where s is a propositional variable are well-formed formulae
 Recursive step: If E and F are well-formed formulae, then ┐E, E˄F, E ˅F, E→F, E ↔F
are well-formed formulae
 For Ex, By the Basis step we know that T,F, p& q are well-formed formulae where p,q are
propositional variables.
 From an initial application of the recursive step, we know that (p˅q), (p→F), (F→q) and
(q˄F) are well-formed formulae
 A second application of the recursive step shows that ((p˅q) →(q˄F)), (q˅(p˅q)), and
((p→F)→T) are well-formed formulae.

67
Rooted trees
 A tree is a graph in which there is exactly one undirected path between each pair of nodes.
 An undirected graph can be represented as a set of unordered pairs (called arcs) of objects called nodes.
 Definition of the set of rooted trees: The set of rooted trees, where a rooted tree consists of a set of
vertices containing a distinguished vertex called the root, and edges connecting these vertices, can be
defined recursively by
 Basis step: a single vertex r is a rooted tree
 Recursive step: suppose that T1, T2, …, Tn are disjoint rooted trees with roots r1, r2, …, rn, respectively.
 Then the graph formed by starting with a root r, which is not in any of the rooted trees T 1, T2, …, Tn, and adding
an edge from r to each of the vertices r1, r2, …, rn, is also a rooted tree

68
Binary trees
A binary tree is a tree data structure in which each vertex (node)
has at most two branches (children), which are referred to as the left
subtree (child) and the right subtree (child)
Extended binary trees: the left subtree or the right subtree can be
empty
Full binary trees: must have left and right subtrees

69
Extended Binary Trees
The set of extended binary trees can be defined by
Basis step: The empty set ∅ is an extended binary tree
Recursive step: If T1 and T2 are disjoint extended binary trees,
there is an extended binary tree, denoted by T1 ∙ T2, consisting of
a root r together with edges connecting the root to each of the
roots of the left subtree T1 and right subtree T2, when these trees
are non-empty

70
Building Up Extended Binary Trees

71
Full Binary Trees
The set of full binary trees can be defined recursively
Basis step: There is a full binary tree consisting only of a single
vertex r
Recursive step: If T1 and T2 are disjoint full binary trees, there is
a full binary tree, denoted by T1 ∙ T2, consisting of a root r
together with edges connecting the root to each of the roots of
the left subtree T1 and right subtree T2

72
Building up Full Binary Trees

73
Structural Induction
Proving something about a recursively defined object
using an inductive proof whose structure mirrors the
object’s definition.
 Basis step: Show that the result holds for all elements in the set specified in the
basis step of the recursive definition
 Recursive step: Show that if the statement is true for each of the elements used
to construct new elements in the recursive step of the definition, the result holds
for these new elements.

74
Trees and Structural induction
To prove properties of trees with structural induction
Basis step: Show that the result is true for the tree consisting of a
single vertex
Recursive step: Show that if the result is true for the trees T1 and
T2, then it is true for T1⋅T2, consisting of a root r, which has T1 as
its left subtree and T2 as its right subtree

75
Height of Binary tree
We define the height h(T) of a full binary tree T recursively
Basis step: The height of the full binary tree T consisting of
only a root r is h(T)=0
Recursive step: If T1 and T2 are full binary trees, then the full
binary tree T= T1⋅ T2 has height h(T)=1+max(h(T1), h(T2))

76
Number of vertices in a Binary tree
If we let n(T) denote the number of vertices in a full binary
tree, we observe that n(T) satisfies the following recursive
formula:
Basis step: The number of vertices n(T) of the full binary tree
consisting of only a root r is n(T)=1
Recursive step: If T1 and T2 are full binary trees, then the
number of vertices of the full binary tree T= T1⋅ T2 is
n(T)=1+n(T1)+n(T2)

77
Theorem
If T is a full binary tree T, then n(T)≤2h(T)+1-1
Use Structural induction to prove this
Basis step: For the full binary tree consisting of just the root
r the result is true as n(T)=1 and h(T)=0, so n(T)=1≤20+1-1=1
Inductive step: For the inductive hypothesis we assume that
n ( T 1 )  2 h ( T1 )  1  1 , n ( T 2 )  2 h ( T 2 )  1  1

where T1 and T2 are full binary trees

78
Theorem
By the recursive formulae for n(T) and h(T), we have
n(T)=1+n(T1)+n(T2) and h(T)=1+max(h(T1), h(T2))
Thus,
n ( T )  1  n ( T1 )  n ( T 2 )
By recursive formula for n(T)
 1  ( 2 h ( T1 )  1  1)  ( 2 h ( T 2 )  1  1) By the Inductive Hypothesis
Since the sum of two terms is at
 2  max( 2 h ( T1 )  1 , 2 h ( T 2 )  1 )  1 most 2 times the larger
 2  2 max( h ( T1 ), h ( T 2 ))  1  1
 2  2 h (T )  1
 2 h (T ) 1  1
This completes the inductive step
79
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
Give a recursive algorithm for computing n! where n is a
non-negative integer
We can compute n!=n∙(n-1)! Where n is a positive integer,
and that 0!=1 for a particular integer
We use the recursive step n times

80
Recursive algorithm for Factorial

procedure factorial(n: non-negative integer)

if n=0 then factorial(n):=1
else factorial(n):=n ∙ factorial(n-1)

81
Recursive algorithm for an
procedure power(a: nonzero real number, n: non-negative
integer)
if n=0 then power(a,n):=1
else power(a,n):=a ∙ power(a, n-1)

82
Recursive Euclid’s Algorithm
Give a recursive algorithm for gcd(a, b) with a < b
A recursive version of Euclidean algorithm: b=aq+r, gcd(b,a)=gcd(a,r)
Two conditions are used here gcd(a,b)=gcd(b mod a,a) and gcd(0,b)=b.
procedure gcd(a, b: non-negative integers with a < b)
if a=0 then
gcd(a, b):=b
else
gcd(a, b):=gcd(b mod a, a)
Let a=5 and b=8. gcd(5, 8)=gcd(8 mod 5, 5)=gcd(3, 5)
Next, gcd(3, 5)=gcd(5 mod 3, 3)=gcd(2, 3), then gcd(2, 3)=gcd (3 mod 2,
2)=gcd(1, 2). Finally gcd(1,2)=gcd(2 mod 1, 2) = gcd(0, 1)=1. Thus,
gcd(5,8)=1 86
Binary Search algorithm
procedure binary_search(x,i, j: integers, 1≤i≤n, 1 ≤j≤n)
m= ⌞(i+j)/2⌟
if x=am then
location:=m
else if (x < am and i < m) then
binary_search(x, i, m-1)
else if (x > am and j > m) then
binary_search(x, m+1, j)
else
location:=0
87
Recursion and Iteration
Often an Iterative algorithm is more efficient than a recursive
one (unless special-purpose machines are used)
 procedure fibonacci(n: nonzero integer)
if n=0 then fibonacci(0):=0
else if n=1 then fibonacci(1):=1
else fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)

89
Iterative algorithm for Fibonacci Number
 procedure iterative_fibonacci(n: nonzero integer)
if n=0 then y:=0
else
begin
x:=0
y:=1
for i:=1 to n-1
z:=x+y
x:=y
y:=z
end
end
{y is the n-th Fibonacci number}
90
Recursion and iteration- Time complexity
The above algorithm initializes x as f0=0, and y as f1=1
When the loop is traversed, the sum of x and y is assigned to the
auxiliary variable z
Then x is assigned the value of y and y is assigned the value of the
auxiliary variable z
Thus, after going through the loop the first time, it follows x equals f 1
and y equals f0+f1=f2
Next, f1+f2=f3, …
After going through the algorithm n-1 times, x equals fn-1 and y equals fn
Only n-1 additions have been used to find fn
91
Merge Sort
Example: Sort the list 8, 2,
4, 6, 9, 7, 10, 1, 5, 3
Merge sort: split the list
into individual elements
by successively splitting
lists into two
Sorting is done by
successively merging pairs
of lists
92
Merge Sort
In general, a merge sort proceeds by iteratively splitting lists into two
sublists represented by a balanced binary tree
We can also describe the merge sort recursively
procedure mergesort(L=a1, …, an)
if n>1 then
m:= ⌞n/2⌟
L1=a1, a2, …, am
L2=am+1, …, an
L=merge(mergesort(L1), mergesort(L2))
{L is a sorted list in non-decreasing order}
93
Merge Sort
Merge two lists, 2, 3, 5, 6, and 1, 4

94
Merging Two lists
procedure merge(L1, L2: sorted lists)
L:=empty set
while L1and L2 are both non-empty
begin
remove smaller of first element of L1 and L2 from the list it is in
and put it at the left end of L
if removal of this element makes one list empty then remove
all elements from the other list and append them to L
end
{L is the merged list with elements in non-decreasing order}
95