The Principle of Mathematical Induction

• The Principle
  
• We apply it to our example
  
• Practical approach
  
• Example 2
  
• Example 3
  
• Example 4
  
• Example 5
  
• Example 6
  
• Reasoning error?
  

The Principle

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

• First step:

  We'll show the truth of E(1). We have to show: 1 = (1+1).1/2

  We see immediately that both sides are equal. So, E(1) is true.

  V contains '1'.

• Second step:

  Assume for a moment that E (k) is true.
  Given : 1+2+3+4+5+...+k = (1+k)k/2

  We'll show the truth of E(k+1).

  Proof:

  •  
        left side
    
      = (1+2+3+4+5+...+k)+ (k+1)
    
      = (1+k).k/2 + (k+1)
    
      = (k+1)(k+2)/2
    

  •  
        right side
    
      = (1+(k+1)).(k+1)/2
    
      = (2+k)(k+1)/2
    

  We see that the left side is equal to the right side.

  Thus if E (k) is true then E(k+1) is true.

  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..

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

Practical approach

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

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 2^k >= 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: 2^k+1 >= k+2

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

So the property is valid for all n.

Example 3

The property is obvious for n = 1.

Now assume that the property is valid for n=k
So, we know that S_k = 1 + 3 + 5 + 7 + ... + 2k-1 = k²
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: S_k+1 = 1 + 3 + 5 + 7 + ... + 2k-1 + 2k+1 = (k+1)²
Well, S_k+1 = S_k + (2k+1) = k² + 2k +1 = (k+1)².

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

Example 4

The property is obvious for n = 1.

Now assume that the property is valid for n = k
So, we know that 1² + 2² + 3² + ... + k² = (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: 1² + 2² + 3² + ... + k² + (k+1)² = (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

The property is obvious for n = 1.

Now assume that the property is valid for n = k
So, 3^2k+1 + 2^k-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: 3^2k+3 + 2^k is a multiple of 7

We transform 3^2k+3 + 2^k such that 3^2k+1 + 2^k-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

The property is obvious for n = 2.

Now assume that the property is valid for n = k (with k an even number)
So, 1² - 2² + 3² - 4² + ... - k² = (-1/2) k (k+1)

We have to prove that property is valid for n = k+2
We have to prove:
1² - 2² + 3² - 4² + ... - k² + (k+1)² - (k+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?

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. .