<meta http-equiv="refresh" content="1; url=/nojavascript/">
You are viewing an older version of this Concept. Go to the latest version.

# Inductive Proofs

## Prove a statement is true for all positive integers if true for "n" and "n + 1."

%
Progress
Progress
%
Induction Proofs

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 $k$ , then it must also be true for $k+1$ .

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 $k$ then it must also be true for $k+1$ , 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?

#### Guidance

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

1. The base case is where the statement is shown to be true for a specific number. Usually this is a small number like 1.
2. The inductive hypothesis is where the statement is assumed to be true for $k$ .
3. The inductive step/proof is where you show that then the statement must be true for $k+1$ .

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: $n \ge 1,2+2^2+2^3+ \cdots + 2^n=2^{n-1}-2$ .

Start with the Base Case . Show that the statement works when $n=1$ :

$2^1=2$ and $2^{1+1}-2=4-2=2$ . Therefore, $2^1=2^{1+1}-2$ . (Both sides are equal to 2)

Next, state your Inductive Hypothesis . Assume that the statement works for some random number $k$ :

$2+2^2+ \cdots +2^k=2^{k+1}-2$ (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 $k+1$ . So, you will be trying to show that $2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2$ . 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): $2+2^2+ \cdots 2^k=2^{k+1}-2$

Multiply by 2: $2(2+2^2+ \cdots +2^k)=2(2^{k+1}-2)$

Rewrite: $2^2+2^3+ \cdots + 2^{k+1}=2^{k+1+1}-4$

Add 2 to both sides: $2+2^2+2^3 + \cdots + 2^{k+1}=2^{k+1+1}-4+2$

Simplify: $2+2^2+ \cdots +2^{k+1}=2^{k+1+1}-2$

This is exactly what you were trying to prove! So, first you showed that the statement worked for $n=1$ . 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.

Example A

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

$For \ n \ge 1: 1^2+2^2+3^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}$

Base Case:   $1=1^2=\frac{1(1+1)(2 \cdot 1+1)}{6}=\frac{1 \cdot 2 \cdot 3}{6}=\frac{6}{6}=1$

Inductive Hypothesis: Assume the following statement is true:

$1^2+2^2+3^2+ \cdots + k^2=\frac{k(k+1)(2k+1)}{6}$

Proof: You want to show the statement is true for $k+1$ .

“Since the statement is assumed true for $k$ , which is any number, then it must be true for $k+1$ . You can just substitute $k+1$ in.”

$1^2+2^2+3^2+ \cdots +(k+1)^2=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$

Solution: This is the most common fallacy when doing induction proofs.  The fact that the statement is assumed to be true for $k$ does not immediately imply that it is true for $k+1$ and you cannot just substitute in $k+1$ 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 B

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

$1^3+2^3+3^3+ \cdots +n^3=\frac{n^2(n+1)^2}{4}$

Solution:

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

Inductive Hypothesis:  Assume the following statement is true:

$1^3+2^3+3^3+ \cdots +k^3=\frac{k^2(k+1)^2}{4}$

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

$1^3+2^3+3^3+ \cdots +k^3+(k+1)^3=\frac{(k+1)^2((k+1)+1)^2}{4}$

Example C

Prove the following statement: $For \ n \ge 1, 1^3+2^3+3^3+ \cdots n^3=(1+2+3+ \cdots n)^2$ .

Solution:

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

$1^3 &=1^2 \\1^3+2^3 &=1+8=9=3^2=(1+2)^2$

Inductive Hypothesis: Assume the statement is true for some number  $k$ . In other words, assume the following is true:

$1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2$

Proof: You want to show the statement is true for $k+1$ . It is a good idea to restate what your goal is at this point. Your goal is to show that:

$1^3+2^3+3^3+ \cdots k^3+(k+1)^3=(1+2+3+ \cdots k+(k+1))^2$

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):

$1^3+2^3+3^3+ \cdots k^3=(1+2+3+ \cdots k)^2$

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

$1+2+3+4+ \cdots +k=\frac{k}{2}(2+(k-1))=\frac{k(k+1)}{2}$

Substitute into the right side of the equation and add $(k+1)^3$ to both sides:

$1^3+2^3+3^3+ \cdots k^3+(k+1)^3=\left(\frac{k(k+1)}{2} \right)^2+(k+1)^3$

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

$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$

$\therefore$

The symbol $\therefore$  is one of many indicators like QED that follow a proof to tell the reader that the proof is complete.

Concept Problem Revisited

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: “ $1=3$

Base Case: Missing

Inductive Hypothesis: $k=k+1$ where $k$ is a counting number.

$k &=k+1 \\k+1 &=k+2$

Thus by transitivity of equality:

$k &=k+1=k+2 \\k &=k+2$

Since $k$  is a counting number,  $k$ could equal 1. Therefore:

$1=3$

#### Vocabulary

The base case is the anchor step. It 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 the step where you assume the statement is true for $k$ .

The inductive step is the proof . It is when you show the statement is true for  $k+1$ using only the inductive hypothesis and algebra.

#### Guided Practice

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

For $n \ge 1, \ n^3+2n$ is divisible by 3 for any positive integer $n$

2. Complete the proof for the previous problem.

3. Prove the following statement using induction:

For $n \ge 1, \ 1+2+3+4+ \cdots + n=\frac{n(n+1)}{2}$

1. Base Case:   $1^3+2 \cdot 1=3$  which is divisible by 3.

Inductive Step: Assume the following is true for $k$ :

$k^3+2k$ divisible by 3.

Next, you will want to show the following is true for $k+1$ :

$(k+1)^3+2(k+1)$ is divisible by 3.

2. The goal is to show that $(k+1)^3+2(k+1)$ is divisible by 3 if you already know $k^3+2k$ is divisible by 3. Expand $(k+1)^3+2(k+1)$ to see what you get:

$(k+1)^3+2(k+1) &=k^3+3k^2+3k+1+2k+2 \\& =(k^3+2k)+3(k^2+k+1)$

$k^3+2k$ is divisible by 3 by assumption (the inductive step) and $3(k^2+k+1)$ is clearly a multiple of 3 so is divisible by 3. The sum of two numbers that are divisible by is also divisible by 3.

$\therefore$

3. Base Case: $1=\frac{1(1+1)}{2}=1 \cdot \frac{2}{2}=1$

Inductive Hypothesis: $1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}$

Proof: Start with what you know and work to showing it true for $k+1$ .

Inductive Hypothesis: $1+2+3+4+ \cdots +k=\frac{k(k+1)}{2}$

Add $k+1$ to both sides: $1+2+3+4+ \cdots + k+(k+1)=\frac{k(k+1)}{2}+(k+1)$

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

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

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

Rewrite the right side: $1+2+3+4+ \cdots +k+(k+1)=\frac{(k+1)((k+1)+1)}{2}$

$\therefore$

#### Practice

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 $n \ge 5, \ 4n < 2^n$ .

2. For  $n \ge 1, \ 8^n-3^n$  is divisible by 5.

3. For $n \ge 1, \ 7^n-1$ is divisible by 6.

4. For $n \ge 2, \ n^2 \ge 2n$ .

5. For $n \ge 1, \ 4^n+5$ is divisible by 3.

6. For $n \ge 1, \ 0^2+1^2+ \cdots + n^2=\frac{n(n+1)(2n+1)}{6}$

7. For $n \ge 5, \ 4n <2^n$ .

8. For $n \ge 1, \ 8^n-3^n$  is divisible by 5.

9. For $n \ge 1, \ 7^n-1$  is divisible by 6.

10. For $n \ge 2, \ n^2 \ge 2n$ .

11. For $n \ge 1, \ 4^n+5$ is divisible by 3.

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

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

For $n \ge 2, \ n^2 < n$

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 $n-gon$ is   $180(n-2)$ for $n \ge 3$ .

### Vocabulary Language: English

arithmetic series

arithmetic series

An arithmetic series is the sum of an arithmetic sequence, a sequence with a common difference between each two consecutive terms.
Base Case

Base Case

In an induction proof, the base case is the anchor step. It is the first domino to fall, creating a cascade and thus proving the statement true for every number greater than the base case.
induction

induction

Induction is a method of mathematical proof typically used to establish that a given statement is true for all positive integers.
inductive hypothesis

inductive hypothesis

In an induction proof, the inductive hypothesis is the step where you assume the statement is true for $k$.
inductive step

inductive step

In an induction proof, the inductive step is the proof. It is when you show the statement is true for $k+1$ using only the inductive hypothesis and algebra.
proof

proof

A proof is a series of true statements leading to the acceptance of truth of a more complex statement.