Proof methods: Proof by mathematical induction

Proof methods: Proof by mathematical induction

Written by on 3 August 2011

Topics: Math

It has been a while since I last posted something about proof methods, but lets dig that up again and take a look at a fourth method. The first three were direct proof, proof by contradiction and contrapositive proofs. Proof by induction is a somewhat different nature.

I have been reading quite a few blog posts recently and they all seem to be witty and clever, so I really wanted to add a joke right here on induction. But I honestly couldn’t find one I think was funny enough. So if you could just laugh or smirk for a few seconds before reading on, my day is saved.

Back to the induction part. Induction usually has it’s strength on statements of the type “For all integers k greater than b, P(k) is true”.  For some statements we could prove it with some of the already covered methods, but for others it would mean that we had to prove an infinity of cases.

The analogy I see everywhere and which I find quite fitting is to compare induction to dominoes (and I don’t mean the pizza thing) which are lined up. As soon as you knock the first one over it knocks all the remaining once over one by one. Induction works in much the same way.

We need to prove two things and for explanatory purposes I will explain them in reverse order

  1. Induction step: We assume that P(k) is true and then we need to show that P(k+1) is true as well. That is the same as saying if we knock an arbitrary domino over, then the next one will fall as well.
  2. Base Case: We need to prove the base case (P(b) – or in other words we need to show that we can knock over the first domino. 

Once we shown these two cases then if b=1 we have shown P(1), which by the induction step implies that P(2) is true, which by the induction step implies P(3)….. all the way to infinity.

Induction Proof Example

Let us start out with proving something Gauss figured out very early in his childhood.

Proposition: For all the following is true

I know this could be proven as a direct proof, but it is rather easy to and therefore well suited for an example. The question is rather easy to understand, so I wont do a whole lot to explain the idea.

Base case: The base case in this situation is N = 1, so we need to show that the statement holds for that

The sum of n from 1 to 1 is…. 1, so the left hand side is rather easy. The right hand side is easy to calculate using the basic arithmetic taught in 1st-4th grade, so we can reduce the statement to

1=1

Which is true.
Induction step: We assume that the statement holds for N = k such that it holds for

and need to show that the statement is also true for

Let us do this part as a direct proof.

The first step just pulls k+1 out of the summation. the second part of the last statement is by assumption equal to so we have

which proofs the proposition that

Thereby we have proven that it holds for the base case of n=1 and that it holds for all n by induction.

QED.

Wrapping Up

I have kept this blog post a tad short with only one example. I have a few more topics regarding induction that I want to blog about but that will be in a later blog post.

I have found a few good sources for reading about proof by induction. As always The book of proofs is a good choice, and also this 21 page pdf file which in my opinion gives a great covering of the topic.

The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.

4 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    I think this is the coolest proof method that we have learned about so far.
    Two steps and you solve infinitely many cases. And that’s a whole lot of cases… :)

  2. Kristian says:

    It is very obvious that we have proved an infinity of cases in the induction case, but is true for many of the other statements as well. This just lends it self to another type of problems.

    The theorem we proved in the example can be proven by direct methods as well for all integers, so we would end up covering the same amount of cases.

    That being said, yes I like it as well, and I always hear by math professor stating that we have to prove it for k+1 in his German accent.

  3. SuprDewd says:

    1. http://translate.google.com/
    2. Choose German
    3. Write “k + 1″
    4. Click Listen
    5. Laugh!

  4. William says:

    Always nice to have a clear and concise refresher of weak induction. Great post.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.