Chapter 5: Q2SE (page 379)
Use mathematical induction to show that
whenever nis a positive integer.
Short Answer
It is shown that whenevernis a positive integer.
Chapter 5: Q2SE (page 379)
Use mathematical induction to show that
whenever nis a positive integer.
It is shown that whenevernis a positive integer.
All the tools & learning materials you need for study success - in one app.
Get started for freeProve that
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 carries out, exactlyn -1 moves are required to assemble a puzzle with n pieces.
Prove that if h > - 1 , then for all nonnegative integers n. This is called Bernoulli’s inequality.
Devise a recursive algorithm for computing where n is a nonnegative integer, using the fact that . Then prove that this algorithm is correct.
The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and be positive integers, and let S be the set of positive integers of the form , where s and t are integers.
a) Show that s is nonempty.
b) Use the well-ordering property to show that s has a smallest element .
c) Show that if d is a common divisor of a and b, then d is a divisor of c.
d) Show that c I a and c I b. [Hint: First, assume that . Then , where . Show that , contradicting the choice of c.]
e) Conclude from (c) and (d) that the greatest common divisor of a and b exists. Finish the proof by showing that this greatest common divisor is unique.
What do you think about this solution?
We value your feedback to improve our textbook solutions.