In the proof of Lemma 1 we mentioned that many incorrect

Problem 1E Use strong induction to show that if you can run one mile or two miles, and if you can always run two more miles once you have run a specified number of miles, then you can run any number of miles.

Problem 43E Show that we can prove the well-ordering property when we take strong induction as an axiom instead of taking the well-ordering property as an axiom.

Problem 3E Let P(n) be the statement that a postage of ncentscanbe formed using just 3-cent stamps and 5-cent stamps The parts of this exercise outline a strong induction proof that P(n) is true for n ? 8. a) Show that the statements P(8), P(9), and P(10) are true, completing the basis step of the proof. ________________ b) What is the inductive hypothesis of the proof? ________________ c) What do you need to prove in the inductive step? ________________ d) Complete the inductive step for k ? 10. ________________ e) Explain why these steps show that this statement is true whenever n ? 8.

Problem 6E a) Determine which amounts of postage can be formed using just 3-cent and 10-cent stamps. ________________ b) Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step. ________________ c) Prove your answer to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction?

Problem 4E Let P (n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that P(n) is true for n ? 18. a) Show statements P (18), P(19), P(20), and P(21) are true, completing the basis step of the proof. ________________ b) What is the inductive hypothesis of the proof? ________________ c) What do you need to prove in the inductive step? ________________ d) Complete the inductive step for k ? 21. ________________ e) Explain why these steps show that this statement is true whenever n 18.

Problem 5E a) Determine which amounts of postage can be formed using just 4-cent and 11 -cent stamps. ________________ b) Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step. ________________ c) Prove your answer to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction?

Problem 7E Which amounts of money can be formed using just two- dollar bills and five-dollar bills? Prove your answer using strong induction.

Problem 13E A jigsaw puzzle is put together by successively joining pieces that fit together into blocks. A move is made each time a piece is added to a block, or when two blocks are joined. Use strong induction to prove that no matter how the moves are carried out, exactly n ? 1 moves are required to assemble a puzzle with n pieces.

Problem 16E Prove that the first player has a winning strategy for the game of Chomp, introduced in Example 12 in Section 1.8. if the initial board is two squares wide, that is, a 2 × n board. [Hint: Use strong induction. The first move of the first player should be to chomp the cookie in the bottom row at the far right.]

Use strong induction to prove that \(\sqrt{2}\) is irrational. [Hint: Let \(P(n)\) be the statement that \(\sqrt{2} \neq n / b\) for any positive integer \(b\).] ________________ Equation Transcription: Text Transcription: sqrt{2} P(n) \sqrt{2} \neq n / b b

Problem 11E Consider this variation of the game of Nim. The game begins with n matches. Two players take turns removing matches, one, two. or three at a time. The player removing the last match loses. Use strong induction to show that if each player plays the best strategy possible, the first player wins if n = 4 j, 4j + 2, or 4j + 3 for some nonnegative integer j and the second player wins in the remaining case when n = 4j + 1 for some nonnegative integer j.

Problem 15E Prove that the first player has a winning strategy for the game of Chomp, introduced in Example 12 in Section 1.8, if the initial board is square. [Hint: Use strong induction to show that this strategy works. For the first move, the first player chomps all cookies except those in the left and top edges. On subsequent moves, after the second player has chomped cookies on either the top or left edge, the first player chomps cookies in the same relative positions in the left or to pedge, respectively.]

Problem 17E Use strong induction to show that if a simple polygon with at least four sides is triangulated, then at least two of the triangles in the triangulation have two sides that border the exterior of the polygon.

Problem 18E Use strong induction to show that when a simple polygon P with consecutive vertices v1, v2,…. vn is triangulated into n ? 2 triangles, the n ? 2 triangles can be numbered 1,2 n — 2 so that v,- is a vertex of triangle i for i = l,2 n?2.

Problem 19E Pick's theorem says that the area of a simple polygon P in the plane with vertices that are all lattice points (that is. points with integer coordinates) equals I(P)+B(P)/2-1. where I(P) and B(P) are the number of lattice points in the interior of P and on the boundary of P, respectively. Use strong induction on the number of vertices of P to prove Pick's theorem. [Hint: For the basis step, first prove the theorem for rectangles, then for right triangles, and finally for all triangles by noting that the area of a triangle is the area of a larger rectangle containing it with the areas of at most three triangles subtracted. For the inductive step, take advantage of Lemma 1.]

Problem 20E Suppose that P is a simple polygon with vertices v1, v2,…. vn listed so that consecutive vertices are connected by an edge, and vi and v j are connected by an edge. A vertex v, is called an ear if the line segment connecting the two vertices adjacent to v; is an interior diagonal of the simple polygon. Two ears vi and vj are called nonover-lapping if the interiors of the triangles with vertices vi and its two adjacent vertices and vj and its two adjacent vertices do not intersect. Prove that every simple polygon with at least four vertices has at least two nonoverlapping ears.

Problem 22E Let P(n) be the statement that when nonintersecting diagonals are drawn inside a convex polygon with n sides, at least two vertices of the polygon are not endpoints of any of these diagonals. a) Show that when we attempt to prove P (n) for all integers n with n ? 3 using strong induction, the inductive step does not go through. ________________ b) Show that we can prove that P(n) is true for all integers n with n ? 3 by proving by strong induction the stronger assertion Q(n). for n ? 4, where Q(n) states that whenever nonintersecting diagonals are drawn inside a convex polygon with n sides, at least two non- adjacent vertices are not endpoints of any of these diagonals.

In the proof of Lemma 1 we mentioned that many incorrect methods for finding a vertex \(p\) such that the line segment \(b p\) is an interior diagonal of \(P\) have been published. This exercise presents some of the incorrect ways \(p\) has been chosen in these proofs. Show, by considering one of the polygons drawn here, that for each of these choices of \(p\), the line segment \(b p\) is not necessarily an interior diagonal of \(P\). a) \(p\) is the vertex of \(P\) such that the angle \(\angle a b p\) is smallest. b) \(p\) is the vertex of \(P\) with the least \(x\)-coordinate (other than \(b\) ). c) \(p\) is the vertex of \(P\) that is closest to \(b\). . Exercises 22 and 23 present examples that show inductive loading can be used to prove results in computational geometry. ________________ Equation Transcription: ? Text Transcription: p b p P p p b p P p P \angle a b p p P x b p P b

Problem 23E Let E(n) be the statement that in a triangulation of a simple polygon with n sides, at least one of the triangles in the triangulation has two sides bordering the exterior of the polygon. a) Explain where a proof using strong induction that E(n) is true for all integers n ? 4 runs into difficulties. ________________ b) Show that we can prove that E(n) is true for all integers n ? 4 by proving by strong induction the stronger statement T (n) for all integers n > 4, which states that in every triangulation of a simple polygon, at least two of the triangles in the triangulation have two sides bordering the exterior of the polygon.

Problem 24E A stable assignment, defined in the preamble to Exercise 60 in Section 3.1, is called optimal for suitors if no stable assignment exists in which a suitor is paired with a suitee whom this suitor prefers to the person to whom this suitor is paired in this stable assignment. Use strong induction to show that the deferred acceptance algorithm produces a stable assignment that is optimal for suitors.

Problem 25E Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true, and justify your answer, if a) P(l) is true; for all positive integers n, if P(n) is true, then P(n + 2) is true. ________________ b) P(1) and P(2) are true; for all positive integers n, if P(n) and P(n + 1) are true, then P(n + 2) is true. ________________ c) P(l) is true; for all positive integers n, if P (n) is true, then P (2n) is true. ________________ d) P(1) is true; for all positive integers n, if P(n) is true, then P( n + 1) is true.

Problem 26E Suppose that P(n) is a propositional function. Determine for which nonnegative integers n the statement P (n) must be true if a) P(0) is true; for all nonnegative integers n, if P(n) is true, then P(n + 2) is true. ________________ b) P(0) is true; for all nonnegative integers n, if P(n) is 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(u + 2) is true. ________________ d) P(0) is true; for all nonnegative integers n, if P(n) is true, then P(n + 2) and P(n + 3) are true.

Problem 27E Show that if the statement P(n) is true for infinitely many positive integers n and P(n + 1)? P(n) is true for all positive integers n, then P(n) is true for all positive integers n.

Problem 28E Let b be a fixed integer and j a fixed positive integer. Show that if P(b), P(b + 1) P(b + j) are true and [P(b) ? P(b + 1) a ? ? ? ?? P(k) ]? P(k + 1) is true for every integer k ?b + j, then P(n) is true for all integers n with n? b.

Problem 29E What is wrong with this "proof" by strong induction? "Theorem" For every nonnegative integer n, 5n = 0. Basis Step: 5?0 = 0. Inductive Step: Suppose that 5j = 0 for all nonnegative integers j with 0 ? j ? k. Write k + 1 = i + j. where i and j are natural numbers less than k + 1. By the inductive hypothesis, 5(k + 1) = 5(i + j) = 5i + 5j = 0 + 0 = 0.

Problem 31E Show that strong induction is a valid method of proof by showing that it follows from the well-ordering property.

Problem 33E Show that we can prove that P(n, k) is true for all pairs of positive integers n and k if we show a) P(1,1) is true and P(n. k)? [P(n + 1. k) ? P(n. k + 1)] is true for all positive integers n and k. ________________ b) P(1,k) is true for all positive integers k, and P(n. k) ? P(n,k+1) is true for all positive integers n and k. ________________ c) P(n, 1) is true for all positive integers n. and P(n. k) ? P(n. k + 1) is true for all positive integers n and k.

Problem 35E Show that if a 1, a 2…. an are n distinct real numbers, exactly n ? l multiplications are used to compute the product of these n numbers no matter how parentheses are inserted into their product. [Hint: Use strong induction and consider the last multiplication.]

Problem 37E Let a be an integer and d be a positive integer. Show that the integers q and r with a = dq + r and 0 ? r

Problem 38E Use mathematical induction to show that a rectangular checkerboard with an even number of cells and two squares missing, one white and one black, can be covered by dominoes.

Problem 39E Can you use the well-ordering property to prove the statement: "Every positive integer can be described using no more than fifteen English words"? Assume the words come from a particular dictionary of English. [Hint: Suppose that there are positive integers that cannot be described using no more than fifteen English words. By well ordering, the smallest positive integer that cannot be described using no more than fifteen English words would then exist.]

Problem 40E Use the well-ordering principle to show that if x and y are real numbers with x<y, then there is a rational number r with x<r<y. [Hint: Use the Archimedean property, given in Appendix 1, to find a positive integer A with A > 1/(y ?x). Then show that there is a rational number r with denominator A between x and y by looking at the numbers [x]+ j/A. where j is a positive integer.]

Problem 41E Show that the well-ordering property can be proved when the principle of mathematical induction is taken as an axiom.

Problem 42E Show that the principle of mathematical induction and strong induction are equivalent; that is, each can be shown to be valid from the other.