Induction

Mathematical induction, simply called "induction", is a method of mathematical proof. In general, proof by induction is used for verifying statements for all nonnegative integers ($0$, $1$, $3$, …).

Let's take a non-mathematical example to understand how you can use this method. Suppose that there is an infinite number of dominoes lined up perfectly. Suppose that the first domino is knocked over, and that each domino that falls knocks over the next one. Induction then proves that all dominoes will fall.

Principle of induction

Proof by Induction is based on the principle of mathematical induction. Suppose that $P$ is a property that holds for integers, and that $a$ is an integer. If the following two statements are true:

1. $P(a )$ is true.
2. For every integer $k \geq a$, if $P(k)$ is true, then $P(k+1)$ is also true,

then the statement $P(n)$ is true for every integer $n \geq a$.

Let's go back to our dominoes example. If we rake that the first domino is knocked over (in other words, $P(1)$ is true — in this case $a=1$). It is also given that if a domino $k$ falls, then a domino $k+1$ also falls. Referring to our description of the principle of induction, this means that all dominoes after the first one also fall.

$P(n)$ (the $n\text{-th}$ domino falls) is true for every integer $n \geq 1$ after the first domino is pushed.

Proof by induction

How can you use induction to prove something? Suppose you have a statement that is in the form "For every integer $n \geq a$, a property $P(n)$ is true". Note that $a$ is a fixed integer. The following three steps are used to prove such a statement.

Step 1: Base case — verify that the property is true for the first integer $n=a$. That is, show that $P(a )$ is true.

Step 2: Induction hypothesis — for some integer $k \geq a$, assume that the property is true. That is, assume that $P(k)$ is true.

Step 3: Induction step — use the hypothesis to prove that the property also holds when $n=k+1$. That is, show that $P(k+1)$ is true.

Now, let's take a look at some examples.

Example: arithmetic progression

Let's prove that the sum of the first $n$ integers where $n \geq 1$ is ${n (n+1) \over 2}$.

So, your property $P(n)$ is:

$$1+2+...+n = {n (n+1) \over 2}$$Step 1: Base case

As your first number is $1$, your base case is at $n=1$. So, you show that $P(1)$ is true.

Left-hand side (LHS): $1$

Right-hand side (RHS): ${{1 \cdot (1+1)} \over 2 } = 1$

LHS = RHS, so $P(1)$ is true.

Step 2: Induction hypothesis

Assume that $P(k)$ is true for some integer $k \geq 1$.

$P(k)$ is:

$$1+2+...+k = {k (k+1) \over 2}$$Step 3: Induction step

You need to show that $P(k+1)$ is true. This means that you need to show that:

$$1+2+...+k+(k+1) = {(k+1)[ (k+1) +1]\over 2}$$One way to do this is by using algebra to get both the sides in the same form.

LHS:

$$1+2+...+k+(k+1) = {k(k +1)\over 2} + (k+1)$$Note how you used the induction hypothesis to make a substitution

$$= {{k(k +1)} \over 2} + {{2(k+1)} \over 2} = {k^2 + k + 2k + 2 \over 2} = {k^2 + 3k + 2 \over 2}$$RHS:

$${(k+1)[ (k+1) +1]\over 2} = {(k+1)^2 + (k+1)\over 2} = {(k^2+2k + 1) + (k+1)\over 2} = {k^2+3k + 2\over 2}$$LHS = RHS, so $P(k+1)$ is true.

By proof of induction, you have shown that the sum of the first n integers where $n \geq 1$ is ${n (n+1) \over 2}$.

Example: inequality proof

Prove that the following inequality is true:$$P(n): 1 + \frac{1}{2} + \frac{1}{4} + … + \left( \frac{1}{2} \right)^n < 2$$You can rewrite it like this:

$$\left( \frac{1}{2} \right)^0 + \left( \frac{1}{2} \right)^1+\left( \frac{1}{2} \right)^2 + … + \left( \frac{1}{2} \right)^n < 2$$Step 1: Base case

Here, the first integer is $n=0$, so you must show that $P(0)$ is true. On the left-hand side, you have $(\frac{1}{2})^0 = 1$, which is less than 2. So, $P(0)$ is true.

Step 2: Induction hypothesis

Assume that $P(k)$ is true for $k \geq 0$.

Here, $P(k)$ is:

$$\left( \frac{1}{2} \right)^0 + \left( \frac{1}{2} \right)^1+ … + \left( \frac{1}{2} \right)^k < 2$$

Step 3: Induction step

Here, you show that for every integer $k \geq 0$, if $P(k)$ is true then $P(k+1)$ is also true.

You need to show:

$$\left( \frac{1}{2} \right)^0 + \left( \frac{1}{2} \right)^1+ … + \left( \frac{1}{2} \right)^k + \left( \frac{1}{2} \right)^{k+1} < 2$$By assumption, you know that:

$$\left( \frac{1}{2} \right)^0 + (\left( \frac{1}{2} \right)^1+ … + \left( \frac{1}{2} \right)^{k-1} + \left( \frac{1}{2} \right)^k < 2$$Let's multiply both sides by $\frac{1}{2}$

$$\frac{1}{2} \cdot \left[\left( \frac{1}{2} \right)^0 + \left( \frac{1}{2} \right)^1+ … + \left( \frac{1}{2} \right)^{k-1} + \left( \frac{1}{2} \right)^k\right] < \frac{1}{2} \cdot 2$$$$\left( \frac{1}{2} \right)^1 + \left( \frac{1}{2} \right)^2+ … + \left( \frac{1}{2} \right)^k + \left( \frac{1}{2} \right)^{k+1} < 1$$Now, let's add $1$ to both sides. Remember $1 = (\frac{1}{2})^0$

$$\left( \frac{1}{2} \right)^0+\left( \frac{1}{2} \right)^1 + \left( \frac{1}{2} \right)^2+ … + \left( \frac{1}{2} \right)^k + \left( \frac{1}{2} \right)^{k+1} < \left( \frac{1}{2} \right)^0 + 1$$$$\left( \frac{1}{2} \right)^0+\left( \frac{1}{2} \right)^1 + \left( \frac{1}{2} \right)^2+ … + \left( \frac{1}{2} \right)^k + \left( \frac{1}{2} \right)^{k+1} < 2$$By proof of induction, you show that the inequality is true for all $n \geq 0$.

Example: base cases besides n=0 and n=1

You have seen examples where base cases are $n = 0$ or $n = 1$. These base cases are common, which is why proof of induction is useful for verifying statements for all nonnegative or positive integers. However, other base cases are possible. Let's take a look at an example: prove $n! > 2^n$ for $n \geq 4$.

Our property $P(n)$ is: $$n! > 2^n$$

Step 1: Base case

The given statement is not true for $n$ = 0, 1, 2, or 3, which is why we need to start at 4.

You need to show that $P(4)$ is true.

LHS: $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

RHS: $2^4 = 16$

$24 > 16$, so the statement is true for the base case.

Step 2: Induction hypothesis

Assume that $P(k)$ is true for $k \geq 4$.

Here, $P(k)$ is:

$$k! > 2^k$$Step 3: Induction step

To show that $P(k+1)$ is true, you must show that

$$(k+1)! > 2^{k+1}$$By assumption,

$$k! > 2^k$$On the LHS, to obtain $(k+1)!$, you multiply $k!$ by $(k+1)$. So, let's multiply both sides by $(k+1)$

$$(k+1) \cdot k! > (k+1) \cdot 2^k$$$$(k+1)! > (k+1) \cdot 2^k$$You know that $(k+1) > 2$ because you know $k \geq 4$. So, the following is true.

$$(k+1)! > 2 \cdot 2^k$$After simplification, you get:

$$(k+1)! > 2^{k+1}$$By proof of induction, you have shown that $n! > 2^n$ for $n \geq 4$.

Conclusion

If something has repeatedly occurred, then the principle of induction can help predict what will happen next and make generalizations.

In this topic, you looked at how we can use this principle to prove statements. You structured your proofs with three steps:

1. The base case;
2. Induction hypothesis, and;
3. Induction step.

You also took a look at some examples of proofs, and you saw that the 3rd step is typically the most challenging, as it requires applying, for example, algebra and geometry to help with problem-solving.