Mathind.html

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.

S₁=1=1^2
S₂=1+3=2^2
S₃=1+3+5=3^2
S₄=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

S_n=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 P_n be a statement involving the positive integer n. If

1. P₁ is true, and

2. The truth of P_k implies the truth of P_k+1 for every positive k,

then P_n 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 P_k+1 for a given statement P_k.

Example 1 Find P_k+1 for
P_k: 5^2k-1 + 1 is divisible by 6.

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

P_k+1: 5^2(k+1)-1 + 1 is divisible by 6.

Example 2 Use mathematical induction to prove the following formula.

S_n=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 P₁ is true, because
P₁: S1=1=1^2.

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

We must show that P_k+1 is true.

P_k+1: S_k+1=(k+1)^2.

We have:
S_k+1=1+3+5+7+....+(2k-1)+[2(k+1)-1]
       =[1+3+5+7+....+(2k-1)]+(2k+2-1)
       =S_k+2k+1 Since we assumed that P_k is true, it means that S_k=k^2
       =k^2+2k +1
       =(k+1)^2. which proves that P_k+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, P₁ is true, because
1(2)(3)
P₁: S₁=1^2= ----------------.
6

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

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

To do this we write the following:

S_k+1=S_k+(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, P₁ is true, because
P₁: 1<2^1 is true.

2. Assumnig that P_k: k<2^k is true, we have to show that
P_k+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
S₁=------- = 1/2=-------
       1*2             1+1
        1          1         4          2          2
S₂=------- + ------- =------- =------- =-------
      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
S_k=------- + ------- + ------- +-------+ .... +-------=-------
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 P_k is true) and trying to show it is valid for n=k+1.

             1            1           1          1              1              1
S_k+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

Finite differences can help you find the pattern.

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=ax²+bx+c with three points. Then solve the system of equations that results. The analogy here is that you can find an=an²+bn+c by substituting in three terms in the sequence for a_n 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 a_n=an³+bn²+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

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

a_n=an²+bn+c

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

a₁=a+ b+c=3
a₂=4a+2+c=5
a₃=9a+3b+c=8

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

a_n=(1/2)n²+n/2+2.

EXERCISES

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

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

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:

a₀=3, a₁=3, a₄=15

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

a₀=-3, a₂=1, a₄=9

10. Use mathematical induction to prove the inequality

n! > 2ⁿ, for n>=4

11. Use mathematical induction to prove the inequality

for n>=2.

Back to Topics