An important technique for verifying proofs in combinatorics and number theory is the Principle of Mathematical Induction. The technique was used implicitly in Euclid's Elements in the “descent proof” that states that every natural number has a prime divisor. The term “Mathematical Induction” was first coined in 1828 by the English logician Augustus DeMorgan (1806–1871) in an article called Induction.
Mathematical Induction is generally not used in deriving new formulas, but is an effective tool to verify formulas and facts you suspect are true. That said, it is part of the repertoire of any mathematician.
The beauty of mathematical induction is it allows a theorem to be proven in cases when there are an infinite number of cases to explore without having to examine each case. Induction is the mathematical analogue of an infinite row of dominoes, where if you tip over the first domino, it tips over the next one, and so on, until they all are tipped over. The nice thing about induction is you do not have to prove that it works. It is an axiom1 in the foundations of mathematics.
Mathematical induction provides a convenient way to establish that a statement is true for all natural numbers 1, 2, 3, …. The following statements are prime candidates for proof by mathematical induction.
Here, then is how induction works.
1.6.2 Mathematical Induction
The Principle of Mathematical Induction is a method of proof for verifying that a proposition P(n) is true for all natural numbers n = 1, 2, …. The methodology for proving theorems by induction is as follows:
The result from Theorem 1 can also be found with pictures.
You may now ask, how did we ever arrive at the nonintuitive inequalities in the proof that made everything turn out so nice? The answer is we worked out the inequalities backwards starting with the conclusion.
Sometimes a result can be proven by induction or with a direct proof. The following problem is such an example. You can decide if you have a preference.
The type of induction discussed thus far is sometimes called weak induction. We now introduce another version of induction called strong induction. Although the two versions are logically equivalent, there are problems where strong induction is more convenient.
1.6.3 Strong Induction
Surprising as it might seem, both weak and strong induction are logically equivalent, the difference being practical, sometimes strong induction is more convenient and sometimes weak induction is more convenient. The methodology of strong induction consists in carrying out the following steps.
The following theorem shows how strong can be useful in proving certain results.
A fundamental result in number theory is the Fundamental Theorem of Arithmetic, which can be proven by strong induction.
The next example shows a variation of the base step in induction. Each problem is different, and the induction proof must be modified accordingly.
Problems
Proof by Induction
Prove the following propositions, either by weak or strong induction.
1 + 3 + 5 + ⋯ + (2n − 1) = n2.
9n − 1 is divisible by 8 for all natural numbers n.
For n ≥ 1, 1 + 22 + 23 + 24 + ⋯ + 2n = 2n + 1 − 1
For n ≥ 5, 4n < 2n,
n3 − n is divisible by 3 for n ≥ 1.
2n − 1 ≤ n!, n ∈ ℕ
For all positive integers n, n2 + n is even.
For any real numbers a, b and natural number n, we have (ab)n = anbn.
Something Fishy
Let us prove by induction n2 + 7n + 3 is even for all natural numbers n = 1, 2, …. What is wrong with the following induction argument? Letting P(n) denote
we prove P(n) ⇒ P(n + 1). Assuming P(n) true, we have
Hence, P(n + 1) is true which by induction proves that n2 + 7n + 3 is even for all natural numbers n. Note: Check the result for n = 2.
Clever Mary
To prove the identity
Mary evaluates the left‐hand side of the equation for n = 0, 1, 2 getting
n
0
1
2
p(n)
0
1
3
and then finds the quadratic polynomial p(n) = an2 + bn + c that passes through those points, getting
Mary turns in this proof to her professor. Is her proof5 valid?
Hmmmmmmmm
Is there something fishy with this argument that Mary can carry a 50‐ton load of straw on her back. Clearly, she can carry one straw on her back, and if she can carry n straws on her back, she can certainly carry one more. Hence, she can carry any number of straws on her back, which can amount to a 50‐ton load.
Geometric Principle by Induction
Show that every convex polygon6 can be divided into triangles. An example illustrating a triangulation of an eight‐sided convex polygon is drawn in Figure 1.13.
A few terms of the sequence are 1,1,2,3,5,8,13. Show the nth term of the sequence is given by
where .
Peano's Axioms
The Principle of Mathematical Induction is generally taken as an axiom for the natural numbers and is in fact the fifth axiom for Peano's axioms. Google Peano's axioms and read about them on the Internet.
Internet Research
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward mathematical induction, and Giuseppe Peano.
.