What is mathematical induction

[Greg Bernhardt]

Definition/Summary

Mathematical Induction is a method of proving a series of mathematical statement labelled by natural numbers.

This method usually involves two steps. First one proves the base case, then one shows that if the statement holds for some natural number, it holds for the next.

It follows from these two proofs that the statement is true for all natural numbers greater than or equal to the base case.

In symbols: if P(1) is true, and if "P(m-1) is true implies P(m) is true for any m > 1" is true, then P(n) is true for any n \ge 1.

This works because P(1) is true, and P(1) proves P(2), and P(2) proves P(3), and so on for all the natural numbers.

Equations



Extended explanation

Induction

For example, if we want to prove that:

<br /> \frac{n^5}{5} + \frac{n^3}{3} + \frac{7n}{15}<br />

is a natural number for all n \in N.

First, we formalize the statement:

<br /> P(n): \frac{n^5}{5} + \frac{n^3}{3} + \frac{7n}{15}~~\mbox{is a natural number}<br />

<br /> P(1): \frac{1}{5} + \frac{1}{3} + \frac{7}{15} = \frac{15}{15} = 1<br />

So, P(1) is true.

Next, we hold an assumption that P(m) is true, for any arbitrary 'm':

<br /> P(m): \frac{m^5}{5} + \frac{m^3}{3} + \frac{7m}{15}~~\mbox{is a natural number}<br />

Now, we need to show that P(m + 1) is true as well. While doing so, we will use the fact that P(m) holds true. Hence, the statement for each natural number will assert the validity of the statement for the next natural number.

<br /> P(m + 1): \frac{(m + 1)^5}{5} + \frac{(m + 1)^3}{3} + \frac{7(m + 1)}{15}<br />

This equals:

<br /> = \frac{1}{5}(m^5 + 5m^4 + 10m^3 + 5m + 1) + \frac{1}{3}(m^3 + 3m^2 + 3m + 1) + \frac{7}{15}m + \frac{7}{15}<br />

<br /> = \left(\frac{m^5}{5} + \frac{m^3}{3} + \frac{7}{15}m\right) + (m^4 + 2m^3 + 3m^2 + 2m) + \left(\frac{1}{5} + \frac{1}{3} + \frac{7}{15}\right)<br />

All the three terms separated by brackets are natural numbers in themselves. The last bracket adds up to 1, and hence is a natural number. For the second bracket, all powers of natural numbers and their products with other natural numbers are natural numbers. As for the first bracket, we know that it is a natural number from our assumption that P(m) is true. And hence, since the sum of natural numbers is a natural number, P(m + 1) holds true, as long as P(m) holds true.

Do note here that we did not directly prove P(m) to be true. The validity of P(m - 1) asserts that P(m) is true. As such, we proved that P(1) is true, which asserts P(2) to be true, which asserts P(3) to be true and so on.

The abovementioned example was cited from the following mentioned textbook: 'Mathematics, Class XI', by R.D. Sharma published by Dhanpat Rai Publication'

Strong Induction

Occasionally, one will need to use more than the fact that P(m-1) is true in order to prove P(m). Indeed, one may need the truth of all the P(i) from the base case, to m-1. This is called strong induction. It is easy to see this is equivalent to the basic principle of induction.


Least counter example

An equivalent method is that of assuming there is a counter example to the assertion. If there is, then since they are labelled by the natural numbers, there is a least such counter example. Now one demonstrates that this implies that there is a smaller counter example. This together with the proof of the base case is sufficient.

Lack of insight

A not unreasonable view held by some mathematicians is that induction, whilst being very powerful, does not necessarily help you understand why something is true. For example, one can prove that

9^n \equiv 4n(n-1) +1\ (64)

easily with induction. But one can more constructively show it is true by considering the fact that 9=8+1.



Toppling Domino Analogy

An analogy to help understand Mathematical Induction is the Toppling Domino Analogy. Imagine that a number of Dominoes are aligned one after the other such that if one Domino topples, it topples the next one with it.

Here, the condition that a Domino will topple asserts that the Domino next to it will topple as well. However, no assertion is made on the toppling of that particular Domino. As such, we just need to ensure that the first Domino is toppled, which asserts, in a nutshell that all other Dominoes in line will be toppled as well.

* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

 

[e-pie]

There is another type of induction, although much lesser used known as Forward Backward Induction as developed by Cauchy.

Generally you prove the P(2k) and then the P(k-1) or the reverse. It is used as a proof for generalized AM GM Inequality (not the weighted one).

 

[jbriggs444]

This works because P(1) is true, and P(1) proves P(2), and P(2) proves P(3), and so on for all the natural numbers.

Although this is a good motivation, it lacks rigour. More formally, one can accept induction as an axiom schema or as part of the definition of the natural numbers, as in https://en.wikipedia.org/wiki/Natural_number#Von_Neumann_ordinals

 

[FactChecker]

That is a good explanation. It might be a step to far, but you might consider mentioning transfinite induction. That might open a can of worms that you wouldn't want to include here, but it would be good for an aspiring mathematician to be aware of it.

 

[Citan Uzuki]

Why are we reviving four year old threads?

 

[fresh_42]

Why are we reviving four year old threads?

Good question, the more as

* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

Thread closed.