Induction is one of many methods for proving mathematical statements about numbers. The basic idea is that you prove a statement is true for a small number like 1. This is called the base case. Then, you show that if the statement is true for some random number \begin{align*}k\end{align*}, then it must also be true for \begin{align*}k+1\end{align*}.

An induction proof is like dominoes set up in a line, where the base case starts the falling cascade of truth. Once you have shown that in general if the statement is true for \begin{align*}k\end{align*} then it must also be true for \begin{align*}k+1\end{align*}, it means that once you show the statement is true for 1, then it must also be true for 2, and then it must also be true for 3, and then it must also be true for 4 and so on.

What happens when you forget the base case?

### Proof by Induction

**Induction** is a method of proof usually used to prove statements about positive whole numbers (the natural numbers). Induction has three steps:

- The
**base case**is where the statement is shown to be true for a specific number. Usually this is a small number like 1. This is the first domino to fall, creating a cascade and thus proving the statement true for every number greater than the base case. - The
**inductive hypothesis**is where the statement is assumed to be true for \begin{align*}k\end{align*}. - The
**inductive step/proof**is where you show that then the statement must be true for \begin{align*}k+1\end{align*}.

These three logical pieces will show that the statement is true for every number greater than the base case.

Suppose you wanted to use induction to prove: \begin{align*}n \ge 1,2+2^2+2^3+ \cdots + 2^n=2^{n-1}-2\end{align*}.

Start with the Base Case. Show that the statement works when \begin{align*}n=1\end{align*}:

\begin{align*}2^1=2\end{align*} and \begin{align*}2^{1+1}-2=4-2=2\end{align*}. Therefore, \begin{align*}2^1=2^{1+1}-2\end{align*}. (Both sides are equal to 2)

Next, state your Inductive Hypothesis. Assume that the statement works for some random number \begin{align*}k\end{align*}:

\begin{align*}2+2^2+ \cdots +2^k=2^{k+1}-2\end{align*} (You are assuming that this is a true statement)

Next, you will want to use algebra to manipulate the previous statement to prove that the statement is also true for \begin{align*}k+1\end{align*}. So, you will be trying to show that \begin{align*}2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2\end{align*}. Start with the inductive hypothesis and multiply both sides of the equation by 2. Then, do some algebra to get the equation looking like you want.

Inductive Hypothesis (starting equation): \begin{align*}2+2^2+ \cdots 2^k=2^{k+1}-2\end{align*}

Multiply by 2: \begin{align*}2(2+2^2+ \cdots +2^k)=2(2^{k+1}-2)\end{align*}

Rewrite: \begin{align*}2^2+2^3+ \cdots + 2^{k+1}=2^{k+1+1}-4\end{align*}

Add 2 to both sides: \begin{align*}2+2^2+2^3 + \cdots + 2^{k+1}=2^{k+1+1}-4+2\end{align*}

Simplify: \begin{align*}2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2\end{align*}

This is exactly what you were trying to prove! So, first you showed that the statement worked for \begin{align*}n=1\end{align*}. Then, you showed that the if the statement works for one number than it must work for the next number. This means, the statement must be true for all numbers greater than or equal to 1.

The idea of induction can be hard to understand at first and it definitely takes practice. One thing that makes induction tricky is that there is not a clear procedure for the “proof” part. With practice, you will start to see some common algebra techniques for manipulating equations to prove what you are trying to prove.

### Examples

#### Example 1

Earlier, you were asked what happens if you forget the base case in induction. If you forget the base case in an induction proof, then you haven’t really proved anything. You can get silly results like this “proof” of the statement: “\begin{align*}1=3\end{align*}”

**Base Case:** Missing

**Inductive Hypothesis:** \begin{align*}k=k+1\end{align*} where \begin{align*}k\end{align*} is a counting number.

**Proof:** Start with the assumption step and add one to both sides.

\begin{align*}k &=k+1 \\ k+1 &=k+2\end{align*}

Thus by transitivity of equality:

\begin{align*}k &=k+1=k+2 \\ k &=k+2\end{align*}

Since \begin{align*}k\end{align*} is a counting number, \begin{align*}k\end{align*} could equal 1. Therefore:

\begin{align*}1=3\end{align*}

#### Example 2

There is something wrong with this proof. Can you explain what the mistake is?

\begin{align*}For \ n \ge 1: 1^2+2^2+3^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}

**Base Case**: \begin{align*}1=1^2=\frac{1(1+1)(2 \cdot 1+1)}{6}=\frac{1 \cdot 2 \cdot 3}{6}=\frac{6}{6}=1\end{align*}

**Inductive Hypothesis:** Assume the following statement is true:

\begin{align*}1^2+2^2+3^2+ \cdots + k^2=\frac{k(k+1)(2k+1)}{6}\end{align*}

**Proof:** You want to show the statement is true for \begin{align*}k+1\end{align*}.

“Since the statement is assumed true for \begin{align*}k\end{align*}, which is any number, then it must be true for \begin{align*}k+1\end{align*}. You can just substitute \begin{align*}k+1 \end{align*} in.”

\begin{align*}1^2+2^2+3^2+ \cdots +(k+1)^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\end{align*}

This is the most common fallacy when doing induction proofs. The fact that the statement is assumed to be true for \begin{align*}k\end{align*} does not immediately imply that it is true for \begin{align*}k+1\end{align*} and you cannot just substitute in \begin{align*}k+1\end{align*} to produce what you are trying to show. his is equivalent to assuming true for all numbers and then concluding true for all numbers which is circular and illogical.

#### Example 3

Write the base case, inductive hypothesis and what you are trying to show for the following statement. Do not actually prove it.

\begin{align*}1^3+2^3+3^3+ \cdots +n^3=\frac{n^2(n+1)^2}{4}\end{align*}

**Base Case:** \begin{align*}1^3=\frac{1^2(1+1)^2}{4}\end{align*} (Both sides are equal to 1)

**Inductive Hypothesis:** Assume the following statement is true:

\begin{align*}1^3+2^3+3^3+ \cdots +k^3=\frac{k^2(k+1)^2}{4}\end{align*}

Next, you would want to prove that the following is true:

\begin{align*}1^3+2^3+3^3+ \cdots +k^3+(k+1)^3=\frac{(k+1)^2((k+1)+1)^2}{4}\end{align*}

#### Example 4

Prove the following statement: \begin{align*}For \ n \ge 1, 1^3+2^3+3^3+ \cdots n^3=(1+2+3+ \cdots n)^2\end{align*}.

**Base Case(s):** Two base cases are shown however only one is actually necessary.

\begin{align*}1^3 &=1^2 \\ 1^3+2^3 &=1+8=9=3^2=(1+2)^2 \end{align*}

**Inductive Hypothesis:** Assume the statement is true for some number \begin{align*}k\end{align*} . In other words, assume the following is true:

\begin{align*}1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2\end{align*}

You want to show the statement is true for \begin{align*}k+1\end{align*}. It is a good idea to restate what your goal is at this point. Your goal is to show that:

\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=(1+2+3+ \cdots k+(k+1))^2\end{align*}

You need to start with the assumed case and do algebraic manipulations until you have created what you are trying to show (the equation above):

\begin{align*}1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2\end{align*}

From the work you have done with arithmetic series you should notice:

\begin{align*}1+2+3+4+ \cdots +k=\frac{k}{2}(2+(k-1))=\frac{k(k+1)}{2}\end{align*}

Substitute into the right side of the equation and add \begin{align*}(k+1)^3\end{align*} to both sides:

\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=\left(\frac{k(k+1)}{2} \right)^2+(k+1)^3\end{align*}

When you combine the right hand side algebraically you get the result of another arithmetic series.

\begin{align*}1^3+2^3+3^3+ \cdots k^3+(k+1)^3=\left(\frac{(k+1)(k+2)}{2} \right)^2=(1+2+3+ \cdots k+(k+1))^2\end{align*}

\begin{align*}\therefore\end{align*}

The symbol \begin{align*}\therefore\end{align*} is one of many indicators like QED that follow a proof to tell the reader that the proof is complete.

#### Example 5

Prove the following statement using induction:

*For* \begin{align*}n \ge 1, \ 1+2+3+4+ \cdots + n=\frac{n(n+1)}{2}\end{align*}

**Base Case:** \begin{align*}1=\frac{1(1+1)}{2}=1 \cdot \frac{2}{2}=1\end{align*}

**Inductive Hypothesis:** \begin{align*}1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}\end{align*}

**Proof:** Start with what you know and work to showing it true for \begin{align*}k+1\end{align*}.

Inductive Hypothesis: \begin{align*}1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}\end{align*}

Add \begin{align*}k+1\end{align*} to both sides: \begin{align*}1+2+3+4+ \cdots + k+(k+1)=\frac{k(k+1)}{2}+(k+1)\end{align*}

Find a common denominator for the right side: \begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{k^2+k}{2}+\frac{2k+2}{2}\end{align*}

Simplify the right side: \begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{k^2+3k+2}{2}\end{align*}

Factor the numerator of the right side: \begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{(k+1)(k+2)}{2}\end{align*}

Rewrite the right side: \begin{align*}1+2+3+4+ \cdots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}\end{align*}

\begin{align*}\therefore\end{align*}

### Review

For each of the following statements: a) show the base case is true; b) state the inductive hypothesis; c) state what you are trying to prove in the inductive step/proof. *Do not prove yet.*

1. For \begin{align*}n \ge 5, \ 4n < 2^n\end{align*}.

2. For \begin{align*}n \ge 1, \ 8^n-3^n\end{align*} is divisible by 5.

3. For \begin{align*}n \ge 1, \ 7^n-1\end{align*} is divisible by 6.

4. For \begin{align*}n \ge 2, \ n^2 \ge 2n\end{align*}.

5. For \begin{align*}n \ge 1, \ 4^n+5\end{align*} is divisible by 3.

6. For \begin{align*}n \ge 1, \ 0^2+1^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}

Now, prove each of the following statements. Use your answers to problems 1-6 to help you get started.

7. For \begin{align*}n \ge 5, \ 4n <2^n\end{align*}.

8. For \begin{align*}n \ge 1, \ 8^n-3^n\end{align*} is divisible by 5.

9. For \begin{align*}n \ge 1, \ 7^n-1\end{align*} is divisible by 6.

10. For \begin{align*}n \ge 2, \ n^2 \ge 2n\end{align*}.

11. For \begin{align*}n \ge 1, \ 4^n+5\end{align*} is divisible by 3.

12. For \begin{align*}n \ge 1, \ 0^2+1^2+ \cdots +n^2=\frac{n(n+1)(2n+1)}{6}\end{align*}

13. You should believe that the following statement is clearly false. What happens when you try to prove it true by induction?

For \begin{align*}n \ge 2, \ n^2 < n\end{align*}

14. Explain why the base case is necessary for proving by induction.

15. The principles of inductive proof can be used for other proofs besides proofs about numbers. Can you prove the following statement from geometry using induction?

The sum of the interior angles of any \begin{align*}n-gon\end{align*} is \begin{align*}180(n-2)\end{align*} for \begin{align*}n \ge 3\end{align*}.

### Review (Answers)

To see the Review answers, open this PDF file and look for section 12.9.