Use strong induction to show that if you can run one mile or two miles, and if you can always run two more miles once you have run a specified number of miles, then you can run any number of miles.
Let be the statement that you can run miles. We want to prove is true for all positive integers .
Basis Step: and are true.
Inductive Step: Fix and assume is true for all . We want to show is true. Since , is a positive integer less than or equal to . By the inductive hypothesis, we know that is true. That is, we know that you can run miles. Since "you can always run two more miles once you have run a specified number of miles", we know that you can run miles. This is .
Let be the statement that a postage of cents can be formed using just 3-cent stamps and 5-cent stamps. The parts of this exercise outline a strong induction proof that is true for .
a) Show that the 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 the inductive step?
d) Complete the inductive step for .
e) Explain why these steps show that this statement is
true whenever .
a), ,
b) Inductive hypothesis is the statement that is true, that is, a postage of cents can be formed from and cent stamps.
c) In the inductive step we need to prove assuming is true for .
d) We assume , that a postage of cents can be formed from and cent stamps. Since , we can know that is true, that we can form cents of postage. Put another cent stamp on the envelope, and we have formed cents of postage.
e) We have completed both the basis and inductive steps, so by the principal of strong induction, the statement is true for every integer .
a) Determine which amounts of postage can be formed using just 4-cent and 11-cent stamps.
b) Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step.
c) Prove your answer to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction?
a) Adding together by hand we can form 4, 8, 11, 12, 15, 16, 19, 20, 22, 23, 24, 26, 27, 28, 30, 31, 32, 33. For any postage , it can be formed from just and cent stamps.
b) The inductive hypothesis is is true. We want to prove it for . We want to show that, assuming , that . We consider two cases. For the first case, if the cents includes an cent stamp, replace it with cent stamps (). Otherwise, includes no cent stamps and has been formed from just cent stamps. Because , that means that at least eight cent stamps were used. Replace those eight cent stamps with three cent stamps, and we have formed cents in postage ().
c) is the same as in part b. This time for our strong induction basis step, we see is true for . Assuming that is true for all with , where , we want to show that is true. , we know that is true. Put one more cent stamp in the envelope, and we have cents of postage as desired.
Use strong induction to prove that is irrational. (Hint: Let be the statement that for any positive integer ).
("there is no positive integer such that . is true because for all positive integers . For the inductive step, we assume is true for all , where is an arbitrary positive integer; we must prove is true.
Assuming the contrary, that for some . Squaring both sides and clearing fractions we get . This tells us that is even, and so is as well (the square of an even number is always even). Therefore we can write for some positive integer . Substituting, we have , so . We see that is even, so for some positive integer . then we have . But ,so this contradicts the inductive hypothesis, and our proof of the inductive step is complete.
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 carried out, exactly moves are required to assemble a puzzle with pieces.
.
Base Case: is trivially true.
Inductive Hypothesis: is true for all .
Inductive Step: Consider a puzzle with pieces. The final move must be the joining of two blocks and for some integer , . By the inductive hypothesis, it required moves to construct the one block, and moves to construct the other. Therefore, moves are required in all, so is true. We have proved that under the assumption that was true for .
What is wrong with this “proof” by strong induction?
“Theorem” For every nonnegative integer , .
Basis Step: .
Inductive Step: Suppose that for all nonnegative
integers with . Write ,
where and are natural numbers less than . By the
inductive hypothesis, .
The error is going from the basis step to the next value . We can't write as the sum of two smaller natural numbers, so we can't invoke the inductive hypothesis. In the notation of the "proof", when , we cannot write where and .
Find the flaw with the following “proof” that for
all nonnegative integers , whenever is a nonzero real
number.
Basis Step: is true by the definition of .
Inductive Step: Assume that for all nonnegative
integers with . Then note that
The denominator contains (which is , for which we have proved nothing). Our inductive step requires .. but we want to start induction at .
Show that strong induction is a valid method of proof by
showing that it follows from the well-ordering property.
To show that strong induction is valid, supose that we have a proposition which has been proved using it. We must show that is true (to say that a principle of proof is valid means that it only proves only true propositions).
Let be the set of counterexamples, . We want to show that . We argue by contradiction. Assume that . Then by the WOP, has a smallest element. Since part of the method of strong induction is to show that is true, this smallest counterexample must be greater than . Lets call it . Since is the smallest element in , it must be the case that is true. But the rest of the proof using strong induction involed showing implied ; therefore since the hypothesis is true, the conclusion must be true as well ( is true). This contradicts our assumption that . Therefore we conclude that , so is true.
Show that the well-ordering property can be proved when the principle of mathematical induction is taken as an axiom.
We will prove this by contradiction. Suppose that the well-ordering property were false. Let b e a counterexample: a nonempty set of nonnegative integers that contains no smallest element. Let be the statement " for all ". We will show that is true for all (which will contradict the assertion that is nonempty). Now must be true, because if then clearly would have a smallest element, namely . Suppose now that is true, so that . If , then would be the smallest element of , and this would contradict our assumption. Therefore . Thus we have shown by the principle of mathematical induction that is true for all , which means there can be no elements of . This contradiction our assumption that , and our proof by contradiction is complete.
Use the well ordering principle to prove that there is no solution over the positive integers to the equation
is the statement that there is no solution to for , , .
is the set of counterexamples of :
Assume for proof by contradiction that is nonempty. That is, contains contains values that make true. By the WOP, there must be an that is the smallest value that makes the equation true. We see that the left hand side of the equation is even, so must be even. So for some integer . Substituting that in we get..
We see is even, so must also be even. There must be some positive integer where . Substituting again we get
We see that is even, so must be even. There must be an integer where . Substituting once more we get
We see that , , and . This appears to be another solution to the original equation, so , , and are elements of . This is a contradiction though, because and was defined as being the smallest value that makes the equation true (the smallest value in ).