Methods of Proof Example

One way of proving things is by induction. Theorem n is odd iff (in and only if) n2 is odd, for
• That’s coming next. n ∈ Z.

What if you can’t use induction? Proof: We have to show

Typically you’re trying to prove a statement like “Given 1. n odd ⇒ n2 odd
X, prove (or show that) Y ”. This means you have to
2. n2 odd ⇒ n odd
prove
X⇒Y For (1), if n is odd, it is of the form 2k + 1. Hence,
In the proof, you’re allowed to assume X, and then show n2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1
that Y is true, using X.
Thus, n2 is odd.
• A special case: if there is no X, you just have to prove For (2), we proceed by contradiction. Suppose n2 is odd
Y or true ⇒ Y . and n is even. Then n = 2k for some k, and n2 = 4k 2.
Thus, n2 is even. This is a contradiction. Thus, n must
Alternatively, you can do a proof by contradiction: As- be odd.
sume that Y is false, and show that X is false.
• This amounts to proving
¬Y ⇒ ¬X

1 2

A Proof By Contradiction Induction

√
Theorem: 2 is irrational. This is perhaps the most important technique we’ll learn
√ for proving things.
Proof: By contradiction. Suppose 2 is rational. Then
√
2 = a/b for some a, b ∈ N +. We can assume that a/b Idea: To prove that a statement is true for all natural
is in lowest terms. numbers, show that it is true for 1 (base case or basis
• Therefore, a and b can’t both be even. step) and show that if it is true for n, it is also true for
n + 1 (inductive step).
Squaring both sides, we get
• The base case does not have to be 1; it could be 0, 2,
2 = a2/b2 3, . . .
Thus, a2 = 2b2, so a2 is even. This means that a must • If the base case is k, then you are proving the state-
be even. ment for all n ≥ k.
Suppose a = 2c. Then a2 = 4c2.
It is sometimes quite difficult to formulate the statement
Thus, 4c2 = 2b2, so b2 = 2c2. This means that b2 is even, to prove.
and hence so is b.
IN THIS COURSE, I WILL BE VERY FUSSY ABOUT
Contradiction!
√ THE FORMULATION OF THE STATEMENT TO PROVE.
Thus, 2 must be irrational. YOU MUST STATE IT VERY CLEARLY. I WILL ALSO
BE PICKY ABOUT THE FORM OF THE INDUC-
TIVE PROOF.

3 4
 Writing Up a Proof by Induction A Simple Example

Theorem: For all positive integers n,

1. State the hypothesis very clearly:
n
X n(n + 1)
• Let P (n) be the (English) statement . . . [some state- k= .
k=1 2
ment involving n]
2. The basis step Proof: By induction. Let P (n) be the statement
n
X n(n + 1)
• P (k) holds because . . . [where k is the base case, k= .
usually 0 or 1] k=1 2
1(1+1)
3. Inductive step Basis: P (1) asserts that P1k=1 k = 2
. Since the LHS
• Assume P (n). We prove P (n + 1) holds as follows and RHS are both 1, this is true.
. . . Thus, P (n) ⇒ P (n + 1). Inductive step: Assume P (n). We prove P (n + 1).
4. Conclusion Note that P (n + 1) is the statement
n+1
X (n + 1)(n + 2)
• Thus, we have shown by induction that P (n) holds k= .
for all n ≥ k (where k was what you used for your k=1 2
basis step). [It’s not necessary to always write the Pn+1
conclusion explicitly.] k=1 k = Pnk=1 k + (n + 1)
= n(n+1)
2 + (n + 1)[Induction hypothesis]
= n(n+1)+2(n+1)
2
= (n+1)(n+2)
2
Thus, P (n) implies P (n + 1), so the result is true by
induction.
5 6

Notes: Another example

P (n)
• You can write = instead of writing “Induction hy-
pothesis” at the end of the line, or you can write
“P (n)” at the end of the line. Theorem: (1+x)n ≥ 1+nx for all nonnegative integers
n and all x ≥ −1. (Take 00 = 1.)
◦ Whatever you write, make sure it’s clear when
you’re applying the induction hypothesis Proof: By induction on n. Let P (n) be the statement
(1 + x)n ≥ 1 + nx.
• Notice how we rewrite Pn+1
k=1 k so as to be able to ap-
peal to the induction hypothesis. This is standard Basis: P (0) says (1 + x)0 ≥ 1. This is clearly true.
operating procedure. Inductive Step: Assume P (n). We prove P (n + 1).

(1 + x)n+1 = (1 + x)n(1 + x)
≥ (1 + nx)(1 + x)[Induction hypothesis]
= 1 + nx + x + nx2
= 1 + (n + 1)x + nx2
≥ 1 + (n + 1)x
• Why does this argument fail if x < −1?

7 8
 Towers of Hanoi Solution
• Move top n − 1 rings from pole 1 to pole 3 (we can
do this by assumption)
◦ Pretend largest ring isn’t there at all
• Move largest ring from pole 1 to pole 2
• Move top n − 1 rings from pole 3 to pole 2 (we can
do this by assumption)
◦ Again, pretend largest ring isn’t there
This solution translates to a recursive algorithm:
• Suppose robot(r → s) is a command to a robot to
move the top ring on pole r to pole s
Problem: Move all the rings from pole 1 and pole 2, • Note that if r, s ∈ {1, 2, 3}, then 6 − r − s is the other
moving one ring at a time, and never having a larger ring number in the set
on top of a smaller one.
How do we solve this? procedure H(n, r, s) [Move n disks from r to s]
if n = 1 then robot(r → s)
• Think recursively! else H(n − 1, r, 6 − r − s)
• Suppose you could solve it for n − 1 rings? How could robot(r → s)
you do it for n? H(n − 1, 6 − r − s, s)
endif
return
endpro

9 10

Towers of Hanoi: Analysis A Matching Lower Bound

Theorem: It takes 2n − 1 moves to perform H(n, r, s), Theorem: Any algorithm to move n rings from pole r
for all positive n, and all r, s ∈ {1, 2, 3}. to pole s requires at least 2n − 1 steps.
Proof: Let P (n) be the statement “It takes 2n −1 moves Proof: By induction, taking the statement of the theo-
to perform H(n, r, s) and all r, s ∈ {1, 2, 3}.” rem to be P (n).
• Note that “for all positive n” is not part of P (n)! Basis: Easy: Clearly it requires (at least) 1 step to move
• P (n) is a statement about a particular n. 1 ring from pole r to pole s.

• If it were part of P (n), what would P (1) be? Inductive step: Assume P (n). Suppose you have a se-
quence of steps to move n + 1 rings from r to s. There’s
Basis: P (1) is immediate: robot(r → s) is the only move a first time and a last time you move ring n + 1:
in H(1, r, s), and 21 − 1 = 1. • Let k be the first time
Inductive step: Assume P (n). To perform H(n+1, r, s), • Let k 0 be the last time.
we first do H(n, r, 6 − r − s), then robot(r → s), then
H(n, 6 − r − s, s). Altogether, this takes 2n − 1 + 1 + • Possibly k = k 0 (if you only move ring n + 1 once)
2n − 1 = 2n+1 − 1 steps. Suppose at step k, you move ring n + 1 from pole r to
pole s0.
• You can’t assume that s0 = s, although this is opti-
mal.

11 12
Key point: Strong Induction
0
• The top n rings have to be on the third pole, 6−r −s
• Otherwise, you couldn’t move ring n + 1 from r to s0. Sometimes when you’re proving P (n + 1), you want to
By P (n), it took at least 2n − 1 moves to get the top n be able to use P (j) for j ≤ n, not just P (n). You can
rings to pole 6 − r − s0. do this with strong induction.
At step k 0, the last time you moved ring n + 1, suppose 1. Let P (n) be the statement . . . [some statement involv-
you moved it from pole r0 to s (it has to end up at s). ing n]
• the other n rings must be on pole 6 − r0 − s. 2. The basis step
n
• By P (n), it takes at least 2 − 1 moves to get them • P (k) holds because . . . [where k is the base case,
to ring s (where they have to end up). usually 0 or 1]
So, altogether, there are at least 2(2n − 1) + 1 = 2n+1 − 1 3. Inductive step
moves in your sequence:
• Assume P (k), . . . , P (n) holds. We show
• at least 2n − 1 moves before step k P (n + 1) holds as follows . . .
• at least 2n − 1 moves after step k 0 Although strong induction looks stronger than induction,
• step k itself. it’s not. Anything you can do with strong induction,
you can also do with regular induction, by appropriately
If course, if k 6= k 0 (that is, if you move ring n + 1 more
modifying the induction hypothesis.
than once) there are even more moves in your sequence.
• If P (n) is the statement you’re trying to prove by
strong induction, let P 0(n) be the statement P (1), . . . , P (n)
hold. Proving P 0(n) by regular induction is the same
as proving P (n) by strong induction.

13 14

An example using strong induction Bubble Sort

Theorem: Any item costing n > 7 kopecks can be Suppose we wanted to sort n items. Here’s one way to
bought using only 3-kopeck and 5-kopeck coins. do it:
Proof: Using strong induction. Let P (n) be the state- Input n [number of items to be sorted]
ment that n kopecks can be paid using 3-kopeck and 5- w1, . . . , wn [items]
kopeck coins, for n ≥ 8.
Algorithm BubbleSort
Basis: P (8) is clearly true since 8 = 3 + 5.
for i = 1 to n − 1
Inductive step: Assume P (8), . . . , P (n) is true. We for j = 1 to n − i
want to show P (n + 1). If n + 1 is 9 or 10, then it’s if wj > wj+1 then switch(wj , wj+1) endif
easy to see that there’s no problem (P (9) is true since endfor
9 = 3 + 3 + 3, and P (10) is true since 10 = 5 + 5). endfor
Otherwise, note that (n + 1) − 3 = n − 2 ≥ 8. Thus,
P (n − 2) is true, using the induction hypothesis. This Why is this right:
means we can use 3- and 5-kopeck coins to pay for some-
• Intuitively, because largest elements “bubble up” to
thing costing n−2 kopecks. One more 3-kopeck coin pays
the top
for something costing n + 1 kopecks.
How many comparisons?
• Best case, worst case, average case all the same:
◦ (n − 1) + (n − 2) + · · · + 1 = n(n − 1)/2

15 16
 Proving Bubble Sort Correct Inductive step: Suppose that Q(l) is true. If l+1 ≥ n−1,
then Q(l + 1) is vacuously true. If l + 1 < n, by Q(l), we
know that wl+1 > wj , for j = 1, . . . , l after l iterations.
We want to show that the algorithm is correct by induc- The (l + 1)st iteration of the inner loop compares wl+1
tion. What’s the statement of the induction? and wl+2. After the (l + 1)st iteration, the bigger one is
Could take P (n) to be the statement: the algorithm wl+2. Thus, wl+2 > wl+1. By the induction hypothesis,
works correctly for n inputs. wl+2 > wj , for j + 1, . . . , l.
• That turns out to be a tough induction statement to That completes the nested induction. Thus, Q(l) holds
work with. for all l. Q(n−1) says that wn > wj for j = 1, . . . , n−1.
That’s just what P (1) says. So we’re done with the base
• Suppose P (1) is true. How do you prove P (2)?
case of the main induction.
A better choice: [Note: For a really careful proof, we need better notation
• P (k) is the statement that, if there are n inputs and (for value of wl before and after the switch).]
k ≤ n − 1, then after k iterations of the outer loop,
Inductive step (for main induction): Assume P (k).
wn−k+1, . . . , wn are the k largest items, sorted in the
Thus, wk+1, . . . , wn are the k largest items. To prove
right order.
P (k + 1), we use nested induction again:
◦ Note that P (k) is vacuously true if k ≥ n.
• Now Q(l) says “if i = k + 1, then if l ≤ n − (k + 1),
Basis: How do we prove P (1)? By a nested induction! after l iterations of the inner loop, wl+1 > wj , for
j = 1, . . . , l.”
This time, take Q(l) to be the statement that, if l ≤ n−1,
then after l iterations of the inner loop, wl+1 > wj , for • Almost the same as before, except that instead of say-
j = 1, . . . , l. ing “if l ≤ n − 1”, we say “if l ≤ n − (k + 1).”
Basis: Q(1) holds because after the first iteration of the ◦ If i = k + 1, we go through the inner loop only
inner loop, w2 > w1 (thanks to the switch statement). n − (k + 1) times.
17 18

Q(n − k − 1) says that, after the (k + 1)st iteration of the How to Guess What to Prove
inner loop, wn−k > wj for j = 1, . . . , k. P (k) says that
the top k elements are wn−k+1, . . . , wn, in that order.
Thus, the top k + 1 elements must be wn−k , . . . wn, in Sometimes formulating P (n) is straightforward; some-
that order. This proves P (k + 1). times it’s not. This is what to do:
Note that P (n − 1) says that after n − 1 iterations of the • Compute the result in some specific cases
outer loop (which is all there are), the top n − 1 elements • Conjecture a generalization based on these cases
are w2, . . . , wn. So w1 has to be the smallest element,
and w1, w2, . . . , wn is a sorted list. • Prove the correctness of your conjecture (by induc-
tion)

19 20
 Example

Suppose a1 = 1 and an = adn/2e + abn/2c for n > 1. Find

an explicit formula for an.
Try to see the pattern:
• a1 = 1
• a2 = a1 + a1 = 1 + 1 = 2
• a3 = a2 + a1 = 2 + 1 = 3
• a4 = a2 + a2 = 2 + 2 = 4
Suppose we modify the example. Now a1 = 3 and an =
adn/2e + abn/2c for n > 1. What’s the pattern?
• a1 = 3
• a2 = a1 + a1 = 3 + 3 = 6
• a3 = a2 + a1 = 6 + 3 = 9
• a4 = a2 + a2 = 6 + 6 = 12
an = 3n!

21