Proof By Mathematical Induction

Proof By Mathematical Induction

Author: c o

This lesson introduces the incredibly powerful technique of proof by mathematical induction.

The discussion is first motivated by a short example after which follows an explanation of mathematical induction. The remainder of the packet reinforces the learners understanding through several short examples in which induction is applied.

See More
Introduction to Psychology

Analyze this:
Our Intro to Psych Course is only $329.

Sophia college courses cost up to 80% less than traditional courses*. Start a free trial now.


Counting To Ellipsis

The Concept

Just because the sun has risen each and every day for as long as anybody can remember does not entail that it will definitely rise tomorrow.  There is always the least chance that something will be amiss, and that some unforeseen event will disrupt the otherwise predictable cycle of the earth rotating on its axis.  In short, the world is an unpredictable place.  In the world of mathematics, however, certainty is more readily available.  In fact, there are a number of techniques that may be employed to prove the certainty of different sorts mathematical of facts, and induction is one of these.  

Induction provides away to prove the mathematical equivalent of propositions like "the sun will rise tomorrow, forever and ever".  Such an equivalent is present in the proposition "the sum of the integers 1 through n is equal to n(n+1)/2".  In this lesson, we will use induction to prove that fact.  But first,  what is induction?

The Steps  

At the heart of mathematical induction rests a simple intuition:  

  1. If you know that where you are now is the right place to be
  2. And if you also know that whenever you happen to be in the right place, you can find out the right place to go next
  3. Then you will always be able to find the right place to go

A more precise definition of the principle of induction can be stated in terms of propositions about the natural numbers. A proposition  P(i) about the natural numbers is a statement that for is either true or false each natural number i.  For instance, P(i) could be "i is an even number".  In that case P(4) would be true, but P(7) would be false.  In these terms, induction is usually defined in the following manner.

The Principle Of Induction

If P(1) is true, and if whenever P(i) is true, we can infer the truth of P(i+1), then P(i) is true for all natural numbers i.

This makes sense because, if P(1) is true, then we know we can infer the truth of P(1+1) = P(2), which in turn means we can infer the truth of P(2+1) = P(3), and so on into infinity.  Hence, we arrive at the most important fact about induction: if we can count, we probably use induction!

Induction In Action

How to start?

In order to make use of induction, a fact about the natural numbers is required to be our proposition P(n).  Mentioned above was the statement "the sum of numbers 1 through n is equal to n(n+1)/2", this will serve as our our example.

Now what?

Next, we must make sure that we're starting on solid ground by answering the question "is P(1) true?" This is often called checking the base case.

So P(1) is true!  It checks out because the sum of all numbers from 1 to 1 (which is, of course, just 1) is equal to 1(1+1)/2 = 1.

The Inductive Step

Now we suppose that P(m) is true for some arbitrary m. We want to see if we can deduce the truth of P(m+1) using only the fact that P(m) is true.  To accomplish this, we will see if we can get the sum of the numbers from 1 to m+1 to look like (m+1)((m+1) + 1)/2.

Because we assumed that the sum of numbers from 1 to m was equal to m(m+1)/2, we can just substitute that m(m+1)/2 in place of that sum.  Lets move on.

Hence, because P(1) is true, and because we have shown that whenever P(m) is true then P(m+1) must also be true, then we may conclude that P(n) is true for all natural numbers n!