Section 2.2 Induction
111
If both statement 1 and the implication of statement 2 are true, then by
statement 1 you can get to the first rung and therefore by statement 2 you can
get to the second; by statement 2 again, you can get to the third rung; by statement 2 again you can get to the fourth; and so on. You can climb as high as you
wish. Both assertions here are necessary. If only statement 1 is true, you have
no guarantee of getting beyond the first rung, and if only statement 2 is true,
you may never be able to get started. Let’s assume that the rungs of the ladder
are numbered by positive integers—1, 2, 3, and so on.
Now think of a specific property a number might have. Instead of “reaching an arbitrarily high rung,” we can talk about an arbitrary, positive integer
having that property. We use the shorthand notation P(n) to mean that the positive integer n has the property P. How can we use the ladder-climbing technique to prove that for all positive integers n, we have P(n)? The two assertions
we need to prove are
1. P(1)
(1 has property P.)
2. For any positive integer k, P(k) S P(k + 1).
(If any number has
property P, so does the
next number.)
If we can prove both assertions 1 and 2, then P(n) holds for any positive integer n, just as you could climb to an arbitrary rung on the ladder.
The foundation for arguments of this type is the first principle of mathematical induction.
ReMinDeR
To prove something true
for all n ≥ some value,
think induction.
The first principle of mathematical induction is an implication. The conclusion is a statement of the form, “P(n) is true for all positive integers n.”
Therefore, whenever we want to prove that something is true for every positive
integer n, it is a good bet that mathematical induction is an appropriate proof
technique to use.
To know that the conclusion of this implication is true, we show that the two
hypotheses, statements 1 and 2, are true. To prove statement 1, we need only show
that property P holds for the number 1, usually a trivial task. Statement 2 is also
an implication that must hold for all k. To prove this implication, we assume for
an arbitrary positive integer k that P(k) is true and show, based on this assumption, that P(k + 1) is true. Therefore P(k) S P(k + 1) and, using universal generalization, (4k)[P(k) S P(k + 1)]. You should convince yourself that assuming that
property P holds for the number k is not the same as assuming what we ultimately
want to prove (a frequent source of confusion when one first encounters proofs of
this kind). It is merely the way to proceed with a direct proof that the implication
P(k) S P(k + 1) is true.
In doing a proof by induction, establishing the truth of statement 1, P(1), is
called the basis, or basis step, for the inductive proof. Establishing the truth of
P(k) S P(k + 1) is called the inductive step. When we assume P(k) to be true
f S P(n) true for all positive integers n
PRinciPLe FIrST PrINCIPlE oF MaThEMaTICal INDuCTIoN
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]
111
If both statement 1 and the implication of statement 2 are true, then by
statement 1 you can get to the first rung and therefore by statement 2 you can
get to the second; by statement 2 again, you can get to the third rung; by statement 2 again you can get to the fourth; and so on. You can climb as high as you
wish. Both assertions here are necessary. If only statement 1 is true, you have
no guarantee of getting beyond the first rung, and if only statement 2 is true,
you may never be able to get started. Let’s assume that the rungs of the ladder
are numbered by positive integers—1, 2, 3, and so on.
Now think of a specific property a number might have. Instead of “reaching an arbitrarily high rung,” we can talk about an arbitrary, positive integer
having that property. We use the shorthand notation P(n) to mean that the positive integer n has the property P. How can we use the ladder-climbing technique to prove that for all positive integers n, we have P(n)? The two assertions
we need to prove are
1. P(1)
(1 has property P.)
2. For any positive integer k, P(k) S P(k + 1).
(If any number has
property P, so does the
next number.)
If we can prove both assertions 1 and 2, then P(n) holds for any positive integer n, just as you could climb to an arbitrary rung on the ladder.
The foundation for arguments of this type is the first principle of mathematical induction.
ReMinDeR
To prove something true
for all n ≥ some value,
think induction.
The first principle of mathematical induction is an implication. The conclusion is a statement of the form, “P(n) is true for all positive integers n.”
Therefore, whenever we want to prove that something is true for every positive
integer n, it is a good bet that mathematical induction is an appropriate proof
technique to use.
To know that the conclusion of this implication is true, we show that the two
hypotheses, statements 1 and 2, are true. To prove statement 1, we need only show
that property P holds for the number 1, usually a trivial task. Statement 2 is also
an implication that must hold for all k. To prove this implication, we assume for
an arbitrary positive integer k that P(k) is true and show, based on this assumption, that P(k + 1) is true. Therefore P(k) S P(k + 1) and, using universal generalization, (4k)[P(k) S P(k + 1)]. You should convince yourself that assuming that
property P holds for the number k is not the same as assuming what we ultimately
want to prove (a frequent source of confusion when one first encounters proofs of
this kind). It is merely the way to proceed with a direct proof that the implication
P(k) S P(k + 1) is true.
In doing a proof by induction, establishing the truth of statement 1, P(1), is
called the basis, or basis step, for the inductive proof. Establishing the truth of
P(k) S P(k + 1) is called the inductive step. When we assume P(k) to be true
f S P(n) true for all positive integers n
PRinciPLe FIrST PrINCIPlE oF MaThEMaTICal INDuCTIoN
1. P(1) is true
2. (4k)[P(k) true S P(k + 1) true]