Next: 4. Analytic Geometry Up: 3. Propositions and Functions Previous: 3.4 Summation Notation   Index

# 3.5 Mathematical Induction

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 be an integer, and let be a proposition form over . 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 , let

Then says

which is true, since both sides of this equation are equal to . Now let be a generic element of Then

It follows from the induction principle that is true for all , 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