Prove the following statements using mathematical induction.
Proofs for the first five theorems (pdf format).
Proofs for the first five theorems (html format, harder to read).
Prove that for any set .
For which positive integers are the following propositional functions true?
is true. For all positive integers , .
is true. For all positive integers , .
and are true. For all positive integers , .
and are true. For all positive integers , and imply .
is true. For all positive integers , .
What is wrong with the following proof?
Theorem: It is possible to form postage of three cents or more using just three cent and four cent stamps.
Proof:
Basis step: We can form postage of three cents with a single three cent stamp and postage of four cents using a single four cent stamp.
Inductive step: Assume that we can form postage of cents for all nonnegative integers with using just three cent and four cent stamps. We can then form postage of cents by replacing one three cent stamp with a four cent stamp or by replacing two four cent stamps by three three cent stamps.
Prove the following using strong induction:
Any amount of change over seven cents can be made out of three cent and four cent coins.
Any positive integer can be written as a sum of distinct powers of two. For example, and .