The principle of mathematical induction

(notes by Roberto Bigoni)


Many mathematical theorems state that a property is true for every element of a definite set. If A is the set and a is an element of A and we use the logical symbolism, we can write:

Eqn101.gif

The translation of this statement may be:"It is always true that, if a is a A, then a has the property P.

Most of these theorems can be demonstrated using the deductive method: starting from the hypothesis, recalling postulates and/or previously demonstrated theorems and applying general logical laws, one can reach the thesis.

Example: "(It is always true that) if τ is a triangle, then the sum of its internal angles equals the straight angle".

img002 Let ABC be a triangle and let α, β and γ be their internal angles.
Let DE be the straight line parallel to AB through C (which exists and is unique: postulate).
The angle DCA = α'=α because it is the internal alternate angle with respect to the angle ABC (theorem).
The angle ECB = β'=β because it is the internal alternate angle with respect to the angle CBA (theorem).
α'+γ+β' = DCE which is a straight angle.
Sums of equal quantities are equal (general logical principle)
so also α+β+γ is straight angle.

 

Mathematicians can also use proofs by contradiction: the falsity of the thesis would imply contradictory consequences, so the thesis must be true.

For example: "The prime numbers are infinite".

As is known, prime numbers are natural numbers greater than 1 and divisible only by themselves and 1.

If we suppose that the number of primes is finite, we must admit the existence of their maximum m and of the number p given by the product of all the primes from 2 to m: Eqn200.gif

We must also admit the existence of the natural number s immediately following p: Eqn201.gif

This number s can't be prime, because it is greater than m, but if we divide it by any prime number from 2 to m, we get the remainder 1, so it is not divisible by any prime number less than or equal to m; then it should be divisible by some prime numbers greater than m, but our assumption is that these numbers do not exist.

Therefore, if we admit that the number of primes is finite, we get a contradictory conclusion; so we must admit that the number of primes is infinite.

 

In order to give the mathematics an axiomatic foundation, some mathematicians in the late 19th century, mainly J. W. R. Dedekind and G. Peano, found it necessary to admit a further way to demonstrate the trueness of the logical statements P(n) about the natural numbers n. This is the principle of mathematical induction.

 

Let f  be a map Eqn102.gif, where N is the set of the natural numbers and A a predefined set. A sequence in A is the set of the elements of A which correspond in f  to the natural numbers.

The elements of a sequence may be written using the same symbol a together with the correspondig integer number. This number, the index, is smaller on the right: a1, a2, a3,....ai,...
ai is the i-th element of the sequence.
The whole sequence may be denoted in the following way: Eqn103.gif.

For example, the sequence of the odd numbers (di)i ∈ N = {1,3,5,7,....} may be denoted by di=2i-1 where d1=1, d2=3, d3=5,...

A sequence of logical propositions Eqn104.gif is a sequence of statements with the same predicate referred to the elements of a sequence of natural numbers.

For example:

Intuitively we know that all the pi are true, and that not all the qi are true. But intuition is insufficient in mathematics. We need a formal procedure to validate a whole infinite set of statements. The mathematical induction principle is admitted as a formal procedure of validation.

 

MATHEMATICAL INDUCTION PRINCIPLE

Given a sequence of logical propositions Eqn104.gif,
if we find that:

  • p1 is true;
  • if pi is true, then pi+1 is true;

we can say that all the pi are true.

 


EXAMPLES


  1. Eqn008.gif

    that is: the sum of a natural number n ≥ 1 and its square n2 is an even number.

    The statement may be easily demonstrated by deduction:

    In both cases, the result is even.

    Applying the mathematical induction principle, we may proceed in the following way:

     


  2. Eqn013.gif

    that is: the sum of the cube of a natural number n ≥ 1 and the quintuple of the same number is a multiple of 6.

    We can also in this case demonstrate the statement by deduction:

    Applying the mathematical induction principle, we may proceed in the following way:

     


  3. Eqn001.gif

    that is: the sum of the first n odd natural numbers equals the square of n.

    The statement is evidently true if n is 1.

    If we admit that it is true for the sum of the first n odd numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 odd numbers, that is Eqn002.gif?

    Demonstration:

    Eqn003.gif

     


  4. Eqn105.gif

    that is: the sum of the squares of the first n natural numbers equals the sixth part of the product between n, its successive number and the successive number of its double.

    This is immediate if n=1.

    If we admit the trueness of the statement for the fist n numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 numbers, that is Eqn106.gif?

    Demonstration:

    Eqn107.gif

     


  5. Eqn108.gif

    that is: the sum of the cubes of the fist n natural numbers equals the fourth part of the square of the product between n and its successive number.

    This is immediate if n=1.

    If we admit the trueness of the statement for the fist n numbers, can we demonstrate that it is true also if we extend the sum to the first n+1 numbers, that is Eqn109.gif?

    Demonstration:

    Eqn110.gif

    This equality has the interesting variant

    Eqn023.gif

    that is

    Eqn024.gif

    In fact, in the equality

    Eqn025.gif

    the right side can be written as

    Eqn026.gif

    and it's easy to demonstrate that the base of the square equals the sum of the first n natural numbers.

     


  6. Eqn004.gif

    If n=1, the equality becomes Eqn005.gif.

    If a number n verifies the equality, we must have Eqn006.gif

    Demonstration:

    Eqn007.gif


  7. Mengoli's series.

    Eqn111.gif

    The equality is immediate if n=1.

    If we admit the equality for n we obtain

    Eqn112.gif

    so also n+1 verifies the identity, therefore it is generally true.

     


  8. Geometric series.

    Eqn113.gif

    The equality is immediate if n=1.

    If we admit the equality for n we obtain

    Eqn115.gif

    so it holds also for n+1 and therefore it is generally true.

     


  9. Eqn116.gif

    that is: the derivative of the n-th power of the base x with respect to the base itself is given by the product between the exponent n and the n-1-th power of the base.

    If n=1 the equality results true.

    From the validity for n one can deduce the validity for n+1, that is

    Eqn117.gif

    Demonstration:

    Eqn118.gif

    The product rule of derivation of a product gives:

    Eqn119.gif

     


  10. Eqn027.gif

    This identity can be proved directly by applying the binomial theorem: infact Eqn028.gif

    It may be interesting, however, to prove this identity by induction.

    We can immediately see that it is true if n=1.

    For n+1 we have

    Eqn029.gif

    Binomial coefficients are such that

    Eqn030.gif

    so we can write

    Eqn031.gif

    that is

    Eqn032.gif

     


  11. Eqn033.gif

    where the double exclamation mark after a natural number indicates the double factorial of the number itself, that is, if the number is even, the product of all even numbers that precede it and, if the number is odd, the product of all odd numbers that precede it. Additionally -1!! = 0!! = 1

    If n=0, both sides of the identity have value 1.

    We must demonstrate that

    Eqn034.gif

    If, in order to simplify the exposition, we assume

    Eqn035.gif

    we must demonstrate that, for every n>0,

    Eqn036.gif

    For this purpose, we observe that

    Eqn037.gif

    and also, assuming Eqn038.gif,

    Eqn039.gif

    In this integral the antiderivative of the integrand function can be evaluated by parts

    Eqn040.gif

    Therefore the first fundamental theorem of calculus gives

    Eqn041.gif

    The integral in the right side is f(n-1), so, ultimately,

    Eqn042.gif

     


  12. Eqn043.gif

    When n=0, the left side is Eqn044.gif

    The right side is Eqn045.gif

    So the identity (12) is true for n=0. Assuming (12) true for a given n we need to prove that

    Eqn046.gif

    The antiderivative of the integrand at the left side can be evaluated by parts

    Eqn047.gif

    The definite integral is therefore

    Eqn048.gif

    Since the first addend in the right side is 0 and the integral in the second addend coincides with the left side in (12) we have

    Eqn049.gif

 


Beware of rash conjectures


If, given a circumference, we consider 2 points on it, and we draw the chord between them, the circle is divided into 2 regions.

cerchio2.gif

If we consider 3 points and trace all the possible chords between them, the circle is divided into 4 regions.

cerchio3.gif

If we consider 4 points and trace all the possible chords between them, the circle is divided into 8 regions.

cerchio4.gif

If we consider 5 points and trace all the possible chords between them, assuming that no more than two lines intersect at any point inside the circle, the circle is divided into 16 regions.

cerchio5.gif

Now we might think that, if we add another point, always assuming that no more than two lines intersect at any point inside the circle, the circle will be divided into 32 regions. But it is not true: the regions will be 31.

cerchio6.gif

As is suggested by D. Acheson in the booklet "1089 and all that" (Oxford University Press, 2002), the number of these regions is

Eqn202.gif

The correct sequence can be obtained by observing that, given r1=1,

Eqn203.gif

Every time we add a new point on the circumference, we get an increase in the number of regions given by the sum of the previous number of triangles with vertices on the circumference, expressed by the binomial coefficient, plus the number of previous points.

For example, when we add the point E,

  cerchio7.gif

we obtain:

In conclusion, when we add the fifth point we have an increase of 8 regions.

n rn rn-rn-1 Eqn204.gif
1 1    
2 2 1 1
3 4 2 2
4 8 4 4
5 16 8 8
6 31 15 15
7 57 26 26
8 99 42 42
9 163 64 64
10 256 93 93

So the equality (1) can be demonstrated by induction. In fact it is true for n = 1 and, taking it true for a given n, we obtain

Eqn205.gif

So the equality (1) holds for every n.


last revision: June 2016