MATHEMATICAL INDUCTION

Objectives:

• Learn the principle of mathematical induction.
• Use the principle of mathematical induction to prove a formula.
• Find the sums of powers of integers.
• Find a formula for a finite sum.
• Use finite differences to find a quadratic model.
INDUCTION

In this topic you will study a form of mathematical proof called mathematical induction. It is important that you clearly see the logical need for it, so let's look at the following problem.

S1=1=1^2
S2=1+3=2^2
S3=1+3+5=3^2
S4=1+3+5+7=4^2

Judging from the pattern formed by these first five sums, it appears that the sum of the first n odd integers is

Sn=1+3+5+7+...+(2n-1)=n^2

Although this particular formula is valid, it is important for you to see that recognizing a pattern and then simply jumping to the conclusion that the pattern must be true for all values of n, is not a logically valid method of proof.
Just because a rule, pattern or formula seems to work for several values of n, you cannot simply decide that it is valid for all values of n without going through a legitimate proof.

 The Principle of Mathematical Induction Let Pn be a statement involving the positive integer n. If  1. P1 is true, and 2. The truth of Pk implies the truth of Pk+1 for every positive k, then Pn must be true for all positive integers n.

It is important to recognize that both parts of the Principle of Mathematical Induction are necessary. To apply the Principle, you need to be able to determine the statement Pk+1 for a given statement Pk.

Example 1   Find Pk+1 for
Pk: 52k-1 + 1 is divisible by 6.

Solution: We just have to replace k by k+1:

Pk+1: 52(k+1)-1 + 1 is divisible by 6.

Example 2 Use mathematical induction  to prove the following formula.

Sn=1+3+5+7+...+(2n-1)=n^2.

Solution: mathematical induction consists of two distinct parts. First we must show that the formula is true when n=1.

1. When n=1 P1 is true, because
P1: S1=1=1^2.

2. We assume Pk is true.
Pk: Sk=1+3+5+7+...+(2k-1)=k^2.

We must show that Pk+1 is true.

Pk+1: Sk+1=(k+1)^2.

We have:
Sk+1=1+3+5+7+....+(2k-1)+[2(k+1)-1]
=[1+3+5+7+....+(2k-1)]+(2k+2-1)
=Sk+2k+1  Since we assumed that Pk is true, it means that Sk=k^2
=k^2+2k +1
=(k+1)^2.  which proves that Pk+1 is true.

Combining the results of parts (1) and (2) we can conclude by mathematical induction that the formula is valid for all positive integer values of n.

Example 3  Use mathematical induction  to prove the following formula.

Solution:

1. When n=1, P1 is true, because
1(2)(3)
P1: S1=1^2= ----------------.
6

2. Assuming that Pk is true
k(k+1)(2k+1)
Pk: Sk=1^2+2^2+...+k^2=----------------.
6

we must show that Pk+1 is true, that is
(k+1)(k+2)(2k+3)
Pk+1: Sk+1=   ----------------
6

To do this we write the following:

Sk+1=Sk+(k+1)^2
=1^2+2^2+...+k^2+(k+1)^2
k(k+1)(2k+1)
=  ----------------   +(k+1)^2    after bringing to the same denominator and factoring
6

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

Combining the results of parts (1) and (2) we can conclude by mathematical induction that the formula is valid for all positive integer values of n.

SUMS OF POWERS OF INTEGERS

The formula in example 3 is one of a collection of useful summation formulas. We summarize this and other formulas dealing with sums of various powers of the first n positive integers as follows.

 Sums of Powers of Integers

Each of these formulas for sums can be proven by mathematical induction.

Example 4  Find

Solution Using the formula for the sum of the cubes of the first n positive integers, we obtain the following

=[7(7+1)/2]^2=49*64/4=784.

Example 5  Prove that n < 2^n for all positive integers n.

Solution:
1. For n=1, P1 is true, because
P1: 1<2^1 is true.

2. Assumnig that Pk: k<2^k is true, we have to show that
Pk+1: k+1<2^(k+1) is true.

We have

2^(k+1)=2(2^k)>2(k)=2k.
Because 2k=k+k+k+1 for all k > 1, it follows that

2^(k+1)>2k>k+1
or
k+1<2^(k+1).

So,  n < 2^n for all positive integers n.

PATTERN RECOGNITION

Although choosing a formula on the basis of a few observations does not guarantee the validity of the formula, pattern recognition is important. Once you have a pattern that you think works, you can try using mathematical induction to prove that it is valid.

 Finding a Formula for the nth Term of a Sequence To find a formula for the nth term of a sequence, consider the following guidelines.  Calculate the first several terms of the sequence. It is often a good idea to write the terms in both simplified and factored forms. Try to find a recognizable pattern for the terms and write a formula for the nth term of the sequence. This is your hypothesis or conjecture. You might try computing one or two more terms in the sequence to test your hypothesis. Use mathematical induction to prove your hypothesis.

Example 6  Find a formula for the following finite sum:
1            1           1          1               1
------- + ------- + ------- + -------+ .... + -------
1*2        2*3      3*4       4*5             n(n+1)

Solution: Begin by writing out the first few sums

1                1
S1=------- = 1/2=-------
1*2             1+1
1          1         4          2          2
S2=------- + ------- =------- =------- =-------
1*2       2*3       6          3        2+1

From this sequence it appears that the formula for the kth sum is:

1          1         1           1                  1         k
Sk=------- + ------- + ------- +-------+ .... +-------=-------
1*2       2*3     3*4         4*5          k(k+1)   k+1

To prove the validity of this hypothesis, use mathematical induction, as follows. Note that we have already verified the formula for n=1, so we can begin by assuming that the formula is valid for n=k (that is Pk is true) and trying to show it is valid for n=k+1.

1            1           1          1              1              1
Sk+1=------- + ------- + ------- + -------+ .... + ------- + ----------------
1*2       2*3        3*4        4*5             k(k+1)       (k+1)(k+2)
k             1
= ------- + ----------------
k+1      (k+1)(k+2)
k^2+2k+1
= ----------------
(k+1)(k+2)
k+1
= -------
k+2

So the hypothesis is valid.

FINITE DIFFERENCES

First differences of a sequence are found by subtracting consecutive terms. If the first differences are all the same, then the pattern is linear.

Second differences are found by subtracting consecutive first differences. If the second differences are all the same, then the pattern is quadratic.

Remember that you can find a quadratic model by taking the equation y=ax2+bx+c with three points. Then solve the system of equations that results. The analogy here is that you can find an=an2+bn+c by substituting in three terms in the sequence for an and their corresponding position in the sequence for n. Then solve the system of linear equations.

This can be extended to third differences by subtracting consecutive second differences. If the third differences are all the same, the pattern is cubic. You can fit a cubic model with four points and the model an=an3+bn2+cn+d.

Example 7  The first and second differences of the sequence 3, 5, 8, 12, 17, 23, . . . are as follows:

n: 1    2    3    4       5     6

an: 3    5    8    12    17    23

first differences:    2    3    4      5     6
second differences:     1    1    1      1

For this sequence the second differences are all the same, which means that the sequence has a perfect quadratic model.

an=an2+bn+c

By substituting 1, 2 and 3 for n, we can obtain a system of three linear equations in three variables:

a1=a+ b+c=3
a2=4a+2+c=5
a3=9a+3b+c=8

The solution are a=1/2, b=1/2 and c=2. Thus the quadratic model of the sequence is

an=(1/2)n2+n/2+2.

EXERCISES

1. Use mathematical induction  to prove that 8n- 3n is divisible by 5, for all n>=1,

2. Use mathematical induction  to prove that, for n >= 5, 4n < 2n.

3. Use mathematical induction  to prove that, for n >= 1,

1*2 + 2*3 + 3*4 + ... + (n)(n+1) = (n)(n+1)(n+2)/3

4. Find the formula for the sum of the first n terms of the sequence:

1, 5, 9, 13, . . .

5. Find the formula for the sum of the first n terms of the sequence:

25, 22, 19, 16, . . .

6. Find the formula for the sum of the first n terms of the sequence:

1, 9/10, 81/100, 729/1000, . . .

7. Find the formula for the sum of the first n terms of the sequence:

1/4, 1/12, 1/24, 1/40, . . . 1/[2n(n+1)], . . . .

8. Find a quadratic model for the sequence with the terms:

a0=3, a1=3, a4=15

9. Find a quadratic model for the sequence with the terms:

a0=-3, a2=1, a4=9

10. Use mathematical induction to prove the inequality

n! > 2n, for n>=4

11. Use mathematical induction to prove the inequality

for n>=2.