**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 k^{th} 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 k^{th}
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**