Mathematical Induction I

Mathematical Induction is a tricky topic and can appear impossible to understand at first. To begin, it’s important to realize that induction comes directly from Peano’s 5th Axiom (or 9th depending on your website of choice).

Remember that an axiom is a rule or statement that is universally accepted without proof. So although the principle of induction is without proof, it can be understood logically from a few examples. The example that I understood best involved a ladder.

Consider a ladder, the first step to climbing this hypothetical ladder is to first climb the lowest rung (base case), and then if you can climb the next rung (n + 1 inductive hypothesis) then you could climb the the entire ladder. This intuitively makes sense because if you can climb the base rung, and the next rung, every other case amounts to just climbing another rung which has already been shown to be possible by the inductive step.

Most induction problems are usually defined for natural numbers (positive-integers). This is good because it allows us to take advantage of the well-ordering principle. This principle basically gives us a “base” to work with because it states that every non-empty set of positive integers has a smallest value. So the goal of induction is to prove a base case, and then prove a more general case (n+1), in effect producing a proof for all natural numbers.

The best way to learn anything is through practice and mathematical induction is no different. Now that I’ve discussed the basics of induction I’ll begin with a classic induction proof and my next post’s will focus on different types of proofs that can be done inductively.

Use mathematical induction to prove that

1 + 2 + 3 + 4 + 5 + … + n = \frac{n(n+1)}{2} for all integers n \geq 1

This is usually one of the first proofs that teachers introduce because its easy to understand and  it just rely’s on algebra. So as always we start with a basis step

Show that P(1) is true

1 = \frac{(1)((1) + 1)}{2} (by basic algebra)

Next we must consider an inductive hypothesis and ultimately prove the formula

Suppose that k is any arbitrarily chosen but particular integer with k \geq 1. Suppose that:

1 + 2 + 3 + 4 +5 + … + k = \frac{k(k+1)}{2}

This step is called a hypothesis because its what we are trying to prove, but it noteworthy to remember that this hypothesis is taken as truth and can be used throughout the proof as such.

So the real heart of the problem comes down to proving the following statement:

1 + 2 + 3 + 4 + 5 + … + k + (k+1) =  \frac{(k+1)((k+1)+1)}{2}

This can be accomplished with basic algebra and our inductive hypothesis. Take note of the following substitution.

(1 + 2 + 3 + 4 + 5 + … + k) + (k+1) =  \frac{(k+1)((k+1)+1)}{2}

\frac{k(k+1)}{2} + (k+1) =  \frac{(k+1)((k+1)+1)}{2}

We are allowed to make this substitution because we are supposing it to be true, that’s why its called an inductive hypothesis. The proof is complete once we have shown that the left side of the equation implies the right side of the equation (which is accomplished with basic algebra).

Left-Side

\frac{k(k+1)}{2} +\frac{2(k+1)}{2} =

\frac {k(k+1) + 2(k+1)}{2} =

\frac {k^2 + k + 2k + 2}{2} =

\frac{k^2 + 3k + 2}{2} =

Right-Side

\frac{(k+1)((k+1)+1)}{2}

= \frac{(k+1)(k+2)}{2}

= \frac{k^2 + 2k + k + 2}{2}

= \frac{k^2 + 3k + 2}{2}

Left-Side = Right Side ?

\frac{k^2 + 3k + 2}{2}\frac{k^2 + 3k + 2}{2} (true)

\therefore  1 + 2 + 3 + 4 + 5 + … + n = \frac{n(n+1)}{2} for all integers n \geq 1

In the next post I’ll focus on using induction with inequalities as well as discuss more examples.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s