The Principle of Mathematical Induction




The Principle

It is common that the validity of a statement must be proved for all natural numbers starting from a certain number. This starting number is usually 0 or 1. Assume, for now, that the starting number is 1.

Example: 'The sum of the natural numbers from 1 to n equals n(n+1)/2'.

This is a property which depends on n. We write this fact as E(n). E(3) means in our example :
' The sum of the natural numbers from 1 to 3 equals 3(3+1)/2'.

A proof by induction is a common method to prove such a property. We show how the method works and why it is correct.

Let V = { n | E(n) is true }. First we prove E(1). Then we know that 1 is in V.

Then we prove that: If E(k) is true, then E(k+1) is true.

If that is proved, we know that: if k is in V then (k+1) is in V.

But 1 is in V, so 2 is in V, so 3 is in V, etc...

Then V = { 1,2,3,4,....}

We have shown that the property E(n) is true for all natural numbers starting with 1.

We apply it to our example

In our example is E(n) is 1+2+3+4+5+...+ n = (1+n)n/2 Conclusion: The property is proved for all natural numbers starting from 1.

Practical approach

Once the principle is clear the procedure is usually significantly shortened.

We resume the same example, but give the short version.

We have to prove: 1+2+3+4+5+...+ n = (1+n)n/2

Proof:

If n=1 then the property is true because 1 = (1+1).1/2
Now assume that the property is true for n= k
We'll show the validity of the property for n= k+1.
We have to prove: 1+2+3+4+5+...+k+(k+1) = (1+(k+1)).(k+1)/2

Left side = (1+2+3+4+5+...+k)+ (k+1) = (1+k).k/2 + (k+1) = (k+1)(k+2)/2 = right side

So, the property is true for all natural numbers starting from 1.

Example 2

Here we write '>=' for 'greater than or equal to'

Show that for all integers greater than zero : 2n >= n+1.

The property is obvious for n = 1.

Now assume that the property is valid for n=k
So, we know that 2k >= k+1.
It is very important that we use this, in the remainder of our proof

We have to prove that property is valid for n = k+1
We have to prove: 2k+1 >= k+2

Well, 2k+1 = 2k.2 >= (k+1).2 = 2k+2 >= k+2

So the property is valid for all n.

Example 3

Prove by induction that Sn = 1 + 3 + 5 + 7 + ... + 2n-1 = n2

The property is obvious for n = 1.

Now assume that the property is valid for n=k
So, we know that Sk = 1 + 3 + 5 + 7 + ... + 2k-1 = k2
It is very important that we use this, in the remainder of our proof

We have to prove that property is valid for n = k+1
We have to prove: Sk+1 = 1 + 3 + 5 + 7 + ... + 2k-1 + 2k+1 = (k+1)2
Well, Sk+1 = Sk + (2k+1) = k2 + 2k +1 = (k+1)2.

So, the property is true for all natural numbers starting from 1.

Example 4

Prove by induction that 12 + 22 + 32 + ... + n2 = (1/6). n.(n+1).(2n+1)

The property is obvious for n = 1.

Now assume that the property is valid for n = k
So, we know that 12 + 22 + 32 + ... + k2 = (1/6). k.(k+1).(2k+1)
It is very important that we use this, in the remainder of our proof

We have to prove that property is valid for n = k+1
We have to prove: 12 + 22 + 32 + ... + k2 + (k+1)2 = (1/6).(k+1).(k+2)(2k+3)

 
Left side

 = 12 + 22 + 32 + ... + k2 + (k+1)2

 = (12 + 22 + 32 + ... + k2) + (k+1)(k+1)

 = (1/6). k.(k+1).(2k+1) + (k+1)(k+1)

 = (1/6).(k+1). [ k(2k+1) + 6(k+1)]

 = (1/6).(k+1).(2 k2 + 7k + 6)

Right side

 = (1/6).(k+1).(k+2)(2k+3)

 = (1/6).(k+1).(2k2 + 3k + 4k + 6)

Example 5

Show that 32n+1 + 2n-1 is a multiple of 7

The property is obvious for n = 1.

Now assume that the property is valid for n = k
So, 32k+1 + 2k-1 is a multiple of 7
It is very important that we use this, in the remainder of our proof

We have to prove that property is valid for n = k+1
We have to prove: 32k+3 + 2k is a multiple of 7

We transform 32k+3 + 2k such that 32k+1 + 2k-1 shows up.

 
   32k+3 + 2k

 = 32.32k+1 + 2.2k-1

 = 9. 32k+1 + 2. 2k-1

 = 7. 32k+1 + 2. 32k+1 + 2. 2k-1

 = (multiple of 7) + 2 (32k+1 + 2k-1)

 = (multiple of 7)+ 2 . (multiple of 7)

 = (multiple of 7)

Example 6

Show that for any even number n

12 - 22 + 32 - 42 + ... - n2 = (-1/2) n (n+1)


The property is obvious for n = 2.

Now assume that the property is valid for n = k (with k an even number)
So, 12 - 22 + 32 - 42 + ... - k2 = (-1/2) k (k+1)

We have to prove that property is valid for n = k+2
We have to prove:
12 - 22 + 32 - 42 + ... - k2 + (k+1)2 - (k+2)2 = (-1/2)(k+2)(k+3)

Proof:

 
   12 - 22 + 32 - 42 +  ... - k2 + (k+1)2 - (k+2)2

= (12 - 22 + 32 - 42 +  ... - k2) + (k+1)2 - (k+2)2

=             (-1/2) k (k+1)           + ((k+1)2 - (k+2)2 )

    We try to factor this expression

= (-1/2) k (k+1) + ((k+1) -(k+2)).((k+1) + (k+2))

= (-1/2) k (k+1) + (-1) (2k + 3)

= (-1/2) ( k(k+1) + 4k + 6)

= (-1/2) ( k2 + 5k + 6 )

= (-1/2) (k + 2)(k + 3)

Reasoning error?

We will show that, in each box with n balls, all balls have equal size!

The property is obvious for n = 1.

Now assume that the property is valid for n = k
So, in each box with k balls, all balls have equal size. (*)

Now take a box with k+1 balls.
On an arbitrary ball we write the letter A and on another randomly chosen ball we write the letter B. To show that all balls have equal size it is sufficient to prove that the randomly selected balls A and B are equal in size.

Now we pick a ball, different from A and B, from the box. Now, the box contains k balls.

Relying on (*) we know that the k balls are equal in size. So, the balls A and B are equal in size.

Conclusion: In each box with n balls, all the balls are equal in size.

---------------------------

Explain exactly why this reasoning is wrong. .


Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

The tutorial address is http://home.scarlet.be/math/

Copying Conditions

Send all suggestions, remarks and reports on errors to Johan.Claeys@ping.be     The subject of the mail must contain the flemish word 'wiskunde' because other mails are filtered to Trash