TABLE OF CONTENTS In this chapter we study proof by induction and prove some important inequalities, particularly the arithmetic-geometric mean inequality. In order to employ induction for defining new objects we prove the so called recursion theorems. Basic properties of powers with rational exponents are also established in this chapter.
The process of deriving general conclusions from particular facts is called induction. It is often used in the natural sciences. For example, an ornithologist watches birds of a certain species and then draws conclusions about the behaviour of all members of that species. General laws of motion were discovered from the motion of planets in the solar system. The following example shows that we encounter inductive reasoning also in mathematics.
Let us consider the numbers n 5 ? n for the first few natural numbers:
| n | n 5 ? n |
|---|---|
| 1 | 0 |
| 2 | 30 |
| 3 | 240 |
| 4 | 1020 |
| 5 | 3120 |
| 6 | 7770 |
| 7 | 16800 |
It seems likely that for every n ? 
the number n 5 ?n is a multiple of 10.
The reasoning in the above example does not give us the feeling of castiron certainty which mathematical arguments usually have. It may not be true for n=8, though you can easily check that it is. Even if you have used a computer to check the first billion natural numbers, that does not prove that it is true for all natural numbers. Indeed, basing arguments on a finite number of...
