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.