House of Math

What Is Proof by Induction?

A proof by induction is a type of proof where you try to state something general from a smaller context. In an inductive proof, you start by assuming that something is true for a given value. Then, you want to show that if it holds for a certain value, then it has to hold for the following value as well. If this is true for an arbitrary value, it must be true for all values.

Here are three steps which are very useful to follow in order to construct an inductive proof:

Rule

How to Write a Proof by Induction

1.: Check that the claim holds for the first value of $n$ .
2.: Assume that the claim holds for $n = k$ , such that $\dots$
3.: Then, show that the claim holds for $n = k + 1$ , such that $\dots$

Note! The key to proofs by induction is to insert your assumption from Item 2 into Item 3. This is the critical element of these proofs!

Example 1

Series by Induction

Show that $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$

1.: Check that this is correct for the first value of $n$ by inserting the value into the expression $2 n - 1$ : $\begin{array}{l} 2 (1) - 1 & = 1^{2} \\ 2 - 1 & = 1^{2} \\ 1 & = 1^{2} & ✓ \end{array}$
2.: Assume that it is correct for $n = k$ , now using the expression directly in the exercise, only switching $n$ with $k$ :

1 + 3 + 5 + \dots + (2 k - 1) = k^{2}

(1)

3.: You need to show that this is correct for $n = k + 1$ , now using the expression directly in the exercise, only switching $n$ with $k + 1$ . Don’t forget parentheses!

1 + \dots + (2 k - 1) + (2 (k + 1) - 1) = {(k + 1)}^{2}

(2)

1 + 3 + \dots + (2 k - 1) + (2 (k + 1) - 1) = {(k + 1)}^{2}

(3)

4.: You now begin the calculation part of the proof. It begins with the left-hand side of (3), and continues with assumption (1). Look closely at what happens below! Finally, you’ll end up with what is on the right-hand side of the equality in (3).
Now you have to use the assumption to write a clean expression for the first $k$ terms:

\begin{array}{l} \underset{Insert the expression (1)}{\underset{⏟}{1 + 3 + 5 + \dots + (2 k - 1)}} + (2 (k + 1) - 1) \\ = k^{2} + (2 (k + 1) - 1) \\ = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} \end{array}

\begin{array}{l} \underset{Insert the expression from (1)}{\underset{⏟}{1 + 3 + 5 + \dots + (2 k - 1)}} + (2 (k + 1) - 1) & = k^{2} + (2 (k + 1) - 1) \\ = k^{2} + 2 k + 1 \\ = {(k + 1)}^{2} \end{array}

Q.E.D

Example 2

Divisibility by Induction

Show that $n^{2} - n$ is divisible by 2

If something is divisible by 2, it has 2 as a factor. In other words, it must be possible to write it as $n^{2} - n = 2 t$ , where $t$ is an integer.

1.: Check that it is correct for the first value of $n$ by inserting the value into the expression $n^{2} - n$ : $\begin{array}{l} 1^{2} - 1 = 0 & = 2 \cdot 0 & ✓ \end{array}$
2.: Assume that it’s correct for $n = k$ , now using the expression directly in the exercise, only switching $n$ with $k$ :

k^{2} - k = 2 t

(4)

3.: You need to show that this is correct for $n = k + 1$ , now using the expression directly in the exercise, only switching $n$ with $k + 1$ . Don’t forget parentheses!

(5)

4.: You now begin the calculation part of your proof. It begins with the left-hand side of (5), and continues with the additional assumption (4). Look closely at what happens below! Finally, you’ll end up with what is on the right-hand side of the equality in (5).
Now using the assumption, $n = k + 1$ gives the following:

\begin{array}{l} {(k + 1)}^{2} - (k + 1) & = \underset{Shuffle this to use (4)}{\underset{⏟}{k^{2} + 2 k + 1 - k - 1}} \\ = \underset{Using (4)}{\underset{⏟}{k^{2} - k}} + 2 k \\ = 2 u + 2 k \\ = 2 (u + k) \\ = 2 t, where t = u + k \end{array}

Q.E.D

Example 3

Derivatives by Induction

Let $f (x) = e^{2 x}$ . Show that $f^{(n)} = 2^{n} e^{2 x}$ .

Here $f^{(n)}$ means that $f$ is differentiated $n$ times.

1.: Check that the claim is correct for the first value of $n$ by evaluating the expression $f^{(n)} = 2^{n} e^{2 x}$ : $\begin{array}{l} f^{(1)} (x) = 2 e^{2 x} & = 2^{1} e^{2 x} & ✓ \end{array}$
2.: Assuming it’s correct for $n = k$ , now using the expression directly in the exercise, only switching $n$ with $k$ :

f^{(k)} (x) = 2^{k} e^{2 x}

(6)

3.: You need to show that this implies that claim is correct for $n = k + 1$ , now using the expression directly in the exercise, only switching $n$ with $k + 1$ . Don’t forget parentheses!

f^{(k + 1)} (x) = 2^{k + 1} e^{2 x}

(7)

4.: You now begin the calculation part of your proof. It begins with the left-hand side of (7), and continues by inserting the assumption (6). Look closely at what happens below! Finally, you’ll end up with what is on the right-hand side of the equality in (7).
Now you need to use the assumption by writing $f^{(k + 1)} (x)$ as ${(f^{(k)} (x))}^{'}$ : $\begin{array}{l} f^{(k + 1)} (x) & = \underset{Insert (6)}{\underset{⏟}{{(f^{(k)} (x))}^{'}}} \\ = {(2^{k} e^{2 x})}^{'} \\ = 2 \cdot 2^{k} e^{2 x} \\ = 2^{k + 1} e^{2 x} \end{array}$
Q.E.D

Want to know more?Sign UpIt's free!

Done

Continue

Proof of the Pythagorean Theorem