Next: 4. Analytic Geometry
Up: 3. Propositions and Functions
Previous: 3.4 Summation Notation
  Index
The induction principle is a way of formalizing the intuitive idea
that if you begin at
and start counting ``
'', then
eventually you will reach any preassigned number (such as for example,
).
3.55
Assumption (The Induction Principle)
Let
![$k$](img247.gif)
be an integer, and let
![$P$](img550.gif)
be
a proposition form over
![$\mbox{{\bf Z}}_{\geq k}$](img802.gif)
. If
is true,
and
``for all
'' is true,
then
``for all
'' is true.
In order to prove ``for all
'' by using the induction
principle, you should
1. Prove that
is true.
2. Take a generic element
of
and
prove
.
Recall that the way to prove ``
'' is true, is to
assume that
is true and show that then
must be true.
3.56
Example.
We will use the induction principle to do exercise
2.10. For all
![$n \in \mbox{{\bf Z}}_{\geq 1}$](img811.gif)
, let
Then
![$P(1)$](img813.gif)
says
which is true, since both sides of this equation are equal to
![$1$](img481.gif)
.
Now let
![$n$](img9.gif)
be a generic element of
![$\mbox{{\bf Z}}_{\geq 1}$](img815.gif)
Then
It follows from the induction principle that
![$P(n)$](img809.gif)
is true for all
![$n \in \mbox{{\bf Z}}_{\geq 1}$](img811.gif)
, which is what we wanted to prove.
3.57
Example.
We will show that
for all
Proof: Define a proposition form
over
by
Now
, so
and thus
is true.
Let
be a generic element of
Since
, we
know that
Hence
Hence, for all
It follows from
the induction principle that for all
Next: 4. Analytic Geometry
Up: 3. Propositions and Functions
Previous: 3.4 Summation Notation
  Index
Ray Mayer
2007-09-07