Chapter 5: Q57E (page 360)
Use strong induction to prove that a function F defined by specifying F (0) and a rule for obtaining F (n + 1) from the values F (k) for k = 0,1,2,......n is well defined.
p (n) is true for all integers n.
Over 30 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 where n is a nonnegative integer.
Prove that the recursive algorithm for finding the sum of the first n positive integers you found in Exercise 8 is correct.
Assume that a chocolate bar consists of n squares arranged in a rectangular pattern. The entire bar, a smaller rectangular piece of the bar, can be broken along a vertical or a horizontal line separating the squares. Assuming that only one piece can be broken at a time, determine how many breaks you must successfully make to break the bar into n separate squares. Use strong induction to prove your answer
Devise a recursive algorithm to find a, where a is a real number and n is a positive integer. [Hint: Use the equality .]
Let be the statement that in a triangulation of a simple polygon with 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 is true for all integers runs into difficulties.
b) Show that we can prove that is true for all integers by proving by strong induction the stronger statement for all integers , 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.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
