Search

Text Color

Margin Size

Font Type

Enable Dyslexic Font

8: Proof by Induction

Last updated

Sep 23, 2021
Save as PDF
- 7.7: Summary
- 8.1: The Principle of Mathematical Induction

( \newcommand{\kernel}{\mathrm{null}\,}\)

Mathematicians aren’t satisfied because they know there are no solutions up to four million or four billion, they really want to know that there are no solutions up to infinity.

attributed to Andrew Wiles (1953–), British mathematician

You are familiar with many of the properties of natural numbers, such as:

the commutative laws: $x + y = y + x$ and $x y = y x$ ,
the associative laws: $(x + y) + z = x + (y + z)$ and $(x y) z = x (y z)$ , and
the distributive laws: $x (y + z) = x y + x z$ and $(y + z) x = y x + z x$ .

These properties are also true for integers, for rational numbers, and for real numbers.

In this chapter, we discuss a very useful property of $N$ that is not true of $Z$ or $Q$ or $R$ . It is often very useful for proving assertions about natural numbers, and requires an understanding of sets and predicates (which were introduced in Chapter 3), but not the full theory of First-Order Logic.

Support Center

How can we help?