7.3: Mathematical Induction
Learning objectives
 Understand the process of mathematical induction.
 Use induction to prove integer sum formulas.
Introduction
In the previous lesson, you found sums of series with different numbers of terms. You probably noticed that adding together many numbers can be tedious, unless you use a calculator. Before people had computers and calculators, they often searched for ways to make calculations easier. For example, logarithms, which you learned about logarithms, were developed to simplify calculations that involve large numbers. Over time, mathematicians have developed formulas that allow us to simplify the calculations of large sums. In fact, German mathematician C.F. Gauss is often credited with discovering such a formula when he was a young child. The story is likely apocryphal (a legend), but it has been passed down since Gauss lived in the 1700’s. According to the story, Gauss’s teacher wanted to occupy students by having them add up large sets of numbers. When Gauss was asked to add up the first 100 integers, he found the sum very quickly, by pairing the numbers:
All of the numbers in the sum could be paired to make groups of 101. There are one hundred numbers being added, so there are such fifty pairs. Therefore the sum is 50(101) = 5050.
The method Gauss used to solve this problem is the basis for a formula that allows us to add together the first n positive integers. However, in order to prove that the formula always works, we need to show that it works for all positive integers. 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 we will present the method, and then we will prove Gauss’s formula, as well another related sum.
The Method of Induction
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 method, 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: you assume that a statement is true for some arbitrary value of n (often it is called k), and then you show that if the statement is true for n=k, it must also be true for n=k+1. We do this precisely 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:
 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.
 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).
 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. In particular, for the third step you must rely on your algebra skills. Next we will prove Gauss’s formula as an example of carrying out induction.
Proof of the sum of the first n integers
Prove: The sum of the first n positive integers is \begin{align*}\frac{n(1 + n)} {2}\end{align*}
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.
2. Assume that the sum of the first \begin{align*}k\end{align*}
3. We must show that the sum of the first \begin{align*}k + 1\end{align*}

\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 . So we can 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*} 


\begin{align*}= \frac{k(k + 1)} {2} + \frac{2(k + 1)} {2}\end{align*} 
The common denominator is 2 Add the fractions 
\begin{align*}= \frac{k(k + 1) + 2(k + 1)} {2}\end{align*} 
Simplify the numerator 
\begin{align*}= \frac{k^2 + k + 2k + 2} {2}\end{align*} 

\begin{align*}= \frac{k^2 + 3k + 2} {2}\end{align*} 
Factor the numerator 
\begin{align*}= \frac{(k + 1) (k + 2)} {2} \end{align*} 
The term \begin{align*}(k + 2)\end{align*} 
\begin{align*}= \frac{(k + 1) ((k + 1) + 1)} {2}\end{align*} 
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*} for all integer values of n. We can similarly prove a formula for the sum of the first n terms in an arithmetic series.
The nth partial sum of an arithmetic series
We can use induction to 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*} , where a_{1} is the first term in the series and a_{n} is the last term.
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*} . We need to keep these ideas in mind in order to complete the proof.
1. Base case: if \begin{align*}n = 1,\end{align*} then \begin{align*}S_1 = a_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*} 

2. Assume that \begin{align*}S_k = \frac{k(a_1 + a_k)} {2}\end{align*}.
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*} 
So we have now proven that the sum of the first n terms in an arithmetic series is \begin{align*}S_n = \frac{n(a_1 + a_n)} {2}\end{align*} . We can use this equation as a formula to find a sum.
Example: Find the sum of the first 50 terms of an arithmetic series if the first term is 5 and the common difference is 3.
Solution:
\begin{align*}S_{50} = \frac{50(a_1 + a_n)} {2} = \frac{50(5 + (5 + 49 \times 3))} {2} = \frac{50(157)} {2} = (25)(127) = 3,175\end{align*}
This method is clearly much easier than writing out and adding 50 numbers!
Summary
In this lesson we have introduced the technique of mathematical induction. This method of proof allows you to prove that a statement is true for all positive integers. In this lesson we have focused on statements involving sums: we proved a formula for the sum of the first n positive integers, and a formula for the sum of the first n terms in an arithmetic series. In the next lesson we will use induction to prove other kinds of statements involving integers.
Points to Consider
1. What is k?
2. How is induction different from other forms of proof?
3. What else can we prove with induction?
Review Questions
 Use Gauss’s formula to find the sum of the first 200 positive integers.
 If the sum of the first n integers is 210, what is n?
 Find the sum of the first 40 terms of an arithmetic series in which the first term is 8 and the common difference is 5.
 The sum of the first 28 terms in an arithmetic series is 1,946. If the first term is 2, what is the hundredth term?
 Consider the series: 13 + 3 + 7 + 17 + 27 + ... a. What is the 25^{th} term? b. What is the sum of the first 25 terms?
 A student needed to find the sum of the first 10 terms of the series 4 + 12 + 36 + ... and so he wrote the following: \begin{align*}S_{10} = \frac{10(4 + 4 \times 3^9)} {2} = \frac{10(78,736)} {2} = 393,680\end{align*} Do you agree with the student’s work? Explain.
 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*}
 Use induction to prove that \begin{align*}1 + 3 + 5 + \cdots + (2n  1) = n^2\end{align*}
 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*}
 Use induction to prove that \begin{align*}1 + 4 + 7 + \cdots + (3n2) = \frac{3n^2n}{2}\end{align*}.
Review Answers
 20,100
 n = 20
 4,220
 137
 a. 227 b. 2,675
 Because the series is geometric, this formula is not appropriate. The work here does not represent the sum of the first 10 terms. Using a graphing calculator, you can find that the sum is 118,096.
 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*} 2. Inductive hypothesis: \begin{align*}1^2 + 2^2 + 3^2 + ... + k^2 = \frac{k(k + 1) (2k + 1)} {6}\end{align*} 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*}  1. Base case: \begin{align*}1 = 1^2\end{align*} 2. Inductive hypothesis: assume that \begin{align*}1 + 3 + 5+ ... + (2k  1) = k^2\end{align*} 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*}  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*} 2. Assume that \begin{align*}1^3 + 2^3 + 3^3 + ... + k^3 = \frac{k^2(k + 1)^2} {4}\end{align*} 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*}  1. Base case: 1 = 1 \begin{align*}\frac{3(1)^2  1} {2} = \frac{2} {2} = 1\end{align*} 2. Inductive hypothesis: assume that \begin{align*}1 + 4 + 7 + ... + (3k  2) = \frac{3k^2  k} {2}\end{align*} 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*}
Vocabulary
 Hypothesis
 A hypothesis is a conclusion made on the basis of evidence, or a statement assumed to be true for the sake of an argument.
 Mathematical Induction
 Mathematical induction is a method of mathematical proof used to establish that a given statement is true of all positive integers (natural numbers).
 Partial sum
 A partial sum is the sum of the first n terms in an infinite series, where n is some positive integer.