## Transcribed Text

For this problem, imagine yourself having accidentally traveled back to the future and are now
living in a world in which, among other oddities, instead of pennies, nickels, dimes and quarters,
change must be formed using coins whose values are powers of two. So, a penny is still a penny,
but the next most valuable coin is a 2'-cent piece, followed by a 2²-cent piece, followed by a 23-
cent piece, and so on. Keep in mind that this is the future, so there are an infinite number of
different types of coins (one for each power of two). This is because, in the future, money self-
assembles.
Since you're new to this future world, you're skeptical as to whether it's even possible to be able
to
form all possible amounts of change using this weird new (infinite) set of coin denominations.
So, you decide that you need to prove it to yourself and you decide that you're going to do so
using mathernatical induction.
To facilitate the proof, you define the propositional function P(n) = "n cents can be changed
using coins whose values are powers of two". Your mission is to prove that P(n)is true for all
valid amounts of change.
(a) Show how to change 137 cents using only denominations that are powers of two.
(b) What is the base case?
(c) Verify that the base case is true.
(d) What is the inductive hypothesis?
(c) What do you need to prove in the inductive step?
(f) Complete the inductive step, identifying very clearly where you use the inductive hypothesis.
Hint: the amount being changed can either be an even number, or an odd number.
(g) What form of mathematical induction did you need to use to verify the induction step?
(h) Is it true that every valid amount of change can be formed using a unique set of coin
denominations? Justify your answer.

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.