Vectors and Vector Operations - University of Michigan



1.9 Mathematical Induction

Mathematical induction is a way of establishing the correctness of formulas involving an integer variable. It also applies to inequalities, algorithms and other assertions involving an integer variable. Even more broadly it applies to algorithms and assertions involving string variables. Let's see how it works first in the case of a formula.

You have a formula that involves an integer variable n and you want to prove it is true for all positive integers n. To do this you do the following two things.

(1) First you show it is true for n = 1

(2) Then you show that the truth of the formula for a particular value of n implies the truth of the formula for n + 1

These two things imply that the formula is true for all positive integers n. The idea is that starting with the truth for n = 1, you can apply (2) repeatedly to reach any positive integer n. Let's see how this is done to prove the following summation formula.

Example 1. Using mathematical induction, show that if n is a positive integer then

(3) 12 + 22 + 32 + … + n2 =

In other words the sum of the squares of the first n positive integers is .

Solution. The first part of the proof of (3) using mathematical induction is to show that it is true for n = 1. If n = 1 then

Left side of (3) |n = 1 = (12 + 22 + 32 + … + n2) |n = 1 = 12

Right side of (3) |n = 1 = |n = 1 = =    = 1

So the result is true for n = 1.

The second part of the proof of (3) using mathamatical induction is to show that if it is true for a certain value of n, then it is true for n + 1. So, we are assuming (3), but for a particular n, not all n. And we want to show (3) is true of n + 1. So we want to show the following.

12 + 22 + 32 + … + n2 + (n + 1)2 =

i.e.

(4) 12 + 22 + 32 + … + n2 + (n + 1)2 =

Note that the left side of what we are assuming is all but the last term of the left side of what we want to show. So if we add (n + 1)2 to both sides of what we are assuming we get

12 + 22 + 32 + … + n2 + (n + 1)2 = + (n + 1)2

So in order to show (4) we need to show

+ (n + 1)2 =

If we multiply both sides by 6 and divide by (n + 1), then we need to show

n(2n + 1) + 6(n + 1) = (n + 2)(2n + 3)

If we expand both sides, then we need to show

2n2 + n + 6n + 6 = 2n2 + 7n + 6

The two sides are equal, so this completes the proof.

The formula (3) is a summation equality. Mathematical induction can also be used to prove inequalities. Often we can't find a closed form for a sum, but we would like to know what the sum is ( of. An inequality can help answer this question. The following is an example of a pair of inequalities that can be proved using mathematical induction.

Example 2. Using mathematical induction, show that if n is a positive integer then

(5) 2 - 2 < + + + … + < 2

There is no formula for the sum in the middle in terms of simple functions. However, the pair of inequalites says that the sum is ( of .

We first show (5) is true for n = 1. If n = 1 then

Left side of (5)|n = 1 = [2- 2]|n = 1 = 2 - 2 = 2( – 1) ( 2(1.414 – 1) = 0.828

Middle of (5) |n = 1 = ( + + + … + ) |n = 1 = = 1

Right side of (5) |n = 1 = 2 |n = 1 = 2 =   2

Since 0.828 < 1 < 2 the result is true for n = 1.

Now we show that if it is true for a certain value of n, then it is true for n + 1. So, we are assuming (5), but for a particular n, not all n. And we want to show (5) is true for n + 1. So we want to show the following.

2 - 2 < + + + … + + < 2

i.e.

(6) 2 - 2 < + + + … + + < 2

Note that the middle of what we are assuming is all but the last term of the middle of what we want to show. So if we add to all three parts of what we are assuming we get

2 - 2 + < + + + … + + < 2 +

So in order to show (6) we need to show

(7) 2 - 2 < 2 - 2 +

and

(8) 2 + < 2

To show (7) we add 2 to both sides and multiply by . Then we need to show

2 < 2 (n + 1) + 1

or

2 < 2n + 3

If we square both sides, then we need to show

4n2 + 12n + 8 < 4n2 + 12n + 9

This is true, so (7) is true. To show (8) we multiply both sides by . Then we need to show.

2 + 1 < 2 (n + 1)

or

2 < 2n + 1

If we square both sides, then we need to show

4n2 + 4n < 4n2 + 4n + 1

This is true, so (8) is true and this completes the proof.

Sometimes the formula is not true for all positive integers, but only for positive integers greater than or equal to a certain value n0. In that case the first part of mathematical induction (1) has to be modified to the following.

(9) First you show it is true for n = n0

Mathematical induction can also be used to show equations and inequalities involving products.

Example 3. Show that if n > 4 then

(10) n2 < 2n

On the right is a table of n2 and 2n for n = 1, 2, …, 7.

Solution. First we show it is true for n = 5.

Left side of (10) |n = 5 = 52 = 25

Right side of (10) |n = 5 = 25 = 32

Since 25 < 32 the result is true for n = 5.

Now we show that if it is true for a certain value of n, then it is true for n + 1. So, we are assuming (10), but for a particular n, not all n. And we want to show (10) is true for n + 1. So we want to show the following.

(11) (n + 1)2 < 2n+1

Note that 2n+1 = 2 ( 2n. So, if we multiply (10) by 2 we get.

2n2 < 2n+1

So, in order to show (11) we need to show that if n > 4 then

(n + 1)2 < 2n2

Taking square roots gives

n + 1 < n

or

1 < ( - 1)n

(12) < n

However, = + 1 = 1.414.. + 1 = 2.414.. So (12) is true if n > 4.

Example 4. When we were working with the exclusive or operation ( we were led to conjecture that

(13) x1 ( x2 ( … ( xn =

Show that this is true using mathematical induction

Solution. If is clearly true if n is 1 or 2. Suppose (13) is true for a certain n. We need to show

x1 ( x2 ( … ( xn ( xn+1 =

Using the fact that ( is associative we see that this is equivalent to

(14) [ x1 ( x2 ( … ( xn ] ( xn+1 =

We break this into four cases.

Case 1. An even number of x1, …, xn are 1 and xn+1 = 0. Then an even number of x1, …, xn+1 are 1. Since (13) is true for this particular n one has x1 ( x2 ( … ( xn = 0. Thus [ x1 ( x2 ( … ( xn ] ( xn+1 = 0 ( 0 = 0. Therefore (14) is true since an even number of x1, …, xn+1 are 1 and [ x1 ( x2 ( … ( xn ] ( xn+1 = 0.

Case 2. An even number of x1, …, xn are 1 and xn+1 = 1. Then an odd number of x1, …, xn+1 are 1. Since (13) is true for this particular n one has x1 ( x2 ( … ( xn = 0. Thus [ x1 ( x2 ( … ( xn ] ( xn+1 = 0 ( 1 = 1. Therefore (14) is true since an odd number of x1, …, xn+1 are 1 and [ x1 ( x2 ( … ( xn ] ( xn+1 = 1.

Case 3. An odd number of x1, …, xn are 1 and xn+1 = 0. Then an odd number of x1, …, xn+1 are 1. Since (13) is true for this particular n one has x1 ( x2 ( … ( xn = 1. Thus [ x1 ( x2 ( … ( xn ] ( xn+1 = 1 ( 0 = 1. Therefore (14) is true since an odd number of x1, …, xn+1 are 1 and [ x1 ( x2 ( … ( xn ] ( xn+1 = 1.

Case 4. An odd number of x1, …, xn are 1 and xn+1 = 1. Then an even number of x1, …, xn+1 are 1. Since (13) is true for this particular n one has x1 ( x2 ( … ( xn = 1. Thus [ x1 ( x2 ( … ( xn ] ( xn+1 = 1 ( 1 = 0. Therefore (14) is true since an even number of x1, …, xn+1 are 1 and [ x1 ( x2 ( … ( xn ] ( xn+1 = 0.

So in all four cases (14) is true. So (13) holds for n + 1 and this completes the proof of (13) by induction.

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

|n |n2 |2n |

|1 |1 |2 |

|2 |4 |4 |

|3 |9 |8 |

|4 |16 |16 |

|5 |25 |32 |

|6 |36 |64 |

|7 |49 |128 |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download