CSD101 - Discrete Structures

(Discrete Mathematics)
Fall 2016

Lecture - 12
Mathematical
Induction
Mathematical Induction

• Mathematical induction is an extremely important proof

technique.

• Mathematical induction can be used to prove

• results about complexity of algorithms
• correctness of certain types of computer programs
• theorem about graphs and trees
• …
What is Mathematical Induction?

• How to prove “P(n), a mathematical statement, for all

positive integer n”.

• It is a method of proof.

• It does not generate answers: it only can prove them.

Mathematical Induction
• Assume P(n) is a propositional function.

• Principle of mathematical induction:

To prove that P(n) is true for all positive integers n, we complete two
steps.

1. Basis Step:
• Verify P(1) is true.

2. Inductive Step:
• Show P(k) → P(k+1) is true for all positive integers k.
Mathematical Induction
• Basis Step: P(1)
• Inductive Step: ∀𝑘(P(k) → P(k+1))
• Result: ∀ n P(n) domain: positive integers

• How to show P(1) is true?

• P(1): n is replaced by 1 in P(n)
• Then, show P(1) is true.
• How to show ∀k (P(k) → P(k+1))?
• Direct proof can be used
• Assume P(k) is true for some arbitrary k.
• Then, show P(k+1) is true.
Example
Suppose that we have an infinite ladder
1. We can reach the first step of the
ladder.
2. If we can reach a particular step of
the ladder, then we can reach the
next step.
Then, we can conclude that we are able
to reach every step of this infinite
ladder.
Example
• An infinite row of dominoes, labeled 1,
2, 3, ..., n
• P(n): Domino n is knocked over
• P(1): The first domino is knocked over
• P(k): The kth domino is knocked over
• The fact that
• The first domino is knocked over
• And whenever the kth domino is knocked
over, it also knocks the (k+1)st domino over
• Implies that all the dominoes are
knocked over
Example
• Show that 1 + 2 + 3 + … + n = n(n+1) / 2, where n is a
positive integer.

• Proof by induction:
• First define P(n)
P(n) is 1 + 2 + 3 + … + n = n(n+1) / 2

• Basis Step: (Show P(1) is true.)

1 = 1(2)/2
So, P(1) is true.
Example
• Proof by induction:
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true.
1 + 2 + 3 + … + k = k(k+1) / 2
• Show P(k+1) is true.
P(k+1) = 1 + 2 + 3 + … (k+1) = (k+1)(k+2) / 2
1 + 2 + … + k + k+1 = (1 + 2 + …+ k) + (k+1)
= k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)]/2
= (k+1)(k+2)/2

• We showed that P(k+1) is true under assumption that P(k) is

true. So, by mathematical induction 1+2+…+n = n(n+1)/2.
What did we show
• Base case: P(1)
• If P(k) was true, then P(k+1) is true
• i.e., P(k) → P(k+1)
• We know it’s true for P(1)
• Because of P(k) → P(k+1), if it’s true for P(1), then it’s true for P(2)
• Because of P(k) → P(k+1), if it’s true for P(2), then it’s true for P(3)
• Because of P(k) → P(k+1), if it’s true for P(3), then it’s true for P(4)
• Because of P(k) → P(k+1), if it’s true for P(4), then it’s true for P(5)
• And onwards to infinity
• Thus, it is true for all possible values of n
• In other words, we showed that:
• [P(1)   k (P(k)  P(k+1))]   n P(n)
Example
• Use mathematical induction to show that 1 + 2 + 22 + ⋯ +
2𝑛 = 2𝑛+1 − 1 for all nonnegative integers n.
• Proof by induction:
• First define P(n)
P(n) is 1 + 2 + 22 + ⋯ + 2𝑛 = 2𝑛+1 − 1
• Basis step: (Show P(0) is true.)
1 = 21 − 1 So, P(0) is true.
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true.
1 + 2 + 22 + ⋯ + 2𝑘 = 2𝑘+1 − 1
Example
• Proof by induction:
• Show P(k+1) is true.
𝑃 𝑘 + 1 𝑖𝑠 1 + 2 + 22 + ⋯ + 2𝑘+1 = 2𝑘+2 − 1
1 + 2 + 22 + ⋯ + 2𝑘 + 2𝑘+1 = 2𝑘+1 − 1 + 2𝑘+1
= 2.2𝑘+1 − 1
= 2𝑘+2 − 1

• We showed that P(k+1) is true under assumption that P(k)

is true. So, by mathematical induction that 1 + 2 + 22 +
⋯ + 2𝑛 = 2𝑛+1 − 1 .
Example
• Show that 1 + 3 + 5 … + (2𝑛 − 1) = 𝑛2 , where 𝑛 is a
positive integer.

• Proof by induction:
• First define P(n)
P(n) is 1 + 3 + 5 … + (2𝑛 − 1) = 𝑛2

• Basis Step: (Show P(1) is true.)

1 = 12
So, P(1) is true.
Example
• Proof by induction:
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true.
1 + 3 + 5 … + (2𝑘 − 1) = 𝑘 2
• Show P(k+1) is true.
𝑃 𝑘 + 1 𝑖𝑠 1 + 3 + 5 … + 2 𝑘 + 1 − 1
= (𝑘 + 1)2
1 + 3 + 5 … + 2𝑘 − 1 + 2 𝑘 + 1 − 1
= 𝑘2 + 2 𝑘 + 1 − 1
= 𝑘 2 + 2𝑘 + 1 = (𝑘 + 1)2

• We showed that P(k+1) is true under assumption that P(k) is true. So,
by mathematical induction 1 + 3 + 5 … + (2𝑛 − 1) = 𝑛2 .
Example
• Prove by mathematical induction
12 + 22 + 32 + ⋯ + 𝑛2 = 𝑛(𝑛+1)(2𝑛+1)
6
𝑓𝑜𝑟 𝑎𝑙𝑙 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑛≥1.
Example
• Use mathematical induction to prove the formula for the
sum of a finite number of terms of a geometric
progression.
𝑛 𝑘 2 𝑛 (𝑎𝑟 𝑛+1 −𝑎)
• 𝑘=0 𝑎𝑟 = 𝑎 + 𝑎𝑟 + 𝑎𝑟 + ⋯ + 𝑎𝑟 = (𝑟−1)
𝑤𝑕𝑒𝑟𝑒 𝑟 ≠ 1.
• Proof by induction:
• First define P(n)
(𝑎𝑟 𝑛+1 −𝑎)
P(n) is 𝑎 + 𝑎𝑟 + 𝑎𝑟 2 + ⋯ + 𝑎𝑟 𝑛 = (𝑟−1)

• Basis step: (Show P(0) is true.)

𝑎 = (𝑎𝑟−𝑎) (𝑟−1) = 𝑎 So, P(0) is true.
Example
• Proof by induction:
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true.
2 𝑘 (𝑎𝑟 𝑘+1 − 𝑎)
𝑎 + 𝑎𝑟 + 𝑎𝑟 + ⋯ + 𝑎𝑟 = (𝑟 − 1)
• Show P(k+1) is true.
(𝑎𝑟 𝑘+2 −𝑎)
P(k+1) is 𝑎 + 𝑎𝑟 + 𝑎𝑟 2 + ⋯ + 𝑎𝑟 𝑘+1 = (𝑟−1)
𝑎𝑟 𝑘+1 −𝑎
𝑎 + 𝑎𝑟 + 𝑎𝑟 2 + ⋯ + 𝑎𝑟 𝑘 + 𝑎𝑟 𝑘+1 = 𝑟−1 + 𝑎𝑟 𝑘+1

= 𝑎𝑟 𝑘+1 − 𝑎 𝑘+1 (𝑟 − 1)
𝑟−1 + 𝑎𝑟 (𝑟 − 1)
𝑘+1 𝑘+2 𝑘+1
= 𝑎𝑟 − 𝑎 + 𝑎𝑟 − 𝑎𝑟
𝑟−1
= 𝑎𝑟 𝑘+2 − 𝑎
𝑟−1
• We showed that P(k+1) is true under assumption that P(k) is true.
(𝑎𝑟 𝑛+1 −𝑎)
So, by mathematical induction 𝑎 + 𝑎𝑟 + 𝑎𝑟 2 + ⋯+ 𝑎𝑟 𝑛 = (𝑟−1)
Proving Inequalities Example
• 𝑈𝑠𝑒 𝑚𝑎𝑡𝑕𝑒𝑚𝑎𝑡𝑖𝑐𝑎𝑙 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑡𝑜 𝑝𝑟𝑜𝑣𝑒 𝑡𝑕𝑒 𝑖𝑛𝑒𝑞𝑢𝑎𝑙𝑖𝑡𝑦
𝑛 < 2𝑛 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑛.
• Proof by induction:
• First define P(n)
P(n) is 𝑛 < 2𝑛 .
• Basis step: (Show P(1) is true.)
1< 21 = 2
So, P(1) is true.
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true 𝑘 ≥ 1.
𝑘 < 2𝑘
Proving Inequalities Example
• Proof by induction:

• Show P(k+1) is true.

P(k+1) is 𝑘 + 1 < 2𝑘+1
𝑘 + 1 < 2𝑘 + 1 𝑢𝑠𝑖𝑛𝑔 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑕𝑦𝑝𝑜𝑡𝑕𝑒𝑠𝑖𝑠 𝑘 < 2𝑘
< 2𝑘 + 2𝑘 = 2. 2𝑘 = 2𝑘+1

• We showed that P(k+1) is true under assumption that P(k)

is true. So, by mathematical induction 𝑛 < 2𝑛 for all
positive integers n.
Proving Inequalities Example
• 𝑈𝑠𝑒 𝑚𝑎𝑡𝑕𝑒𝑚𝑎𝑡𝑖𝑐𝑎𝑙 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑡𝑜 𝑝𝑟𝑜𝑣𝑒 𝑡𝑕𝑒 𝑖𝑛𝑒𝑞𝑢𝑎𝑙𝑖𝑡𝑦
2𝑛 < 𝑛! 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑛 𝑎𝑛𝑑 𝑛 ≥ 4.
• Proof by induction:
• First define P(n)
P(n) is 2𝑛 < 𝑛!.
• Basis step: (Show P(4) is true.)
24 < 4!
16 < 24
So, P(4) is true.
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true for 𝑘≥4
2𝑘 < 𝑘!
Proving Inequalities Example
Proof by induction:
• Show P(k+1) is true.
P(k+1) is 2𝑘+1 < (𝑘 + 1)!
2𝑘+1 = 2. 2𝑘 𝑏𝑦 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 𝑜𝑓 𝑒𝑥𝑝𝑜𝑛𝑒𝑛𝑡
< 2. 𝑘! 𝑏𝑦 𝑡𝑕𝑒 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑕𝑦𝑝𝑜𝑡𝑕𝑒𝑠𝑖𝑠
< 𝑘 + 1 . 𝑘! 𝑏𝑒𝑐𝑎𝑢𝑠𝑒 2 < 𝑘 + 1
= 𝑘+1 ! 𝑏𝑦 𝑑𝑒𝑓𝑖𝑛𝑖𝑡𝑖𝑜𝑛 𝑜𝑓 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛.

• We showed that P(k+1) is true under assumption that P(k)

is true. So, by mathematical induction2𝑛 < 𝑛! for all
positive integers n and n ≥ 4 .
Proving Inequalities Example
• Show that 𝑛! < 𝑛𝑛 for all 𝑛 > 1.

• Proof by induction:

• First define P(n)

P(n) is 𝑛! < 𝑛𝑛

• Basis Step: (Show P(2) is true.)

2! < 22
2 < 4
So, P(2) is true.
Proving Inequalities Example
• Proof by induction:
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true 𝑘 > 1.
𝑘! < 𝑘𝑘
• Show P(k+1) is true.
P(k+1) is 𝑘 + 1 ! < (𝑘 + 1)𝑘+1
𝑘 + 1 ! = 𝑘 + 1  𝑘!
𝑘 + 1  𝑘! < 𝑘 + 1 . 𝑘𝑘
< 𝑘 + 1 𝑘 + 1 𝑘 𝑎𝑠 𝑘𝑘 < (𝑘 + 1)𝑘
= 𝑘 + 1 𝑘+1
• We showed that P(k+1) is true under assumption that P(k) is true.
Proving Divisibility Results
• 𝑈𝑠𝑒 𝑚𝑎𝑡𝑕𝑒𝑚𝑎𝑡𝑖𝑐𝑎𝑙 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 𝑡𝑜 𝑝𝑟𝑜𝑣𝑒 𝑡𝑕𝑎𝑡 𝑛3 −
𝑛 𝑖𝑠 𝑑𝑖𝑣𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3 𝑤𝑕𝑒𝑛𝑒𝑣𝑒𝑟 𝑛 𝑖𝑠 𝑎 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑖𝑛𝑡𝑒𝑔𝑒𝑟.
• Proof by induction:
• First define P(n)
P(n) is "𝑛3 −𝑛 𝑖𝑠 𝑑𝑖𝑣𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3" .
• Basis step: (Show P(1) is true.)
13 − 1 = 0 𝑖𝑠 𝑑𝑖𝑣𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3.
So, P(1) is true.
• Inductive Step: (Show ∀k (P(k) → P(k+1)) is true.)
• Assume P(k) is true.
𝑘 3 − 𝑘 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑏𝑙𝑒 𝑏𝑦 3.
Proving Divisibility Results
• Proof by induction:
• Show P(k+1) is true.
P(k+1) is (𝑘 + 1)3 − (𝑘 + 1) 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑏𝑙𝑒 𝑏𝑦 3.

(𝑘 + 1)3 − 𝑘 + 1 = 𝑘 3 + 3𝑘 2 + 3𝑘 + 1 − (𝑘 + 1)
= (𝑘 3 − 𝑘) + 3(𝑘 2 + 𝑘)

• We showed that P(k+1) is true under assumption that P(k) is true.

Chapter Exercise

Chapter # 5
Topic # 5.1
Q 3, 4, 5, 7, 8, 18, 20, 21, 31, 32, 33, 34