112
Proofs, Induction, and Number Theory
so as to prove the inductive step, P(k) is called the inductive assumption, or
inductive hypothesis.
All the proof methods we have talked about in this chapter are techniques
for deductive reasoning—ways to prove a conjecture that perhaps was formulated by inductive reasoning. Mathematical induction is also a deductive
technique, not a method for inductive reasoning (don’t get confused by the terminology here). For the other proof techniques, we can begin with a hypothesis
and string facts together until we more or less stumble on a conclusion. In fact,
even if our conjecture is slightly incorrect, we might see what the correct conclusion is in the course of doing the proof. In mathematical induction, however,
we must know right at the outset the exact form of the property P(n) that we
are trying to establish. Mathematical induction, therefore, is not an exploratory
proof technique—it can only confirm a correct conjecture.
Proofs by Mathematical Induction
Suppose that the ancestral progenitor Smith married and had two children. Let’s
call these two children generation 1. Now suppose each of those two children had
two children; then in generation 2, there were four offspring. This trend continued from generation unto generation. The Smith family tree therefore looks like
Figure 2.2. (This figure looks exactly like Figure 1.1b, where we looked at the
possible T–F values for n statement letters.)
Generation
1
2
Offspring
2 = 2 1
4 = 2 2
3
…
…
…
8 = 2 3
Figure 2.2
It appears that generation n contains 2
n
offspring. More formally, if we let P(n)
denote the number of offspring at generation n, then we guess that
P(n) = 2
n
We can use induction to prove that our guess for P(n) is correct.
The basis step is to establish P(1), which is the equation
P(1) = 2
1
= 2
This is true because we are told that Smith had two children. We now assume that
our guess is correct for an arbitrary generation k, k ≥ 1; that is, we assume
P(k) = 2
k
and try to show that
P(k + 1) = 2
k+1
Proofs, Induction, and Number Theory
so as to prove the inductive step, P(k) is called the inductive assumption, or
inductive hypothesis.
All the proof methods we have talked about in this chapter are techniques
for deductive reasoning—ways to prove a conjecture that perhaps was formulated by inductive reasoning. Mathematical induction is also a deductive
technique, not a method for inductive reasoning (don’t get confused by the terminology here). For the other proof techniques, we can begin with a hypothesis
and string facts together until we more or less stumble on a conclusion. In fact,
even if our conjecture is slightly incorrect, we might see what the correct conclusion is in the course of doing the proof. In mathematical induction, however,
we must know right at the outset the exact form of the property P(n) that we
are trying to establish. Mathematical induction, therefore, is not an exploratory
proof technique—it can only confirm a correct conjecture.
Proofs by Mathematical Induction
Suppose that the ancestral progenitor Smith married and had two children. Let’s
call these two children generation 1. Now suppose each of those two children had
two children; then in generation 2, there were four offspring. This trend continued from generation unto generation. The Smith family tree therefore looks like
Figure 2.2. (This figure looks exactly like Figure 1.1b, where we looked at the
possible T–F values for n statement letters.)
Generation
1
2
Offspring
2 = 2 1
4 = 2 2
3
…
…
…
8 = 2 3
Figure 2.2
It appears that generation n contains 2
n
offspring. More formally, if we let P(n)
denote the number of offspring at generation n, then we guess that
P(n) = 2
n
We can use induction to prove that our guess for P(n) is correct.
The basis step is to establish P(1), which is the equation
P(1) = 2
1
= 2
This is true because we are told that Smith had two children. We now assume that
our guess is correct for an arbitrary generation k, k ≥ 1; that is, we assume
P(k) = 2
k
and try to show that
P(k + 1) = 2
k+1