Suppose you want to sum up the first 10 natural numbers 1, 2, 3, ...

The most obvious way to do it would be to add the numbers consecutively like so:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
No big deal, but now you want to sum the first 1000 natural numbers i.e. 1, 2, 3, ..., 1000. While you’re carrying out this laborious task, your friend Hypatia passes by and tells you with a confused look “Why are you doing all that? You can just use this formula:”
$$ \frac{n(n+1)}{2} $$
Skeptical, you give it a try on the first 10 natural numbers, because you already know the answer to that. So, you substitute n for 10 and you get
$$ \frac{10(10+1)}{2} = \frac{110}{2} = 55 $$
Lo and Behold, it’s the right answer. Go ahead and try it for other values of n yourself, see if it works.

So it works for the couple of instances that you’ve tried, but how do we know it works for the first 1024 natural numbers i.e. 1, 2, 3, ..., 1024 or for n = 50000. It seems implausible to actually try it for all instances of n. And even if we tried it for n up to 50000, we only know it works thus far, how do we know whether it works for n = 50001, n = 50002, ...etc especially given the fact that the set of Natural Numbers ℕ is Countably Infinite.

If you don’t know what the last couple of phrases mean, think of it this way, if we start with the number 1 and add 1 to it and keep adding 1 to the sum, you will always get a new natural number. For example, 1 + 1 = 2,  2 + 1 = 3,  3 + 1 = 4 and so on.

Obviously our manual method of verifying the technique’s applicability on single instances of n is incapable of convincing us of the applicability of the rule for any n and we need a new method to do just that, that method is Mathematical Induction.

Definition

Mathematical Induction is a general way to prove that some statement about the natural number n is true for all n ≥ 1.¹

A proof by induction involves first proving that we want to prove holds for n = 1 and then proving that if it holds for any n then it holds for n + 1.

Analogy

As a helpful analogy, think of the process of climbing a ladder, we will prove that we can climb the first step, then we will prove that if we can climb any step then we can climb the step that’s after it. Now we know that we can climb the first step and we know that we can climb any step after it. Symbolically, think of the first step as saying that n = 1, think of any step as n and think of the step that follows any step as n + 1.

Informally:

1. Can climb first step n = 1.
2. If we can climb step n then we can climb step n + 1.
3. Let n be 1, we can already climb the first step, let n + 1 be 1 + 1 = 2, we can climb the second step.
4. Let n be 2, we know we can climb it from item 3, so we can climb the n + 1 step which is the third step.
5. Repeat ad infinitum, can climb any step.

Outline for a proof by induction

A proof by induction will involve the following steps:

1. Prove that the statement where n = 1 is true, this is called the Base Case ², we’ll refer to this statement as S₁.
2. Prove that when n ≥ 1, the statement S_n ⇒ S_n + 1 is true.^{3 4} This is called the Inductive Step ⁵.

After we’ve completed these two steps, we say that it follows by Mathematical Induction that every S_n is true.

Proof Sketch for our Summation Technique

We will first start by proving the Base Case, in our case this means proving that the technique holds for n = 1. Again, we will refer to this statement as S₁.

We will then proceed to the Inductive Step, proving that S_n ⇒ S_n + 1.

In our case, this means proving that
$$ \frac{n(n+1)}{2} \implies \frac{(n+1)((n+1)+1)}{2} $$

Proof

Base Case: When n = 1, our formula expands to
$$ \frac{1(1+1)}{2} $$
which evaluates to 1 and is true.

Inductive Step: Assume that our formula S_n is true, this means that
$$ 1+2+3+...+n = \frac{n(n+1)}{2} $$
is true. This is called the Induction Hypothesis. We now have to show that S_n + 1 is true, algebraically this means that
$$ (1+2+3+...+n)+(n+1) = \frac{(n+1)((n+1)+1)}{2} $$
Let’s start with the left hand side
(1 + 2 + 3 + ... + n)+(n + 1)
Since we’ve already assumed that S_n
$$ 1+2+3+...+n = \frac{n(n+1)}{2} $$
is true, we can substitute it in the left hand side like so:
$$ \begin{align} (1+2+3+...+n)+(n+1) & = \frac{n(n+1)}{2} + n+1\\ & = \frac{n(n+1)+2(n+1)}{2}\\ & = \frac{n^2+n+2n+2}{2}\\ & = \frac{n^2+3n+2}{2}\\ & = \frac{(n+1)(n+2)}{2}\\ & = \frac{(n+1)((n+1)+1)}{2} \end{align} $$
This shows us that S_n + 1 is indeed true if S_n is true. Since we’ve proven the Base Case and conducted the Inductive Step, our formula
$$ \frac{n(n+1)}{2} $$
is true for all numbers n ≥ 1 by Mathematical Induction.

\( \square \)

Examples

Proposition

If n ∈ ℕ⁶ then the sum of the first n odd numbers 1 + 3 + 5 + 7 + ... + (2n − 1) is n².

Proof

Therefore, it follows by induction that 1 + 3 + 5 + 7 + ... + (2n − 1)=n² as required.

\( \square \)

Proposition

If n ∈ ℕ, then 3|(n³ − n).

Proof

It follows by induction that 3|(n³ − n).

\( \square \)

Exercises

Exercise

If n is a non-negative integer, then 5|(n⁵ − n).

Exercise

If n ∈ ℤ and n ≥ 0, then
$$ \sum_{i=0}^{n} i.i! = (n+1)!-1 $$

Exercise

For every Natural Number n, 2⁰ + 2¹ + 2² + ... + 2ⁿ = 2^n + 1 − 1.

Footnotes