# Mathematical Induction – Quick Introduction

Mathematical induction, in its most

basic form, is often used to prove statements that

depend on a natural number n. Here, we use the convention that the

natural numbers begin at 1. For example, 2^n greater than or equal to n squared for all

natural numbers n is such a statement. In order to prove

something like this using mathematical induction, what you

need to establish are the following: the first is, the

statement holds for the case when n is equal to 1.

This is called the basis or the base case. The second is, assuming that the statement holds for

n=k for some natural number k, the statement also holds for n=k + 1. This step is called the inductive step

and the assumption that we’re making here is called the inductive hypothesis or

induction hypothesis. To get an idea why this is sufficient to prove the statement

for all natural numbers n, suppose that the basis has been

established. Now, if the inductive step is also

established, then that means the statement must be true for n=2

because it is true for n=1 and the

inductive step tells us that the statement must also be true for n=1 +1 which is 2. But now, we can apply the inductive step again. We

know that the statement is true for n=2, so it’s also true for n=2 + 1, which is 3. You can keep applying this reasoning and you’ll see that the statement is true

for any arbitrarily large values for n. So this is like falling dominoes. So let’s use this technique to prove the following. So we’re going to prove that the sum of the first n natural numbers is given by n (n + 1) / 2. So let’s look at the base case. When n=1, the left-hand side is just 1, and the right-hand side is 1 times (1 + 1) divided by 2 and that’s also 1. So the left-hand side is

the same as the right-hand side. So the statement holds for n=1. Now let’s establish the inductive step. So we assume that the statement holds for

n=k for some natural number k. That is we assume that the sum of i when i ranges from 1 to k is given by k (k + 1) / 2 for some natural number k. Now we want to prove that the statement holds for n=k + 1. So the left-hand side is the sum of i as i ranges from 1 to k + 1. And that can be broken down into the sum of i as i ranges from 1 to k plus k + 1. But by the induction hypothesis we know that this is just k (k + 1) / 2. So we can replace that with k (k + 1) / 2 plus (k + 1). And if you work this out, this is the same as (k + 1) times (k + 2) divided by 2, which can be written as (k + 1) times (k + 1) + 1 divided by 2. And this is precisely the right-hands side of the statement when

n=k + 1. So we have established that the

statement holds when n=k + 1 assuming that statement holds when n=k. So we have established both the basis and the inductive step and by the principle

of mathematical induction, we conclude that the statement holds for

all natural numbers n. Now, as an exercise, try applying mathematical induction to prove this statement. You’ll see that you cannot do it because

it’s not true.