Mathematical Foundations of Computer Science
Lecture Outline
September 18, 2018
Example. Prove that the sum of the first n positive odd numbers is n2 .
Solution. We want to prove that ∀ positive integers n, P (n) where P (n) is the following
property.
n−1
X
2i + 1 = n2
i=0
Base Case: We want to show that P (1) is true. This is clearly true as
0
X
2i + 1 = 1 = 12
i=0
Induction Hypothesis: Assume P (k) is true for some k ≥ 1.
Induction Step: We want to show that P (k + 1) is true, i.e., we want to show that
k
X
2i + 1 = (k + 1)2
i=0
We can do this as follows.
k
X k−1
X
2i + 1 = 2i + 1 + 2k + 1
i=0 i=0
= k 2 + 2k + 1 (using induction hypothesis)
2
= (k + 1)
Example. Show that for all integers n ≥ 0, if r 6= 1,
n
X a(rn+1 − 1)
ari =
r−1
i=0
2 Lecture Outline September 18, 2018
Solution. Let r be any real number that is not equal to 1. We want to prove that ∀
integers n, P (n), where P (n) is given by
n
X a(rn+1 − 1)
ari =
r−1
i=0
Base Case: We want to show that P (0) is true.
0
X a(r − 1)
ari = a =
r−1
i=0
Induction Hypothesis: Assume that P (k) is true for some k ≥ 0.
Induction Step: We want to show that P (k + 1) is true, i.e., we want to prove that
k+1
X a(rk+2 − 1)
ari =
r−1
i=0
We can do this as follows.
k+1
X
L.H.S. = ari
i=0
Xk
= ari + ark+1
i=0
ark+1 −a
= + ark+1
r−1
a(rk+1 − 1) ark+1 (r − 1)
= +
r −1 r−1
a k+1
= r (1 + r − 1) − 1
r−1
a
= rk+2 − 1
r−1
a(rk+2 − 1)
=
r−1
Example. Prove that ∀ non-negative integers n,
n
X
2i = 2n+1 − 1
i=0
Solution. By setting a = 1, r = 2 in the result of the previous problem, the claim follows.
September 18, 2018 Lecture Outline 3
Example. Prove that ∀ non-negative integers n, 22n − 1 is a multiple of 3.
Solution. We want to prove that ∀ non-negative integers n, P (n), where P (n) is
22n − 1 = 3k, for some non-negative integer k
Base Step: P (0) is true as shown below.
20 − 1 = 0 = 3 · 0.
Induction Hypothesis: Assume that P (x) is true for some x ≥ 0, i.e., 22x − 1 = 3 · k 0 , for
some k 0 ≥ 0.
Induction Step: We want to prove that P (x + 1) is true, i.e., we want to show that
22(x+1) − 1 = 3l, for some non-negative integer l.
We can show this as follows.
L.H.S. = 22(x+1) − 1
= 22x+2 − 1
= 22x · 22 − 1
= 22x · 4 − 1
= 22x · (3 + 1) − 1
= 3 · 22x + 22x − 1
= 3 · 22x + 3 · k 0 (using induction hypothesis)
2x 0
= 3(2 +k)
= 3l, where l = 22x + k 0
Since x and k 0 are integers l is also an integer. Hence, P (x + 1) is true.
Example. Prove that ∀n ∈ N, n > 1 → n! < nn .
Solution. Below is a simple direct proof for this inequality.
n! = 1 × 2 × 3 × · · · × n
< n × n × n × ··· × n
= nn
We now give a proof using induction. Let P (n) denote the following property.
n! < nn
Induction Hypothesis: Assume that P (k) is true for some k > 1.
Base Case: We want to prove P (2). P (2) is the proposition that 2! < 22 , or 2 < 4, which
4 Lecture Outline September 18, 2018
is true.
Induction Step: We want to prove P (k +1), i.e., we want to prove that (k +1)! < (k +1)k+1 .
L.H.S. = (k + 1)!
= k! × (k + 1)
< k k × (k + 1) (using induction hypothesis)
k
< (k + 1) × (k + 1) (since k > 1)
= (k + 1)k+1
Example. Recall that for any set A, P(A) denotes the power set of A. Let S =
{x1 , x2 , . . . , xn }. Prove using induction that for all positive integers n, |P(S)| = 2n .
Solution. We will prove the claim using induction on n.
Induction Hypothesis: Assume that the claim is true when n = k, for some k ≥ 1. In other
words, assume that if S = {x1 , x2 , . . . , xk }, then |P(S)| = 2k .
Base Case:n = 1. When S = {x1 }, there are exactly two subsets of S, namely ∅ and S,
itself. Thus the claim is true when n = 1.
Induction Step: We want to prove that the claim is true when n = k + 1. In other
words, we want to show that if S = {x1 , x2 , . . . , xk , xk+1 }, then |P(S)| = 2k+1 . Let
S 0 = {x1 , x2 , . . . , xk }. The set of all subsets of S can be partitioned into S1 and S2 ,
where S1 ⊂ P(S) contains subsets of S that does not contain xk+1 , and S2 ⊂ S contains
subsets of P(S) that contains xk+1 . Thus we have
|P(S)| = |S1 | + |S2 | (1)
Note that S1 contains all subsets of P(S 0 ). By the induction hypothesis, we have |S1 | =
|P(S 0 )| = 2k . We will now compute |S2 |. Observe that each set in S2 is of the form
{xk+1 } ∪ X, where X is a subset of S 0 . By induction hypothesis, we know that there are
2k subsets of S 0 and hence |S2 | = 2k . Plugging in the values for |S1 | and |S2 | in (1), we get
|P(S)| = 2k + 2k = 2k+1
Example Let A1 , A2 , . . . , An be sets (where n ≥ 2). Suppose for any two sets Ai and Aj
either Ai ⊆ Aj or Aj ⊆ Ai . Prove by induction that one of these n sets is a subset of all of
them.
Solution. We will prove the claim using induction on n.
Induction Hypothesis: Assume that the claim is true when n = k, for some k ≥ 2. In other
words, assume that if we have sets A1 , A2 , . . . , Ak , where for any two sets Ai and Aj , either
Ai ⊆ Aj or Aj ⊆ Ai then one of the k sets is a subset of all of the k sets.
Base Case: n = 2. We have two sets A1 , A2 and we know that A1 ⊆ A2 or A2 ⊆ A1 .
Without loss of generality assume that A1 ⊆ A2 . Then A1 is a subset of A1 and is also a
September 18, 2018 Lecture Outline 5
subset of A2 , so the claim holds when n = 2.
Induction Step: We want to prove the claim when n = k + 1. That is, we are given a set
S = {A1 , A2 , . . . , Ak+1 } of with the property that for every pair of sets Ai ∈ S and Aj ∈ S,
either Ai ⊆ Aj or Aj ⊆ Ai . We want to show that there is a set in S that is a subset of all
k + 1 sets in S. Let S 0 = S \ {Ak+1 }. By induction hypothesis, there is a set Ap ∈ S 0 that
is a subset of all sets in S 0 . We now consider the following two cases.
Case 1 : Ap ⊆ Ak+1 . Then it follows that Ap is a subset of all sets in S.
Case 2 : Ak+1 ⊆ Ap . Since Ap is a subset of all sets in S 0 and Ak+1 ⊆ Ap , it follows that
Ak+1 is a subset of all sets in S.
Example. For all n ≥ 1, prove that n lines separate the plane into (n2 + n + 2)/2 regions.
Assume that no two of these lines are parallel and no three pass through a common point.
Solution. Let P (n) be the property that n lines, such that no two of them are parallel
and no three of them pass through a common point, separate the plane into (n2 + n + 2)/2
regions. We will prove the claim by induction on n.
Induction Hypothesis: Assume that P (k) is true for some k > 0.
Base Case: P (1) is true since one line divides the plane into 2 regions which is also given
by (12 + 1 + 2)/2.
Induction Step: To prove that P (k + 1) is true. Consider a set S of k + 1 lines such that no
two of them are parallel and no three of them pass through a common point. Remove any
line ` from the set S. Let S 0 be the resulting set of k lines. By induction hypothesis, the k
lines in S 0 divide the plane into (k 2 + k + 2)/2 regions. Now we add the line ` to the set
S 0 to obtain the set S. Line ` intersects exactly once with each of the k lines in S 0 . These
intersections divide the line ` into k + 1 line segments. Each of these line segments passes
through a region and hence k + 1 additional regions are created. Hence, the total number
of regions formed by k + 1 lines is given by
k2 + k + 2 k 2 + 3k + 4 k 2 + 2k + 1 + k + 3 (k + 1)2 + (k + 1) + 2
+k+1= = =
2 2 2 2
Thus P (k + 1) is correct and this completes the proof.
