Proof by Mathematical Induction

Mathematical Induction is often used in situations where the problem can be stated as a list of examples.

Example: Prove that the sum of a number of odd numbers can be immediately found by taking the square of how many odd numbers there are.

Notice that this problem could be stated as a list of examples each of which could be individually proved.

Example #1 on the list (only one odd number to add): 1. The sum is 1. Proof: 1 = 1. Therefore Example#1 is true.

Example #2 on the list: 1 + 3. The sum is 2². Proof: 1 + 3 = 4 and 2² = 4. Therefore Example #2 is true.

Example #3 on the list: 1 + 3 + 5. The sum is 3². Proof: 1 + 3 + 5 = 9 and 3² = 9. Therefore Example #3 is true.

…..

and so on.

The list is infinite because the Natural Numbers are infinite and we are using Natural Numbers to indicate each Example on our list.

Of course, we will never get to prove all the examples and so we cannot conclude that the original statement is true. ie. We cannot say that we have proved (by this method) for all Examples that ‘the sum of a number of odd numbers can be immediately found by taking the square of how many numbers there are.’

[A well-known counter-example states that ‘x² + x + 41 is a prime number’. And so it is for Example #1; Example #2; Example #3; … Try a few more. But what about Example #41?? Try it and see.]

There is a way around this problem.

We can show that there is a connecting link between any true Example and the Example which follows it. [This link could not be shown in the case of the counter-example!]

Thus, consider a typical true example such as Example #(k) on the list:

Example #(k) on the list: 1 + 3 + 5 + … + (2k-1). The sum is k².

[Note that the formula ‘2k-1’ produces the k^th odd number]

We are not required to prove this Example, merely to go on the basis that it is taken to be true for the purposes of moving on to the next Example.

How to move from Example #k to Example #(k+1):

[We note that Example #(k+1) will look like this:

Example #(k+1) on the list: 1 + 3 + 5 + … + (2k+1). The sum is (k+1)².

We also notice that each line on the list of Examples has one extra figure added on to the previous line Example. We are dealing with an addition problem.]

So, we start with Example #(k) and add on one extra figure both to the list of additions and to the total sum. We notice that the correct figure to add on is the (k+1)^th odd number which is ‘2(k+1) –1’ or (2k +1).

The changed Example #(k) will then look like this:

1 + 3 + 5 + … + (2k-1) + (2k+1). The sum is k² + (2k+1). [Remember, we are only moving on from Example #k and using it as our foundation material to see if we can produce the next Example.]

Look at both parts of the line we have produced.

The first part: 1 + 3 + 5 + … + (2k +1). This part is exactly what is required for the first part of Example #(k+1).

The second part: k² + (2k+1).

i.e. k² + 2k + 1 which has factors (k+1)(k+1) or (k+1)². This part is also exactly what is required for the second part of Example #(k+1).

ie. By using Example #k we have produced Example #(k+1).

So, whenever we use a true Example on this list we can be sure that we are able to go on to produce the next true Example.

Now, we have already shown that the first Example on the list is true. This means that we know it can be used to show that the second Example on the list is true (without even looking at the second Example).

And then that since the second Example on the list is true that it could be used to show that the third Example on the list is true.

And then that since the third Example on the list is true it can be used …

And so on for all the Examples on the list as far as infinity. Each true Example can be used to generate the next true Example.

Therefore, we conclude that all the Examples on the list are true.

Therefore we have proved by Mathematical Induction that the statement ‘that the sum of a number of odd numbers can be immediately found by taking the square of how many odd numbers there are’ is correct.

Now for a summarised version of the procedure.

The example lines are referred to as Propositions or Statements and given the code P.

1 + 3 + 5 + … + (2n-1) = n² and this is true for any value of n in the Natural Numbers. Prove this statement.

We can say that P(n) is the statement: 1 + 3 + 5 + … + (2n-1) = n²

Step 1: Prove that P(1) is true.

P(1) is: 1 = 1². This is true since 1 = 1. Therefore P(1) is true.

Step 2: Make the assumption that P(k) is a true statement where k is any Natural number.

P(k) is: 1 + 3 + 5 + … + (2k-1) = k². Assume that this is true.

Add (2k +1) to both sides.

Then 1 + 3 + 5 +…+ (2k-1) + (2k+1) = k² + (2k+1).

ie. 1 + 3 + 5 + … +(2k+1) = k² + 2k + 1

ie. 1 + 3 + 5 + … + (2k+1) = (k+1)²

But this last line is statement P(k+1).

Therefore P(k+1) is true whenever P(k) is true.

Step 3: Therefore by the Principle of Mathematical Induction P(n) is true for all values of n in the Natural Numbers.

Some web-sites with Mathematical Induction

http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html Some examples

http://www2.edc.org/mathproblems/problems/htmlProblems/nsMathInduction/nsMathInduction.asp?returnTo=http://www2.edc.org/makingmath/mathtools/induction/induction.asp Some questions and solutions

http://mathcentral.uregina.ca/RR/database/RR.09.95/nom3.html Examples of strategies which may come in useful