Chapter 5: Q18E (page 370)
Prove that Algorithm 1 for computing n! when n is a nonnegative integer is correct.
The required algorithm is proved by induction.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
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 top edge, respectively.]
Prove that the recursive algorithm that you found in Exercise 10 is correct.
Let P (n) be the statement that a postage of n cents can be 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.
Let be the statement that a postage of n cents can be formed using 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that is true for .
(a) Show statements and 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 this inductive step?
(d) Complete the inductive step for .
(e) Explain why these steps show that statement is true whenever
Describe a recursive algorithm for multiplying two nonnegative integers x and y based on the fact that xy = 2 (x . (y / 2)) when y is even and xy = 2 (x . [y / 2]) + x when y is odd, together with the initial condition xy = 0 when y = 0 .
What do you think about this solution?
We value your feedback to improve our textbook solutions.
