Mathematical induction – Explanation and Example

Mathematical induction is an elegant technique applied in math to prove statements, theorems, and formulas. Learning about mathematical induction makes you appreciate the theorems and formulas you’ve learned and the mathematicians and theorists behind them.

Mathematical induction is a sophisticated proving technique in math where we first prove that the theory applies to the first value or term then use this to prove the general statement.

In a world where we can quickly search for the formulas and theorems online, it helps to retain our skill to think beyond what’s already given and learn to analyze things on our own.

One of the first techniques you’ll learn is the use of mathematical induction. In fact, there are a lot of sum formulas for common series we’ve encountered where we can use mathematical induction to prove their formula.

In this article, we’ll learn the process of using mathematical induction and even work on some examples. This is why it’s important to make sure you are familiar with common algebraic techniques, including the following:

• Factoring trinomials and expanding polynomials.

• Use different properties such as factoring by grouping and perfect square trinomial.

• We may even have to refresh our knowledge of exponent rules.

Aside from learning an essential proving technique, we’ll also be able to check our algebraic skills, so let’s dive right into our main topic.

What is mathematical induction?              

Mathematical induction is a sophisticated technique in math that can aid us in proving general statements by showing the first value to be true. We can then prove that the statement is true for two consecutive values and proves that it is true for all values.

Let’s go ahead and try out this mental exercise to understand the process of mathematical induction better:

Imagine a series of dominoes about to fall, and we want to show that all the dominoes would fall.

• If the domino at the beginning of the domino series falls.
• If we can show that when any domino between the series falls, the entire series falls.
• We can conclude that the domino effect can occur.

Here’s another: let’s imagine an infinite ladder, and we want to prove that we can reach all rungs of the ladder.

• If mathematical induction holds true, our first goal is to see if we can reach the ladder’s first rung. When we do, we can show that we can reach a certain rung of the ladder.

At this point, you already have an idea of how we perform mathematical induction. In general, the process itself requires two main steps:

1. Show that the mathematical statement is true for the first value.

2. Assume that the statement will continue to hold true for a given value, so show that the value after will also return a true statement.

When we can prove these two conditions through mathematical induction, we can conclude that the statement is true for all values.

How to do mathematical induction?              

Now that we can see how beneficial it is for us to apply mathematical induction to prove statements let’s understand the principle behind this technique. Here are the important points when using mathematical induction to prove a statement:

Given that $n$ is a natural number and $P_n$ is a statement that depends on the input value, $n$.

i) If the statement is true for $P_1$, and

ii) if we assume that $P_k$ is also true, we must show that $P_{k + 1}$ is true for all the positive integers, $k$.

If we can meet these two conditions, then we can conclude that the statement, $P_n$, is true all values of $n$.

This means that we can prove statements through mathematical induction by showing that the first and $(n + 1)$th terms are true.

Why don’t we apply this to prove that the formula for the sum of the first $n$ even integers will always be equal to $n(n +1)$?

Example of a mathematical induction proof

To show our understanding of mathematical induction, let’s work on one example and highlight the important steps we need to check to prove the statement that the first $n$ even integers will share a sum of $n(n + 1)$.

This means that we want to show that $2 + 4 + 6 + 8 + …+ (2n – 2)+ 2n = n(n + 1)$ or in summation form, that’s $ \sum_{i=1}^{n} 2i = n(n + 1)$. To further understand how the series behaves, let’s check the table of values shown below.

Our goal is to show that the last row is true – we do so through mathematical induction and using the steps shown below.

Step 1: Show that the statement is true for the first term, $i = 1$.

\begin{aligned} \sum_{i=1}^{n= 1} 2i &= 2(1)\\&=2 \\ n(n+1) &= 1(1 + 1)\\&=1(2)\\&= 2\\\\ \sum_{i=1}^{n} 2i &= n(n + 1) \end{aligned}

Step 2: Assume that $\sum_{i=1}^{n} 2i = n(n + 1)$ is true for $n = k$. We must show that the statement is also true for $n = k + 1$.

Keep in mind that $\sum_{i=1}^{k + 1} 2i$ is the result when we find $\sum_{i=1}^{k} 2i$ plus the next term, $2(k + 1)$.

\begin{aligned} \sum_{i=1}^{k + 1} 2i &= (\sum_{i=1}^{k} 2i) + (k + 1)\end{aligned}

Use the fact that the statement applies for $n = k$, so $\sum_{i=1}^{k} 2i = k(k + 1)$

\begin{aligned} (\sum_{i=1}^{k} 2i) + (k + 1) &= k(k+1) + 2(k+ 1)\\&= (k + 1)(k + 2)\\&= (k + 1)[(k + 1) + 1]\end{aligned}

This shows that $\sum_{i=1}^{k + 1} 2i = (k + 1)[(k + 1) + 1]$ showing that the formula is true for $k + 1$.

From the discussion above:

i) We’ve shown that the formula is true when $i= 1$.

ii) Given that the formula applies to $i = n$, then we’ve shown that the formula also applies to $i = n + 1$.

This means that through mathematical induction, we can confirm that $ \sum_{i=1}^{n} 2i = n(n + 1)$. It’s in fact true that the sum of the first $n$th even number is equal to the product of $n$ and $n + 1$.

Do you want to try out more problems involving mathematical induction? Don’t worry; we’ve prepared more examples for you!

Example 1

Show that the sum of the first $n$ natural numbers can be determined using the formula, $\dfrac{n(n + 1)}{2}$.

Solution

Our goal is to show that $1 + 2 + 3 + … + n = \dfrac{n(n + 1)}{2}$ and we can use mathematical induction to prove this.

We can begin by checking if the formula is true for $k = 1$. (Note that $n = k$)

\begin{aligned} S_1 &= 1\\S_1&= \dfrac{k(k + 1)}{2}\\&= \dfrac{1(1 + 1)}{2}\\&= 1\end{aligned}

We’ve shown that the formula applies to $k = 1$. Now, let’s assume that the formula applies to $n = k$. Meaning, we can assume that $1 + 2 + 3 + …k = \dfrac{k(k + 1)}{2}$ is true.

\begin{aligned} S_k &= \dfrac{k(k + 1)}{2}\\S_{k + 1} &= S_k + (k + 1)\end{aligned}

This only means that we can find the sum of the first $k +1$ terms by adding the sum of the first $k$ terms to $(k + 1)$. Let’s work on the resulting expression and see if we can show that $S_{k + 1}$ is equal to $\dfrac{(k + 1)[(k + 1)+1]}{2}$.

\begin{aligned} S_{k + 1} &= \dfrac{k(k + 1)}{2} + (k + 1)\\&= \dfrac{k(k + 1)}{2} + \dfrac{2(k + 1)}{2}\\&= \dfrac{k(k + 1) + 2(k + 1)}{2}\\&= \dfrac{k^2 + k + 1 + 2k + 2}{2}\end{aligned}

The expression we currently have for $S_{k + 1}$ can be factored by grouping to attain our ideal form for $S_{k + 1}$.

\begin{aligned} S_{k + 1} &= \dfrac{k(k + 1) +2(k + 1)}{2}\\&= \dfrac{(k + 1)(k + 2)}{2}\\&= \dfrac{(k + 1)[(k + 1) + 1]}{2}\end{aligned}

Hence, we’ve shown that $S_{k + 1}$ is indeed equal to $\dfrac{(k+1)[(k+1)+1]}{2}$.Since we’ve shown that the formula applies for the initial value and for $k +1$, we can conclude that the formula, $1+ 2+ 3+ …+n = \dfrac{n(n + 1)}{2}$, is indeed true.

Example 2

Show that the sum of the first $n$ consecutive cubes can be determined by squaring the sum of the first $n$ terms.

Solution

What we want is to show that $1^3+ 2^3 + 3^3 + ….+n^3 = (1 + 2 + 3+…+n)^2$. Let’s begin by showing that the formula applies when $k = 1$.

\begin{aligned}S_{1} &= 1^3\\&=1\\S_{1} &= (1)^2\\&= 1\end{aligned}

Since we’ve shown that $S_1 = 1^3 = 1$, we can now proceed to the next step. Let’s assume that the formula applies when $n=k$, so the sum of the first $k$ cubes is equal to $(1 + 2 +3 +…+k)^2$. Use the formula, $1+2+3+…+n = \dfrac{n(n+1)}{2}$, to rewrite $S_k$

\begin{aligned}S_k &= (1 + 2 + 3 +…+ k)^2\\&= \left[\dfrac{k(k + 2)}{2}\right]^2 \end{aligned}

With these forms in mind, let’s show that the formula will also apply to $S_{k + 1}$. We know that $S_{k + 1} = S_k + (k + 1)^3$, so let’s see if we can show that this is in fact equal to $[1 + 2 + 3 +…+ k + (k +1)]^2$.

\begin{aligned} S_{k + 1} &= S_k + (k + 1)^3\\&= \left[\dfrac{k(k + 1)}{2} \right ]^2 + (k + 1)^3\\&= \dfrac{k^2(k+1)^2}{4} + (k+1)^3\\&= \dfrac{k^2(k+1)^2}{4} + \dfrac{4(k+1)^3}{4}\\&= \dfrac{k^2(k+1)^2 + 4(k+1)^3}{4}\end{aligned}

This form is still not what we want for $S_{k+1}$ – our goal is to show that $S_{k+1}$ as $[1 + 2 + 3 +…+ k + (k +1)]^2$ or $\left[\dfrac{(k +1)( k+2)}{2}\right]^2$. Let’s continue manipulating our expression and we can do this by factoring out $(k+1)^2$.

\begin{aligned} S_{k + 1} &= \dfrac{(k + 1)^2[k^2 +4(k + 1)]}{4}\\&=\dfrac{(k+1)^2(k^2 + 4k + 4)}{4}\\&= \dfrac{(k + 1)^2(k +2)^2}{4}\\&= \left[\dfrac{(k + 1)(k +2)}{2} \right ]^2\\&= [1 + 2 + 3+…(k+1)]^2\end{aligned}

We’ve shown that the formula applies for $k+1$, so through mathematical induction, we can conclude that the formula, $1^3+ 2^3 + 3^3 + ….+n^3 = (1 + 2 + 3+…+n)^2$, is true for all $n$.