Page 364 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 343

∗∗ 20. Suppose that P is a simple polygon with vertices a) Explain where a proof using strong induction that
v 1 , v 2 ,..., v n listed so that consecutive vertices are con- E(n) is true for all integers n ≥ 4 runs into difficulties.
nectedbyanedge,andv 1 andv n areconnectedbyanedge. b) Show that we can prove that E(n) is true for all inte-
A vertex v i is called an ear if the line segment connecting gers n ≥ 4 by proving by strong induction the stronger
the two vertices adjacent to v i is an interior diagonal of the statement T (n) for all integers n ≥ 4, which states that
simple polygon. Two ears v i and v j are called nonover- in every triangulation of a simple polygon, at least two
lapping if the interiors of the triangles with vertices v i of the triangles in the triangulation have two sides bor-
and its two adjacent vertices and v j and its two adjacent dering the exterior of the polygon.
vertices do not intersect. Prove that every simple polygon ∗ 24. A stable assignment, defined in the preamble to Exer-
with at least four vertices has at least two nonoverlapping cise 60 in Section 3.1, is called optimal for suitors if no
ears.
stable assignment exists in which a suitor is paired with
21. In the proof of Lemma 1 we mentioned that many in-
a suitee whom this suitor prefers to the person to whom
correct methods for finding a vertex p such that the
this suitor is paired in this stable assignment. Use strong
line segment bp is an interior diagonal of P have been induction to show that the deferred acceptance algorithm
published. This exercise presents some of the incorrect produces a stable assignment that is optimal for suitors.
ways p has been chosen in these proofs. Show, by con-
sidering one of the polygons drawn here, that for each of 25. Suppose that P(n) is a propositional function. Determine
these choices of p, the line segment bp is not necessarily for which positive integers n the statement P(n) must be
an interior diagonal of P. true, and justify your answer, if
a) P(1) is true; for all positive integers n,if P(n) is true,
a) p is the vertex of P such that the angle ∠abp is small-
est. then P(n + 2) is true.
b) p is the vertex of P with the least x-coordinate (other b) P(1) and P(2) are true; for all positive integers n,if
than b). P(n) and P(n + 1) are true, then P(n + 2) is true.
c) p is the vertex of P that is closest to b. c) P(1) is true; for all positive integers n,if P(n) is true,
then P(2n) is true.
a
a d) P(1) is true; for all positive integers n,if P(n) is true,
then P(n + 1) is true.
p f 26. Suppose that P(n) is a propositional function. Determine
b for which nonnegative integers n the statement P(n) must
q b
g be true if
p
a) P(0) is true; for all nonnegative integers n,if P(n) is
s true, then P(n + 2) is true.
r b) P(0) is true; for all nonnegative integers n,if P(n) is
c
d h true, then P(n + 3) is true.
c) P(0) and P(1) are true; for all nonnegative integers n,
if P(n) and P(n + 1) are true, then P(n + 2) is true.
c e
Exercises 22 and 23 present examples that show inductive d) P(0) is true; for all nonnegative integers n,if P(n) is
loading can be used to prove results in computational geom- true, then P(n + 2) and P(n + 3) are true.
etry. 27. Show that if the statement P(n) is true for infinitely many
∗ 22. Let P(n) be the statement that when nonintersecting di- positive integers n and P(n + 1) → P(n) is true for all
agonals are drawn inside a convex polygon with n sides, positive integers n, then P(n) is true for all positive inte-
at least two vertices of the polygon are not endpoints of gers n.
any of these diagonals. 28. Let b be a fixed integer and j a fixed positive inte-
a) Show that when we attempt to prove P(n) for all inte- ger. Show that if P(b), P(b + 1),...,P(b + j) are true
gersnwithn ≥ 3usingstronginduction,theinductive and[P(b) ∧ P(b + 1) ∧ ··· ∧ P(k)]→ P(k + 1)istrue
step does not go through. for every integer k ≥ b + j, then P(n) is true for all
b) Show that we can prove that P(n) is true for all inte- integers n with n ≥ b.
gers n with n ≥ 3 by proving by strong induction the
stronger assertion Q(n), for n ≥ 4, where Q(n) states 29. What is wrong with this “proof” by strong induction?
that whenever nonintersecting diagonals are drawn in- “Theorem” For every nonnegative integer n,5n = 0.
side a convex polygon with n sides, at least two non-
adjacent vertices are not endpoints of any of these Basis Step: 5 · 0 = 0.
diagonals. Inductive Step: Suppose that 5j = 0 for all nonneg-
23. Let E(n) be the statement that in a triangulation of a sim- ative integers j with 0 ≤ j ≤ k. Write k + 1 = i + j,
ple polygon with n sides, at least one of the triangles in where i and j are natural numbers less than k + 1. By the
the triangulation has two sides bordering the exterior of inductive hypothesis, 5(k + 1) = 5(i + j) = 5i + 5j =
the polygon. 0 + 0 = 0.