Proof Strategy- Mathematical

Induction
Dr. Pronaya Bhattacharya
Disclaimer- Slides are adapted from Rosen
5th Edition, Cornell University Web Site, and
MIT Oxford Lecture on Trees

1
What’s is Induction About?

• Many statements assert that a property is an universal true – i.e.,

all the elements of the universe exhibit that property

• Examples:

1. For every positive integer n: n! ≤ nn

2. For every set with n elements, the cardinality of its power set is
2 n.

• Induction is one of the most important techniques for proving

statements about universal properties.

2
The Ladder Example to Understand Induction-

1. We can reach the first rung of this ladder;

2. If we can reach a particular rung of the ladder,
• then we can reach the next rung of the ladder.

• Can we reach every step of this infinite ladder?

• Yes, using Mathematical Induction which is

• a rule of inference that tells us:

• P(1)
• k (P(k) → P(k+1))
• --------------------------
•  n (P(n)
Principle of
Mathematical Induction
• Hypothesis: P(n) is true for all integers nb

• To prove that P(n) is true for all integers nb (*), where P(n) is a
propositional function, follow the steps:

• Basic Step or Base Case: Verify that P(b) is true;

• Inductive Hypothesis: assume P(k) is true for some k  b;

• Inductive Step: Show that the conditional statement P(k) →P(k+1) is

true for all integers k  b. This can be done by showing that under
the inductive hypothesis that P(k) is true, P(k+1) must also be true.

(*) quite often b=1, but b can be any integer number. 4

Mathematical
Prove a base case Induction
(n=1)
example
Prove P(k)→P(k+1)

• Use induction to prove that the sum of the first n odd integers is
n2. What’s the hypothesis?
Note:
1 – Hypothesis: P(n) – sum of first n odd integers = n2. We assume P(k)
(Statement we are trying to prove.) not:
k P(k)
2 - Base case (n=1): the sum of the first 1 odd integer is 12.
Since 1 = 12 ☺
3 - Assume P(k): the sum of the first k odd ints is k2. Inductive
1 + 3 + … + (2k - 1) = k2 hypothesis

4 – Inductive Step: show that (k) P(k) → P(k+1), assuming P(k).

How?
By inductive
P(k+1)= 1 + 3 + … + (2k-1) + (2k+1) = k2 + (2k + 1) hypothesis
= (k+1)2
p(k) 5
Mathematical Induction
example Prove a base case (n=?)
Prove P(k)→P(k+1)

• Use induction to prove that the 1 + 2 + 22 + … + 2n = 2n+1 - 1 for all

non-negative integers n.

• 1 - Hypothesis? P(n) = 1 + 2 + 22 + … + 2n = 2n+1 – 1

• (to be proven) for all non-negative integers n.

2 - Base case? n = 0 20 = 21-1. not n=1! The base case

can be negative, zero,
or positive

3 – Inductive Hypothesis
Inductive
Assume P(k) = 1 + 2 + 22 + … + 2k = 2k+1 – 1 hypothesis

6
4 – Inductive Step: show that (k) P(k) → P(k+1), assuming
P(k). How?

By inductive
P(k+1)= 1 + 2 + 22 +…+ 2k+ 2k+1 = (2k+1 – 1) + 2k+1 hypothesis
p(k)
= 2 2k+1 - 1
= 2(k+1)+1 - 1

Note: P(k) = 1 + 2 + 22 + … + 2k = 2k+1 – 1

7
Mathematical Induction
example
• Prove that 11! + 22! + … + nn! = (n+1)! - 1,  positive integers
1 – Hypothesis P(n) = 11! + 22! + … + nn! = (n+1)! - 1,  positive integers
2 - Base case (n=1): 11! = (1+1)! - 1?
11! = 1 and 2! - 1 = 1 Inductive
3 - Assume P(k): 11! + 22! + … + kk! = (k+1)! - 1 hypothesis

4 – Inductive Step - show that (k) P(k) → P(k+1).

I.e, prove that 11! + … + kk! + (k+1)(k+1)! = (k+2)! – 1, assuming P(k)

11! + … + kk! + (k+1)(k+1)! = (k+1)! - 1 + (k+1)(k+1)!

= (1 + (k+1))(k+1)! - 1
= (k+2)(k+1)! - 1
= (k+2)! - 1
Mathematical Induction - why does it work?

• Definition:
• A set S is “well-ordered” if every non-empty subset of S has a least
element.

• Given (we take as an axiom): the set of natural numbers (N) is

well-ordered.

• Is the set of integers (Z) well ordered?

No.
{ x  Z : x < 0 } has no
least element.
9
Mathematical Induction - why does it work?

• Is the set of non-negative reals (R) well ordered?

No.
{ x  R : x > 1 } has no
least element.

10
Mathematical Induction
example

Prove that a set with n elements has 2n subsets.

• 1-Hypothesis: set with n elements has 2n subsets

2- Base case (n=0): S=ø, P(S) = {ø} and |P(S)| = 1 = 20

Inductive
3- Inductive Hypothesis - P(k): given |S| = k, |P(S)| = 2k hypothesis

4- Inductive Step: (k) P(k) → P(k+1), assuming P(k). i.e,

Prove that if |T| = k+1, then |P(T)| = 2k+1, given that P(k)=2k

11
Inductive Step: Prove that if |T| = k+1, then |P(T)| = 2k+1 assuming
P(k) is true.
T = S U {a} for some S  T with |S| = k, and a  T

How to obtain the subsets of T?

For each subset X of S there are exactly two subsets of T, namely X and X U {a}

Generating subsets of a set T with k+1 elements

from a set S with K elements

Because there are 2k subsets of S (why?), Ind. hypothesis

there are 2  2k subsets of T.
Deficient Tiling

• A 2n x 2n sized grid is deficient if all but one cell is tiled.

2n

2n
Mathematical Induction - a clever example

Hypothesis:
P(n) - We want to show that all 2n x 2n sized deficient grids
can be tiled with right triominoes, which are pieces that
cover three squares at a time, like this:

14
• Base Case:

P(1) - Is it true for 21 x 21 grids?

YES ☺

15
• Inductive Hypothesis:
• We can tile a 2k x 2k deficient board using our designer tiles.

• Inductive Step:
• Use this to prove that we can tile a 2k+1 x 2k+1 deficient
board using our designer tiles.

16
2k 2k

2k
? ?
2k+1

?
OK!!
2k (by
IH)
2k 2k

OK!! OK!!
2k (by (by
IH) IH)
2k+1
OK!! OK!!
2k (by (by
IH) IH)
So, we can tile a 2k x 2k deficient board using our designer tiles.

What does this mean for 22k mod 3? = 1 (also do

direct proof by induction)
Principle of Strong Induction

1. State the hypothesis very clearly:

• P(n) is true for all integers nb – state the property P is English
2. Identify the the base case
• P(b) holds because …
3. Inductive Hypothesis
• (P(b)  P(b+1)  …  P(k)
• 4 . Inductive Step - Assuming P(k) is true for all positive integers
not exceeding k (inductive hypothesis), prove that P(k+1) holds;
i.e.,
(P(b)  P(b+1)  …  P(k) → P(k+1)
•

21
Strong Mathematical Induction

• If
• P(0) and
• n0 (P(0)  P(1)  …  P(k)) → P(k+1)
• Then
• n0 P(n) In strong induction proofs, to
show P(k+1), our inductive
hypothesis assures that ALL
of P(b), P(b+1), … P(k) are
true, so we can use ANY of
them to make the inference.

22
Strong Induction
example
• Show that if n is an integer greater than 1, then n can be written as
the product of primes.

• 1 - Hypothesis P(n) - n can be written as the product of primes.

• 2 – Base case – P(2) 2 can be written a 2 (the product of itself)

• 3 – Inductive Hypothesis - P(j) is true for  2 ≤j ≤k, j integer.

• 4 – Inductive step?
•
a) k+1 is prime – in this case it’s the product of itself;
b) k+1 is a composite number and it can be written
as the product of two positive integers a and b, with 2 ≤a ≤ b ≤
k+1. By the inductive hypothesis, a and b can be written as the
product of primes, and so does k+1
Strong Induction vs. Induction

• Sometimes strong induction is easier to use.

• It can be shown that strong induction and induction are equivalent:

• - any proof by induction can easily be written as a proof by

strong induction (why?)

• - any proof by strong induction can be converted into a proof

by induction – but not that obvious

• Strong induction also referred to as complete induction; in this

context induction is referred to as incomplete induction.

24
Strong Induction:
Polygon Triangulation
• Theorem: A simple polygon with n sides, where n is an integer with
n≥3, can be triangulated into (n-2) triangles.

n=7
5 triangles
(2 different
triangulations)

How would we prove it? 25

• Hypothesis (to be proved):
• T(n) – every polygon with n sides can be triangulated in n-2
triangles

• Base Case: T(3), a polygon with three sides is a (one) triangle.

• Inductive Hypothesis: T(j), i.e, all simple polygons with j sides can
be triangulated in j-2 triangles, is true for all integers 3≤j ≤k.

• Inductive Step – assuming inductive hypothesis, show T(k+1), i.e.,

every simple polygon of k+1 sides can be triangulated in k+1-2 = k-
1 triangles
• Inductive Step – assuming T(j), i.e, all polygons with j sides can be
triangulated in j-2 triangles, is true for all integers 3≤j ≤k, show
T(k+1), i.e., every single polygon of k+1 sides can be triangulated in
k+1-2 = k-1 triangles.

• First, we split the polygon with (k+1) sides into two polygons:
• Q with s sides and R with t sides.
• #sides of P = k+1 = #sides of Q + #sides of R – 2 = s + t – 2
• (we counted the new (internal) diagonal twice)
• Also 3≤s ≤k and 3≤t ≤k both Q and R have at least one fewer side
than P, and therefore by IH we can triangulate Q into s-2 and R into
t-2 triangles respectively.
• These triangulations with s-2+t-2 = s+t-4= (k+1)-2 triangles
constitute a valid triangulation for P.
QED
Postage: Induction
• Prove that every amount of postage of 12 cents or more can be formed
using just 4-cent and 5-cent stamps.
• Hypothesis: Every amount of postage of 12 cents or more can be formed
using just 4-cent or 5-cent stamps.
• Base case: P(12) postage of 12 cents can be formed using just 4-cent or 5-
cent stamps, 12=3(4).
• Inductive Hypothesis: P(k) postage of k cents can be formed using just 4-
cent or 5-cent stamps

• Inductive step: P(k)→ P(k+1), given P(k).

• Let’s assume P(k), k12. There are two cases for k+1:
• a) at least one 4-cent stamp was used to form postage of k cents --- in
that case with the extra cent we replace this stamp with a 5-cent stamp.
• b) no extra 4-cent was used to form postage of k cents --- in that case
we only used 5 cent stamps; given that k>=12, it has to be at least 15, in
which case we need at least three 5-cent stamps. We can replace three 5
cent stamps with four 4-cent stamps to form postage of k+1 cents.

QED
Postage:
Strong Induction

• Prove that every amount of postage of 12 cents or more can be

formed using just 4-cent and 5-cent stamps.
• Hypothesis: Every amount of postage of 12 cents or more can be
formed using just 4-cent or 5-cent stamps
• Base case: P(12) 12=3(4); P(13) 13=2(4)+1(5); P(14) 14=1(4)+2(5) P(15)
15=3(5), so 12n15, P(n).
• Inductive Hypothesis: P(j) postage, j, 12jk, k  15 cents can be
formed using just 4-cent or 5-cent stamps

• Inductive step: Assuming j 12jk P(j), k 15, we want to show

P(k+1).
• Note 12k−3k, so P(k−3), so add a 4-cent stamp to get postage for
k+1.

So, shortens/simplifies standard induction proof. QED

Recursive Defined Structures and Introduction
to Structural Induction
• Many structures in Computer Science are recursively defined, i.e
parts of them exhibit the same characteristics and have the same
properties as the whole!
• They are also “well-ordered”, in the sense that they exhibit a “well-
founded partial order”, like the order ≤ of Z or ⊆ for sets.
• Structural induction is a proof methodology similar to
mathematical induction, only instead of working in the domain of
positive integers (N) it works in the domain of such recursively
defined structures!
• It is terrifically useful for proving properties of such structures.
• Its structure is sometimes “looser” than that of mathematical
induction.

30
EXAMPLE- A BINARY TREE CONSTRUCTION

What is the
property??

31
Recursive Definition of Binary Tree

• Definition (Non-empty binary tree)

• A non-empty binary tree T is either:
• Base case: A root node r with no pointers, or
• Recursive (or inductive) step: A root node r pointing to 2
• non-empty binary trees TL and TR

• Prove that Claim: |V | = |E| + 1

• The number of vertices (|V |) of a non-empty binary tree T is the
number of its edges (|E|) plus one.

32
The proof

33
One Example for You

• Definition (Height of a non-empty binary tree)

• The height h(T ) of a non-empty binary tree T is defined as follows:
(Base case:) If T is a single root node r, h(r) = 0. (Recursive step:) If T is a
root node connected to two
• “sub-trees” TL and TR, h(T ) = max{h(TR), h(TL)} + 1

• A non-empty binary tree T of height h(T ) has at most 2h(T )+1 − 1

• nodes. Prove using Structural Induction.

34
The proof explained

• Proof. By induction on h(T).

• Let N(h) be number of nodes in a perfect tree of height h.
• Base case: when h = 0, tree is a single node. N(0) = 1 = 20+1 - 1.
• Induction step: Assume N(i) = 2i+1 - 1 for 0 ≤ i < h.
• A perfect binary tree of height h consists of 2 perfect binary trees of
height h-1 plus the root:
• N(h) = 2 × N(h - 1) + 1
• = 2 × (2h-1+1 - 1) + 1
• = 2 × 2h - 2 + 1 = 2h+1 - 1
• 2h are leaves 2h - 1 are internal nodes

35
36