9.4 Mathematical Induction

Mathematical Induction:
Induction can be used to prove statements involving a positive integer n.

A proof must be used to verify that a rule, pattern, or formula is valid for all values of n.

This is called the Principle of Mathematical Induction:

Let  be a statement involving the positive integer n.

In order to show a statement is true for all values of n, you must follow these steps:

 

1. Show that the statement is true for n=1.

2. Assume that the statement is true for some integer n.

3. Use the above assumption to prove that the statement is valid for the next integer n+1.

 

 

Example: Prove the following formula using mathematical induction:

 





Using the steps of mathematical induction, we must:

1. Show it's true for n=1.

 

 

 

2. Assume that the statement is true for some integer n.

 

 

 

3. Prove the statement is valid for n+1.

This means proving that this formula is true: 

 

 



The next step is to replace the first part of the equation with

The result is:

This equation can be factored to equal this, which was our goal for this step:

 We have now proved that the formula:

 

is true when n=1, assumed that it is true for all values of n, and proven that it is true for the next integer n+1.

 

 

 

Sums of Powers of Integers

These formulas can be used to find the sums of various powers of the first n positive integers.

 

 

 

 

 

 

 

 

 
 
 

Finite Differences

There are two types of finite differences:

First differences are the differences between consecutive terms of a sequence.

Second differences are the differences between the first differences.

 

Example: 1, 4, 9, 16, 25

First: 3, 5, 7, 9

Second: 2, 2, 2

 

If the second differences are the same and nonzero, the sequence is a quadratic model. If the first differences are the same and nonzero, it is a linear model. If none of the differences are the same, it is neither model.