7.6: Inductive Proofs
Proving a theory can be a daunting process, after all, 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 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?
Watch This
Embedded Video:
 PatrickJMT: Proof by Induction
Guidance
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.
Inductive Proofs
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.
Example A
Prove: The sum of the first n positive integers is \begin{align*}\frac{n(1 + n)} {2}\end{align*}
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, \begin{align*}\frac{n(1 + n)} {2} = \frac{1(1 + 1)} {2} = \frac{2} {2} = 1\end{align*}
n(1+n)2=1(1+1)2=22=1 .  This establishes the base case.
Step 2) Assume that the sum of the first \begin{align*}k\end{align*}

In other words, assume that \begin{align*}1+2+3+\cdots+k=\frac{k(1+k)}{2}\end{align*}
1+2+3+⋯+k=k(1+k)2 .
Step 3) We must show that the sum of the first \begin{align*}k + 1\end{align*}

In other words, we must show that \begin{align*}1+2+3+\cdots+k+(k+1)=\frac{(k+1)(1+(k+1))}{2}\end{align*}
1+2+3+⋯+k+(k+1)=(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 \begin{align*}1+2+3+\cdots+k+(k+1)\end{align*}
1+2+3+⋯+k+(k+1) .

Now we must use our assumption. Remember that we are assuming that \begin{align*}1+2+3+\cdots+k=\frac{k(1+k)}{2}\end{align*}
1+2+3+⋯+k=k(1+k)2 . 
Substitute \begin{align*}\frac{k(1+k)}{2}\end{align*}
k(1+k)2 in for \begin{align*}1+2+3+\cdots+k\end{align*}1+2+3+⋯+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 \begin{align*}\frac{k(1+k)}{2}+(k+1)\end{align*}
k(1+k)2+(k+1) .

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

\begin{align*}\frac{k(1 + k)} {2} + (k + 1)\end{align*} k(1+k)2+(k+1) \begin{align*}= \frac{k(k + 1)} {2} + \frac{2(k + 1)} {2}\end{align*} =k(k+1)2+2(k+1)2  The common denominator is 2
 Add the fractions
\begin{align*}= \frac{k(k + 1) + 2(k + 1)} {2}\end{align*} =k(k+1)+2(k+1)2 Simplify the numerator \begin{align*}= \frac{k^2 + k + 2k + 2} {2}\end{align*} =k2+k+2k+22 \begin{align*}= \frac{k^2 + 3k + 2} {2}\end{align*} =k2+3k+22 Factor the numerator \begin{align*}= \frac{(k + 1) (k + 2)} {2} \end{align*} =(k+1)(k+2)2 The term \begin{align*}(k + 2)\end{align*} (k+2) is the same as \begin{align*}((k + 1) + 1)\end{align*}((k+1)+1) \begin{align*}= \frac{(k + 1) ((k + 1) + 1)} {2}\end{align*} =(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 \begin{align*}\frac{n(1 + n)} {2}\end{align*}
Example B
Prove that the sum of the first n terms of an arithmetic series is \begin{align*}S_n = \frac{n(a_1 + a_n)} {2}\end{align*}
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 \begin{align*}a_n = a_1 + d(n  1)\end{align*}
Step 1) Base case: if \begin{align*}n = 1,\end{align*}
 Using the hypothesized formula, we have

\begin{align*}S_1 = \frac{1(a_1 + a_1)} {2} = \frac{2a_1} {2} = a_1\end{align*}
Step 2) Assume that \begin{align*}S_k = \frac{k(a_1 + a_k)} {2}\end{align*}
Step 3) Prove that if our formula for \begin{align*}\,\! S_{k}\end{align*} is true then \begin{align*}S_{k + 1} = \frac{(k +1) (a_1 + a_{k + 1})} {2}\end{align*}.
 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:

\begin{align*}S_{k + 1} = S_k + a_{k + 1}\end{align*} Add the \begin{align*}k + 1\end{align*} term \begin{align*}= \frac{k(a_1 + a_k)} {2} + a_{k + 1}\end{align*} Use the formula for \begin{align*}S_k\end{align*} from step 2 \begin{align*}= \frac{k(a_1 + a_k)} {2} + \frac{2a_{k + 1}} {2}\end{align*} The common denominator is 2 \begin{align*}= \frac{k(a_1 + a_k) + 2a_{k + 1}} {2}\end{align*} Add the fractions \begin{align*}= \frac{k(a_1 + (a_1 + (k  1)d)) + 2(a_1 + kd)} {2}\end{align*} Use substitution: remember that \begin{align*}a_m = a_1 + (m  1)d\end{align*} for any positive integer \begin{align*}m\end{align*}. So \begin{align*}a_k = a_1 + (k  1)d\end{align*} and \begin{align*}a_{k + 1} = a_1 + (k)d\end{align*} \begin{align*}= \frac{k(a_1 + a_1 + kd  d) + 2a_1 + 2kd} {2}\end{align*} \begin{align*}= \frac{ka_1 + ka_1 + k^2d  kd + 2a_1 + 2kd} {2}\end{align*} Distribute and combine like terms \begin{align*}= \frac{2ka_1 + 2a_1 + k^2d + kd} {2}\end{align*} Factor by grouping \begin{align*}= \frac{2a_1(k + 1) + kd(k + 1)} {2}\end{align*} \begin{align*}= \frac{(k + 1) (2a_1 + kd)} {2}\end{align*} \begin{align*}= \frac{(k + 1) (a_1 + a_1 + kd)} {2}\end{align*} Again, \begin{align*}a_{k + 1} = a_1 + (k)d\end{align*} \begin{align*}= \frac{(k + 1) (a_1 + a_{k + 1})} {2}\end{align*}
Example C
Use induction to prove that \begin{align*}1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n + 1) (2n + 1)} {6}\end{align*}
Solution
Step 1) Base case: \begin{align*}1^2 = 1\end{align*}
 \begin{align*}\frac{1(1 + 1) (2(1) + 1)} {6} = \frac{2(3)} {6} = 1\end{align*}
Step 2) Inductive hypothesis: \begin{align*}1^2 + 2^2 + 3^2 + ... + k^2 = \frac{k(k + 1) (2k + 1)} {6}\end{align*}
Step 3) Inductive step: show that
 \begin{align*}1^2 + 2^2 + 3^2 + ... + k^2 + (k + 1)^2 = \frac{(k + 1) (k + 1 + 1) (2(k + 1) + 1)} {6}\end{align*}
 First, note that \begin{align*}\frac{(k + 1) (k + 1 + 1) (2(k + 1) + 1)} {6} = \frac{(k + 1) (k + 2) (2k + 3)} {6}\end{align*}.
 Now we have:

\begin{align*}1^2 + 2^2 + 3^2 + ... + k^2 + (k + 1)^2\end{align*} \begin{align*}= \frac{k(k + 1)(2k + 1)} {6} + (k + 1)^2\end{align*} \begin{align*}= \frac{k(k + 1) (2k + 1) + 6(k + 1)^2} {6} = \frac{(k + 1) \left[k(2k + 1) + 6(k + 1) \right]} {6}\end{align*} \begin{align*}= \frac{(k + 1) \left[2k^2 + k + 6k + 6 \right]} {6} = \frac{(k + 1) \left[2k^2 + 7k + 6 \right]} {6} = \frac{(k + 1) (2k + 3) (k + 2)} {6}\end{align*}
Concept question wrapup Situations like this are custommade 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. 

Vocabulary
Mathematical induction, allows you to prove that a particular statement is true for all positive integers by proving it true for "n", and "n + 1".
A series sum is the total of all of the numbers in a series.
The n^{th} term in a series commonly refers to the last term in a series, often left unspecified.
Guided Practice
Questions
1) Use induction to prove that \begin{align*}1 + 3 + 5 + \cdots + (2n  1) = n^2\end{align*}
2) Use induction to prove that \begin{align*}1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2(n + 1)^2} {4}\end{align*}
3) Use induction to prove that \begin{align*}1 + 4 + 7 + \cdots + (3n2) = \frac{3n^2n}{2}\end{align*}
Solutions
1) Prove that \begin{align*}1 + 3 + 5 + \cdots + (2n  1) = n^2\end{align*}
Step 1) Base case: \begin{align*}1 = 1^2\end{align*}
Step 2) Inductive hypothesis: assume that \begin{align*}1 + 3 + 5+ ... + (2k  1) = k^2\end{align*}
Step 3) Show that \begin{align*}1 + 3 + 5 + ... + (2k  1) + (2k + 1) = (k +1)^2\end{align*}
 We have: \begin{align*}1 + 3 + 5 + ... + (2k  1) + (2k + 1)= k^2 + (2k + 1)\end{align*}

\begin{align*}= k^2 + 2k + 1\end{align*} \begin{align*}= (k + 1) (k + 1) = (k + 1)^2\end{align*}
2) Prove that \begin{align*}1^3 + 2^3 + 3^3 + \cdots + n^3 = \frac{n^2(n + 1)^2} {4}\end{align*}
Step 1) Base case: \begin{align*}1^3 = 1\end{align*}
 \begin{align*}\frac{1^2(1 + 1)^2} {4} = \frac{2^2} {4} = 1\end{align*}
Step 2) Assume that \begin{align*}1^3 + 2^3 + 3^3 + ... + k^3 = \frac{k^2(k + 1)^2} {4}\end{align*}
Step 3) Show that \begin{align*}1^3 + 2^3 + 3^3 + ... + k^3 + (k + 1)^3 = \frac{(k + 1)^2((k + 1) + 1)^2} {4}\end{align*}
 First, note that \begin{align*}\frac{(k + 1)^2((k + 1) + 1)^2} {4} = \frac{(k + 1)^2(k + 2)^2} {4}\end{align*}
 Now we have:

\begin{align*}1^3 + 2^3 + 3^3 + ... + k^3 + (k + 1)^3\end{align*} \begin{align*}= \frac{k^2(k + 1)^2} {4} + (k + 1)^3\end{align*} \begin{align*}= \frac{k^2(k + 1)^2 + 4(k + 1)^3} {4}\end{align*} \begin{align*}= \frac{(k + 1)^2 \left[k^2 + 4(k + 1) \right]} {4} = \frac{(k + 1)^2 \left[k^2 + 4k + 4 \right]} {4} = \frac{(k + 1)^2(x + 2)^2} {4}\end{align*}
3) Prove that \begin{align*}1 + 4 + 7 + \cdots + (3n2) = \frac{3n^2n}{2}\end{align*}
Step 1) Base case: \begin{align*}1 = 1\end{align*}
 \begin{align*}\frac{3(1)^2  1} {2} = \frac{2} {2} = 1\end{align*}
Step 2) Inductive hypothesis: assume that \begin{align*}1 + 4 + 7 + ... + (3k  2) = \frac{3k^2  k} {2}\end{align*}
Step 3) Show that \begin{align*}1 + 4 + 7 + ... + (3(k + 1)  2) = \frac{3(k + 1)^2  (k + 1)} {2}\end{align*}
 First note that:

\begin{align*}1 + 4 + 7 + ... + (3(k + 1)  2) = \frac{3(k + 1)^2  (k + 1)} {2}\end{align*} \begin{align*}= \frac{(k + 1) \left [3(k + 1)  1 \right]} {2}\end{align*} \begin{align*}\frac{(k + 1) \left[3k + 2 \right]} {2}\end{align*}
 Now we have:

\begin{align*}1 + 4 + 7 + ... + (3k  2) + (3(k + 1)  2)\end{align*} \begin{align*}= \frac{3k^2  k} {2} + (3(k + 1)  2)\end{align*} \begin{align*}= \frac{3k^2  k} {2} + (3k + 1)\end{align*} \begin{align*}\frac{3k^2  k + 2(3k + 1)} {2} = \frac{3k^2  k + 6k + 2} {2} = \frac{3k^2 + 5k + 2} {2} = \frac{(3k + 2) (k + 1)} {2}\end{align*}
Practice
Use induction to prove the following:
 \begin{align*}15  25  35 +... 10k  5 = k(5k10)\end{align*}
 \begin{align*}1 + 9 + 9^2 + 9^3 +...+ 9^k = \frac{9^{k+1} 1}{9  1} \end{align*}
 \begin{align*}4 + 8 + 12 +... + 4k = 2k(k +1)\end{align*}
 \begin{align*}6 + 8 + 10 + ... + 2k + 4 = k(k + 5)\end{align*}
 \begin{align*}1 + 2 + 3 + ... + k = \frac{1}{2} k(k + 1)\end{align*}
 \begin{align*}1 + 6 + 6^2 + 6^3 + ...+6^k = \frac{6^{k+1} 1}{6  1}\end{align*}
 \begin{align*} 1  5  9 + ...  4k + 3 = k(2k + 1)\end{align*}
 \begin{align*}1 + 4 + 4^2 + 4^3 + ... + 4^k = \frac{4^{k+1}  1}{4  1}\end{align*}
 \begin{align*}3 + 6 + 9 + ... + 3k = \frac{3}{2} k(k+ 1)\end{align*}
 \begin{align*}1  3  5 + ...  2k + 1 = k(k)\end{align*}
 \begin{align*}1 + 3 + 3^2 + 3^3 + ... + 3^k = \frac{3^{k+1} 1}{3 1}\end{align*}
 \begin{align*}1 + 7 + 7^2 + 7^3 + ... + 7^n = \frac{7^{n + 1}  1}{6}\end{align*}
 \begin{align*}4 + 8 + 12 + ... + 4n = 2n (n + 1)\end{align*}
 \begin{align*}10 + 18 + 26 + ... 8n + 2 = n (4n + 6)\end{align*}
 \begin{align*}6 + 12 + 18 + ... + 6n = 3n (n + 1)\end{align*}
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 .inductive step
In an induction proof, the inductive step is the proof. It is when you show the statement is true for 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.Image Attributions
Description
Learning Objectives
Here you will learn about proof by induction, a process which allows you to attempt to prove a theorem is true for every number if it is true for a single particular number.