Lec 14
Lec 14
Lec 14
1. Formal Setting.
Mathematical Induction is used to prove theorems of the form ∀n ∈ N : P (n) where P is
some predicate with the natural numbers as the domain of discourse. Formally, it is stated
as follows
P (1) ∧ (∀k ∈ N : P (k) ⇒ P (k + 1)) ⇒ (∀n ∈ N : P (n)) (PMI)
In plain English, it asserts that to prove the statement “P (n) is true for all n ∈ N.”, it suffices
to prove
• The Base Case:(often easy) Prove that P (0) is true; and
• The Inductive Case:(the meat!) For any natural number k, if P (k) is true, then prove
that P (k + 1) is true.
In the inductive case, the assumption that “P (k) is true” is called the Induction Hypothesis.
2. Meeting an old friend.
Let us use induction to prove something we proved in the first class.
Pn
Theorem 1. For all non-negative integers n, i=1 i = n(n + 1)/2
Pn
The predicate P (n) takes the value true if i=1 i = n(n + 1)/2 and false otherwise. (1) asserts
that P (n) is true for all natural numbers.
Proof. To prove ∀n ∈ N : P (n), the principle of mathematical induction (or simple induction,
henceforth) asks us to check/prove the following.
Base Case: Let us verify that P (1) is true. Indeed, 1i=1 i = 1 and 1(1+1)
P
2 = 1, and thus P (1)
is true.
Inductive Case: Fix any natural number k. The induction hypothesis is that P (k) is true. We
need to prove P (k + 1) is true.
P (k) is true implies
k
X k(k + 1)
i= (Induction Hypothesis)
2
i=1
To prove P (k + 1) is true, that is, we need to show
k+1
X (k + 1)(k + 2)
i= (Need to Show)
2
i=1
1
We establish this by noting that the LHS of (Need to Show) is
k+1 k
X X k(k + 1) k (k + 1)(k + 2)
i= i + (k + 1) = + (k + 1) = (k + 1) · +1 =
2 2 2
i=1 i=1
where in the second inequality we have used the (Induction Hypothesis). Thus, we have
established (Need to Show), and thus ∀n ∈ N : P (n) follows from induction.
b
Exercise: Using induction, prove
Pn 2 n(n+1)(2n+1)
• i=1 i = 6 for any non-negative integer n.
2
Pn 3 n(n+1)
• i=1 i = 2 for any non-negative integer n.
Pn i an+1 −1
• i=1 a = a−1 for any integer a > 1 and non-negative integer n.
Proof. Let P (n) be the predicate representing the truth value of the statement given in the
theorem for a fixed natural number n. We proceed to prove ∀n ∈ N : P (n) by induction.
Base Case: Let us verify P (1). We need to verify that 3 divides 13 − 1 = 0. Indeed, 3 times 0
is 0.
Inductive Case: Let us now assume for a fixed k ∈ N that P (k) is true. That is, 3 divides
k 3 − k. We need to show P (k + 1) is true, that is, 3 divides (k + 1)3 − (k + 1). To do so, we
expand (k + 1)3 , to get
(k + 1)3 − (k + 1) = (k 3 + 3k 2 + 3k + 1) − (k + 1) = (k 3 − k) + 3(k 2 + k)
3(k 2 + k) is divisible by 3, and by the induction hypothesis (that is, P (k) is true), k 3 − k is
divisible by 3. Therefore, (k + 1)3 − (k + 1) is divisible by 3. That is, P (k + 1) is true. By the
principle of mathematical induction, P (n) is true for all n ∈ N.
Remark: But you already knew the above fact, right? Note that n3 − n = n · (n2 − 1). If n ≡ 0
mod 3, then n3 − n is divisible by 3. Otherwise, since 3 is prime, Fermat’s Little Theorem says
n2 − 1 ≡0 3, and thus n3 − n is divisible by 3. It is good to prove the same theorem in more than
one ways.
b
Exercise: Does 4 divide n4 − n for all non-negative integers n? Does 5 divide n5 − n for all
non-negative integers n?
2
Theorem 3. For all n ∈ N, 7 divides 32n − 2n .
Proof. Let P (n) be the predicate representing the truth value of the statement given in the
theorem for a fixed natural number n. We proceed to prove ∀n ∈ N : P (n) by induction.
Base Case: Let us verify P (1). We need to verify that 7 divides 32 − 21 = 7. Indeed it does.
Therefore P (1) is true.
Inductive Case: Let us now assume for a fixed k ∈ N that P (k) is true. That is, 7 divides
32k − 2k . We need to show P (k + 1) is true, that is, 7 divides 32(k+1) − 2(k+1) . Indeed observe,
5. Proving Recursive Programs Correct. Induction is the way to prove recursive programs
correct. For example, consider the following program.
3
Theorem 4. For all positive integers n, FACT(n) returns n!
Proof. We prove by induction the statement ∀n ∈ N : P (n), where P (n) is the predicate
FACT(n) returns n!.
Base Case: Let us verify P (1). By definition of the factorial function, 1! = 1. Now, if n = 1,
then Line (3) returns 1. Thus, the base case is verified; P (1) is indeed true.
Inductive Case: Let us now assume for a fixed k ∈ N that P (k) is true. That is FACT(k) indeed
returns k!. We need to prove P (k + 1), that is, we need to prove FACT(k + 1) returns (k + 1)!.
Inspecting Line (5), we see that FACT(k + 1) returns (k + 1) times the number returned by
FACT(k). By the induction hypothesis, the latter number is k!. Therefore, FACT(k + 1) returns
(k + 1) · k! = (k + 1)!. Therefore, the inductive case is true, and so by induction, the theorem
is proved.
Remark: Sometimes, the induction principle may look as follows: (a) The base case may involve
proving P (1), P (2), . . . , P (c) for some finite c, and (b) The inductive case may be possible only
for numbers k ≥ c. Note this is also perfectly OK to establish ∀n : P (n). We will see such an
example in class and problem sets.