Return home

Mathematical Induction

Mathematical Induction is a basic but powerful method for showing a property (e.g., formula, expression) is true for all nonnegative integers. In this tutorial, we will discuss how to use the mathematical induction to prove the following summation formula:

1 + 2 + 4 + 8 + 16 + ... + N = 2*N 1 for N > 0

Step1: Verify that the formula is true when N=1

When N=1 (i.e., when we have only the first element):

1 + 2 + 4 + 8 + 16 + ... + N = 2*N 1

1 = 2*N 1

1 = 2*1 1

1 = 1, that is true.

Step2: Assume that the formula is true when N=k

When N=k (i.e., when we have all the elements from the first one to the kth element):

1 + 2 + 4 + 8 + 16 + ... + N = 2*N 1

1 + 2 + 4 + 8 + 16 + ... + k = 2*k 1

and we simply assume that this is true and the life is beautiful.

Step3: Show that the case for N=k implies the case for N=k+1

This step is called the induction step. Now assuming the claim in Step2 holds for all N=k, we need to prove that it is true for N=k+1.

When N=k+1 (i.e., when we have all the elements from the first one to the (k+1)th element):

1 + 2 + 4 + 8 + 16 + ... + N = 2*N 1

1 + 2 + 4 + 8 + 16 + ... + k + 2*k = 2*(2*k) 1

At this step, we need to be careful because we may naively assume that when N=k+1, the formula is

1 + 2 + 4 + 8 + 16 + ... + k + k+1 = 2*(k+1) 1 (THIS IS WRONG)

As you see, k+1 does not exist. In general, please keep in mind that

        N=1 refers to the case where we have only the first element.

        N=k refers to the case where we have all the elements from the first one to the kth element.

        N=k+1 refers to the all the elements from the first one to the (k+1)th element.

So, when N=k+1:

1 + 2 + 4 + 8 + 16 + ... + N = 2*N 1

1 + 2 + 4 + 8 + 16 + ... + k + 2*k = 2*(2*k) 1

We can rewrite the green part on the left size of the equation using the assumption (1 + 2 + 4 + 8 + 16 + ... + k = 2*k 1) in Step2:

1 + 2 + 4 + 8 + 16 + ... + k + 2*k = 2*(2k) 1

2*k 1+ 2*k = 2*(2*k) 1

Let us evaluate the expression

2*k + 2*k 1= 2*(2*k) 1

2*k + 2*k 1= 2*(2*k) 1

4*k 1= 4*k 1, which is true!

We conclude that the formula is true for all positive integers N by the principal of mathematical induction.

This is the end of the tutorial. I hope you enjoyed it. Please feel free to contact me at haberdar AT gmail dot com. You can use anything here as long as you give credit as follows:
Hakan Haberdar, "Mathematical Induction", Computer Science Tutorials [online], (Accessed MM-DD-YYYY) Available from: http://www.haberdar.org/mathematical-induction-tutorial.htm