7.3.1.1: Inductive Proofs

Last updated
Save as PDF

Page ID: 14791

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Inductive Proofs

Proving a theory can be a daunting process. No matter how many times you try something with the same result, how can you be certain that it will always have the same result, no matter what?

For example, if you were to see someone fill a water balloon with ice water and hold it out the window, you would probably either cringe in anticipation of the shouting below, or eagerly watch, depending on the situation. In either case, your response would be based on the fact that you would be certain that a water balloon would pop on someone's head if dropped out the window onto them. Your certainty would be based on your past experience with water balloons and sidewalks, and you'd very likely be correct, but until the balloon actually hits the target, there isn't any way to be absolutely certain it will break.

In math, situations like this occur a lot. Based on repeated experience, you may develop a rule or shortcut to save time or effort when calculating. However, you may be rightly concerned about using such shortcuts on an important exam. After all, how can you be certain that the shortcut works in every situation?

Proofs by Induction

In this lesson you will learn about mathematical induction, a method of proof that will allow you to prove that a particular statement is true for all positive integers.

First let's make a guess at a formula that will give us the sum of all the positive integers from 1 to n for any integer n. If we look closely at Gauss’s Formula we used in the last lesson, where the young boy was able to quickly add up all of the numbers between 1 and 100, we can see a general form: there were 100 numbers, hence 50 pairs. So if there were n numbers, there would be (n/2) pairs. The first and last numbers were 1 and 100. They added together to give us 101. This number was the sum of each pair in the overall sum. So in general, we could add together 1 and n to get the sum of each pair. Therefore we might hypothesize that the sum of the first n positive integers is n((1 + n)/2). However, we have not proven that this formula works for all positive integers n. Mathematical induction will allow us to do this.

The overall idea of induction is this: Assume that a statement is true for some arbitrary value of n, and show that if the statement is true for n = k, it must also be true for n = k+1. This process is used because we can’t actually show it is true for every value. For example, you might show that the above equation is true for n = 100, and then n = 101, and then n = 102, but then what about 103? 104? 500? A million?

Mathematical induction allows us prove that a statement is true in three steps:

Step 1) The base case: prove that the statement is true for the first value of n. In some cases, this might be n = 0. In the case of the integer sum formula above, we would start with n = 1. Often with induction you may want to expand the first step by showing that the statement is true for several values of n.

Step 2) The inductive hypothesis: assume that the statement is true for the k^th value of n. In the case of the integer sum formula, we would state the following: the sum of the first k positive integers is k((1 + k)/2).

Step 3) The inductive step: use the inductive hypothesis to show that the statement is true for the k + 1^th step. In the case of the integer sum formula, we would prove the following: assuming that the sum of the first k positive integers is k((1 + k)/2) , the sum of the first k +1 positive integers is ((k + 1) (1 + (k + 1)/2).

Carrying out this kind of proof requires that you perform each of these steps., For the third step in particular you must rely on your algebra skills.

Examples

Example 1

Earlier, you were asked how you could be certain that a theory always results in the correct answer.

Solution

Situations like this are custom-made for inductive proofs. If you come up with a shortcut on your math, and want to be absolutely certain it works in every situation, run it through the proof explained in this lesson. If it passes all of the tests, you can be sure it will work with any number you throw at it.

Example 2

Prove: The sum of the first n positive integers is \(\ \frac{n(1+n)}{2}\).

Solution

Use the three steps of mathematical induction:

Step 1) The base case:

If n = 1, the entire sequence is just 1 and therefore the sum is 1. Also, \(\ \frac{n(1+n)}{2}=\frac{1(1+1)}{2}=\frac{2}{2}=1\)

This establishes the base case.

Step 2) Assume that the sum of the first \(\ k\) positive integers is \(\ \frac{k(1+k)}{2}\).

In other words, assume that \(\ 1+2+3+\cdots+k=\frac{k(1+k)}{2}\).

Step 3) We must show that the sum of the first \(\ k+1\) positive integers is \(\ \frac{(k+1)(1+(k+1))}{2}\).

In other words, we must show that \(\ 1+2+3+\cdots+k+(k+1)=\frac{(k+1)(1+(k+1))}{2}\)

There are two key ideas to keep in mind as you are carrying out this step: (1) remember to use the assumption and (2) remember how sums work.

How does the sum of the first k + 1 integers relate to the sum of the first k integers? To get the sum of the first k + 1 integers we must add up all the integers from 1 to k and then add on k + 1, since the sum of the first k + 1 integers is \(\ 1+2+3+⋯+k+(k+1)\).

Now we must use our assumption. Remember that we are assuming that

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

Substitute \(\ \frac{k(1+k)}{2}\) in for \(\ 1+2+3+\cdots+k\) in our expression above for the sum of the first k + 1 integers.

Now we have the sum of the first k + 1 integers is \(\ \frac{k(1+k)}{2}+(k+1)\).

Remember that we are trying to show that the sum of the first k + 1 integers is \(\ \frac{(k+1)(1+(k+1))}{2}\). With some algebraic manipulation, we can show that \(\ \frac{k(1+k)}{2}+(k+1)=\frac{(k+1)(1+(k+1))}{2}\).

See below:

\(\ \frac{k(1+k)}{2}+(k+1)\)
\(\ =\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\)	The common denominator is 2 Add the fractions
\(\ =\frac{k(k+1)+2(k+1)}{2}\)	Simplify the numerator
\(\ =\frac{k^{2}+k+2 k+2}{2}\)
\(\ =\frac{k^{2}+3 k+2}{2}\)	Factor the numerator
\(\ =\frac{(k+1)(k+2)}{2}\)	The term (k+2) is the same as ((k+1)+1)
\(\ =\frac{(k+1)((k+1)+1)}{2}\)

We have shown that our formula for the sum of the first n integers is true for n = 1. We have also shown that whenever it is true for n = k it is also true for n = k+1. Since we know it is true for n = 1, it must therefore be true for n = 2. Similarly, since it is true for n = 2, it must therefore be true for n = 3, and it must therefore be true for n = 4,... You should see that we have proven that the sum of the first n positive integers is \(\ \frac{n(1+n)}{2}\) for all integer values of n. We can similarly prove a formula for the sum of the first n terms in an arithmetic series.

Example 3

Prove that the sum of the first n terms of an arithmetic series is \(\ S_{n}=\frac{n\left(a_{1}+a_{n}\right)}{2}\) where a₁ is the first term in the series and a_n is the last term.

Solution

Recall that in an arithmetic sequence or series, there is a common difference, d, between each term, and that the n^th term is a_n=a₁+d(n−1) We need to keep these ideas in mind in order to complete the proof.

Step 1) Base case: if n=1, then S₁=a₁

Using the hypothesized formula, we have

\(\ S_{1}=\frac{1\left(a_{1}+a_{1}\right)}{2}=\frac{2 a_{1}}{2}=a_{1}\)

Step 2) Assume that \(\ S_{k}=\frac{k\left(a_{1}+a_{k}\right)}{2}\)

Step 3) Prove that if our formula for \(\ S_{k}\) is true then \(\ S_{k+1}=\frac{(k+1)\left(a_{1}+a_{k+1}\right)}{2}\).

We can think of the sum of the first k + 1 terms as the sum of the first k terms, plus the k + 1 term.

So we have:

\(\ S_{k+1}=S_{k}+a_{k+1}\)	Add the \(\ k+1\) term
\(\ =\frac{k\left(a_{1}+a_{k}\right)}{2}+a_{k+1}\)	Use the formula for \(\ S_{k}\) from step 2
\(\ =\frac{k\left(a_{1}+a_{k}\right)}{2}+\frac{2 a_{k+1}}{2}\)	The common denominator is 2
\(\ =\frac{k\left(a_{1}+a_{k}\right)+2 a_{k+1}}{2}\)	Add the fractions
\(\ =\frac{k\left(a_{1}+\left(a_{1}+(k-1) d\right)\right)+2\left(a_{1}+k d\right)}{2}\)	Use substitution: remember that \(\ a_{m}=a_{1}+(m-1) d\) for any positive integer \(\ m\). So \(\ a_{k}=a_{1}+(k-1) d\) and \(\ a_{k+1}=a_{1}+(k) d\)
\(\ =\frac{k\left(a_{1}+a_{1}+k d-d\right)+2 a_{1}+2 k d}{2}\)
\(\ =\frac{k a_{1}+k a_{1}+k^{2} d-k d+2 a_{1}+2 k d}{2}\)	Distribute and combine like terms
\(\ =\frac{2 k a_{1}+2 a_{1}+k^{2} d+k d}{2}\)	Factor by grouping
\(\ =\frac{2 a_{1}(k+1)+k d(k+1)}{2}\)
\(\ =\frac{(k+1)\left(2 a_{1}+k d\right)}{2}\)
\(\ =\frac{(k+1)\left(a_{1}+a_{1}+k d\right)}{2}\)	Again, \(\ a_{k+1}=a_{1}+(k) d\)
\(\ =\frac{(k+1)\left(a_{1}+a_{k+1}\right)}{2}\)

Example 1

Use induction to prove that \(\ 1^{2}+2^{2}+3^{2}+\cdots+n^{2}=\frac{n(n+1)(2 n+1)}{6}\).

Solution

Step 1) Base case: \(\ 1^{2}=1\)

\(\ \frac{1(1+1)(2(1)+1)}{6}=\frac{2(3)}{6}=1\)

Step 2) Inductive hypothesis: \(\ 1^{2}+2^{2}+3^{2}+\ldots+k^{2}=\frac{k(k+1)(2 k+1)}{6}\)

Step 3) Inductive step: show that

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

First, note that \(\ \frac{(k+1)(k+1+1)(2(k+1)+1)}{6}=\frac{(k+1)(k+2)(2 k+3)}{6}\)

Now we have:

\(\ 1^{2}+2^{2}+3^{2}+\ldots+k^{2}+(k+1)^{2}\)
\(\ =\frac{k(k+1)(2 k+1)}{6}+(k+1)^{2}\)
\(\ =\frac{k(k+1)(2 k+1)+6(k+1)^{2}}{6}=\frac{(k+1)[k(2 k+1)+6(k+1)]}{6}\)
\(\ =\frac{(k+1)\left[2 k^{2}+k+6 k+6\right]}{6}=\frac{(k+1)\left[2 k^{2}+7 k+6\right]}{6}=\frac{(k+1)(2 k+3)(k+2)}{6}\)

Example 5

Use induction to prove that \(\ 1+3+5+\cdots+(2 n-1)=n^{2}\).

Solution

Step 1) Base case: \(\ 1=1^{2}\)

Step 2) Inductive hypothesis: assume that \(\ 1+3+5+\ldots+(2 k-1)=k^{2}\)

Step 3) Show that \(\ 1+3+5+\ldots+(2 k-1)+(2 k+1)=(k+1)^{2}\)

We have: \(\ 1+3+5+\ldots+(2 k-1)+(2 k+1)=k^{2}+(2 k+1)\)

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

Example 6

Use induction to prove that \(\ 1^{3}+2^{3}+3^{3}+\cdots+n^{3}=\frac{n^{2}(n+1)^{2}}{4}\).

Solution

Step 1) Base case: \(\ 1^{3}=1\)

\(\ \frac{1^{2}(1+1)^{2}}{4}=\frac{2^{2}}{4}=1\)

Step 2) Assume that \(\ 1^{3}+2^{3}+3^{3}+\ldots+k^{3}=\frac{k^{2}(k+1)^{2}}{4}\)

Step 3) Show that \(\ 1^{3}+2^{3}+3^{3}+\ldots+k^{3}+(k+1)^{3}=\frac{(k+1)^{2}((k+1)+1)^{2}}{4}\)

First, note that \(\ \frac{(k+1)^{2}((k+1)+1)^{2}}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}\)

Now we have:

\(\ 1^{3}+2^{3}+3^{3}+\ldots+k^{3}+(k+1)^{3}\)
\(\ =\frac{k^{2}(k+1)^{2}}{4}+(k+1)^{3}\)
\(\ =\frac{k^{2}(k+1)^{2}+4(k+1)^{3}}{4}\)
\(\ =\frac{(k+1)^{2}\left[k^{2}+4(k+1)\right]}{4}=\frac{(k+1)^{2}\left[k^{2}+4 k+4\right]}{4}=\frac{(k+1)^{2}(x+2)^{2}}{4}\)

Review

Use induction to prove the following:

\(\ -15-25-35+\ldots-10 k-5=k(-5 k-10)\)
\(\ 1+9+9^{2}+9^{3}+\ldots+9^{k}=\frac{9^{k+1}-1}{9-1}\)
\(\ 4+8+12+\ldots+4 k=2 k(k+1)\)
\(\ 6+8+10+\ldots+2 k+4=k(k+5)\)
\(\ 1+2+3+\ldots+k=\frac{1}{2} k(k+1)\)
\(\ 1+6+6^{2}+6^{3}+\ldots+6^{k}=\frac{6^{k+1}-1}{6-1}\)
\(\ -1-5-9+\ldots-4 k+3=k(-2 k+1)\)
\(\ 1+4+4^{2}+4^{3}+\ldots+4^{k}=\frac{4^{k+1}-1}{4-1}\)
\(\ 3+6+9+\ldots+3 k=\frac{3}{2} k(k+1)\)
\(\ -1-3-5+\ldots-2 k+1=k(-k)\)
\(\ 1+3+3^{2}+3^{3}+\ldots+3^{k}=\frac{3^{k+1}-1}{3-1}\)
\(\ 1+7+7^{2}+7^{3}+\ldots+7^{n}=\frac{7^{n+1}-1}{6}\)
\(\ 4+8+12+\ldots+4 n=2 n(n+1)\)
\(\ 10+18+26+\ldots 8 n+2=n(4 n+6)\)
\(\ 6+12+18+\ldots+6 n=3 n(n+1)\)

Review (Answers)

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

Vocabulary

Term	Definition
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	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 is a method of mathematical proof typically used to establish that a given statement is true for all positive integers.
inductive hypothesis	In an induction proof, the inductive hypothesis is the step where you assume the statement is true for k.
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.
Mathematical induction	Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all positive integers.
n^th term	The n^th term in a series commonly refers to the last term in a series, often left unspecified.
proof	A proof is a series of true statements leading to the acceptance of truth of a more complex statement.
series sum	The series sum is the total sum of all of the numbers in a series.