Proof by Induction

By: Fabian Meraz

What is a Proof by Induction?

A good analogy for a proof by induction is the domino effect. The domino effect happens when you have dominoes standing so that when one falls, the next one falls, then the one behind that one falls, and so on.

You might be wondering, “How does this relate to an induction proof?” When we do a proof by induction, we basically create the domino effect.When we prove that the theorem holds for k+1, we start the domino effect. Where does k+1 come from? We will learn about this in the next section.

Okay, how do I do a Proof by Induction?

To write a proof by induction, just follow these simple steps:

Step one: State that you will be using a proof by induction.


Step two: Prove the base case is true. This is usually n=1.


Step three: Assume that the statement is true for some k. This is the inductive hypothesis.


Step four: State that you will prove that your statement is true for k+1. This usually involves using your assumption. When you use your assumption, state that you used your inductive hypothesis.


Step five: Once you have proved the statement is true for k+1, state your conclusion. It is customary to state, “By the principle of mathematical induction, the statement is true.”

There are so many types of proofs, how do I know when to use it?

We use a proof by induction,when we are trying to prove a statement is true for all natural numbers. What if the problem states, “For all even numbers?” The even numbers are a subset of the natural numbers; there are infinite even numbers. Thus, we use a proof by induction.

Test Question:

Prove 1+2+...+n=n(n+1)/2 by using a proof by induction.

Bonus

With all this talk about dominoes, here is a fun video you should watch.

128,000 Dominoes - Falling into past - a journey around the world (2 Guinness World Records)

Sources:

Discrete Math Arthur T. Benjamin

How to Think Like a Mathematician Arthur Kevin Houston

http://www.youtube.com/watch?v=9E7Ep3U06Nc

http://comet.lehman.cuny.edu/sormani/teaching/induction.html