Skip to main content

Section 8.2 Mathematical Induction

In this section, we introduce mathematical induction, a powerful proof technique used throughout mathematics and theoretical computer science to prove a statement \(P(n)\) that depends on an integer \(n\text{.}\) For example, it is used in computer science to verify loop invariants. We practice using mathematical induction to prove some of our conjectures about explicit rules for recursively-defined sequences from Section 8.1.

Subsection 8.2.A Proof Format: Mathematical Induction

Mathematical induction is used to prove a statement \(P(n)\) for all values of the integer \(n \ge s\) for some nonnegative integer \(s\text{.}\) That is, to prove the infinite list of statements \(P(s)\text{,}\) \(P(s+1)\text{,}\) \(P(s+2)\text{,}\) …. A proof by mathematical induction takes an inventive approach.

Definition 8.2.1 Proof by mathematical induction.

A proof by mathematical induction that a statement \(P(n)\) is true for all integers \(n \ge s\text{,}\) where \(s\) is a nonnegative integer, consists of two parts.
  1. First, we prove the base case: \(P(s)\text{.}\)
  2. Next, we prove the inductive step: for any integer \(n\text{,}\) if \(n > s\) and \(P(n-1)\text{,}\) then \(P(n)\text{.}\)
  3. To prove the inductive step, we assume \(P(n-1)\) for some integer \(n > s\) and prove \(P(n)\) using a direct proof of the conditional Theorem 5.3.13. The assumption of \(P(n-1)\) is the inductive hypothesis.
Here is the official proof format.
The phrase “induct on \(n\)” alerts the reader that we are using proof by mathematical induction. The key words in the proof are “First” (indicates the base case), “Assume” (indicates the inductive hypothesis), “for Some” (indicates the existential quantifier), and “Then” (indicates the end of the inductive step). A mnemonic is that a proof by mathematical induction is FAST.
Why does this proof format work? The result of the inductive step is \(P(n-1) \to P(n)\) whenever \(n > s\text{.}\) That is, if we know that \(P(n-1)\) is true for some integer \(n >s\text{,}\) then we can conclude that \(P(n)\) is true. Since we have proved \(P(s)\) in the base case, we can apply the result of the inductive step with \(n=s+1\) to get \(P(s) \to P(s+1)\text{,}\) from which it follows that \(P(s+1)\text{.}\) Officially we are using the logical inference modus ponens from Section 5.5. Then, since we know \(P(s+1)\text{,}\) we can apply the result of the inductive step with \(n=s+2\) to get \(P(s+1) \to P(s+2)\) from which it follows that \(P(s+2)\text{.}\) And so on.
Try reading a proof by mathematical induction.

Activity 8.2.A Divisibility proof by mathematical induction.

 
  1. Copy the following proof. Use mathematical induction to prove that \(4 \mid (5^n-1)\) for all integers \(n \ge 1\)

    Proof.
    First, when \(n=1\) we have \(5^1-1=4\) so \(4 \mid (5^1-1)\text{.}\)
    Next, assume \(4 \mid (5^{n-1}-1)\) for some integer \(n > 1\text{.}\) By the definition of divides, we can write
    \begin{equation*} 5^{n-1}-1=4k \end{equation*}
    for some integer \(k\text{.}\) Adding one to each side of the equation we get
    \begin{equation*} 5^{n-1}=4k+1\text{.} \end{equation*}
    Then
    \begin{equation*} 5^n-1=5\cdot5^{n-1}-1 = 5(4k+1)-1 \end{equation*}
    \begin{equation*} = 20k + 5 -1= 20k+4 = 4(5k+1) \end{equation*}
    and so \(4 \mid (5^n-1)\text{.}\)
  2. In the proof you copied, \(P(n)\) was the statement \(4 \mid (5^n-1)\text{.}\) What what the inductive hypothesis \(P(n-1)\text{?}\) Hint: Look after the word “assume”.
  3. Explain the algebra step-by-step in the last line of the proof.
Let’s look at more examples.

Example 8.2.4 Number of bit strings.

 
  1. In Theorem 2.4.8, we proved that for \(n \ge 0\) there are \(2^n\) bit strings of length \(n\text{.}\) Use mathematical induction to prove that there are \(2^n\) bit strings of length \(n\text{.}\)
    Solution.
    Proof Induct on \(n\text{.}\) First, when \(n=0\text{,}\) there is exactly one bit string of length zero, namely \(\lambda\text{,}\) the empty bit string. Since \(2^0=1\text{,}\) it follows that there are \(2^0\) bit strings of length zero.
    Next, assume there are \(2^{n-1}\) bit strings of length \(n-1\) for some integer \(n > 0\text{.}\) Let \(b\) be a bit string of length \(n\text{.}\) Since the length of \(b\) is at least 1, we can consider two cases.
    Case 1: \(b\) starts with \(\bs{0}\text{.}\) Then \(b=\bs{0}b_0\) where \(b_0\) is a bit string of length \(n-1\text{.}\) By the inductive hypothesis, there are \(2^{n-1}\) choices for the bit string \(b_0\text{.}\) Therefore, there are \(2^{n-1}\) choices for the bit string \(b\) in this case.
    Case 2: \(b\) starts with \(\bs{1}\text{.}\) Then \(b=\bs{1}b_1\) where \(b_1\) is a bit string of length \(n-1\text{.}\) By the inductive hypothesis, there are \(2^{n-1}\) choices for the bit string \(b_1\text{.}\) Therefore, there are also \(2^{n-1}\) choices for the bit string \(b\) in this case.
    Then, since cases add Theorem 2.2.7, there are
    \begin{equation*} 2^{n-1}+2^{n-1}=2\cdot2^{n-1}=2^n \end{equation*}
    bit strings of length \(n\text{.}\)
  2. What was the inductive hypothesis?
    Solution.
    The inductive hypothesis was that there are \(2^{n-1}\) bit strings of length \(n-1\) for some integer \(n > 0\text{.}\)
  3. Explain step-by-step why the algebra in the final equation is correct.
    Solution.
    For any number \(x\) we have \(x+x=x(1+1)=2x\text{.}\) In particular,
    \begin{equation*} 2^{n-1}+2^{n-1}=2\cdot2^{n-1}\text{.} \end{equation*}
    Next, \(2\cdot2^{n-1}= 2 \cdot \underbrace{2 \times 2 \times \cdots \times 2}_{(n-1) \text{ times } }= \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ times } }=2^n\text{.}\)
We conclude with an example of a proof by mathematical induction about trees. We use the fact that any tree with at least two vertices contains at least one leaf (degree one vertex).

Example 8.2.5 Tree with \(n\) vertices has exactly \(n-1\) edges.

Use mathematical induction to prove that a tree with \(n\) vertices has exactly \(n-1\) edges.
Solution.
Proof Induct on \(n\text{.}\)
First, when \(n=1\) the only tree is a single vertex which has zero edges, and \(1-1=0\text{.}\)
Next, assume that any tree with \((n-1)\) vertices has exactly \((n-1)-1 = n-2\) edges for some integer \(n \ge 2\text{.}\) Let \(T\) be a tree with \(n\) vertices. Since every tree with at least two vertices has at least one leaf, there exists a vertex \(v\) in \(T\) such that \(\fn{deg}(v)=1\text{.}\)
Consider the graph \(T'\) formed by removing \(v\) and the one edge ending at \(v\) from \(T\text{.}\) Since \(T\) was a tree, it does not contain any cycles so neither does \(T'\text{.}\) Since \(T\) is connected, any two vertices in \(T\) are connected by a path in \(T\text{.}\) Since \(\fn{deg}(v)=1\text{,}\) there is no path that includes \(v\) in the middle (because that would mean \(\fn{deg}(v)\ge2\)). Therefore any two vertices other than \(v\) are connected by a path in \(T\) that does not include \(v\) and so \(T'\) is still connected. Last, \(T'\) has \((n-1)\) vertices because we removed one vertex.
By our inductive hypothesis, it follows that \(T'\) has exactly \((n-2)\) edges. Since we only removed one edge from \(T\text{,}\) it follows that \(T\) has exactly \((n-2)+1=n-1\) edges.

Subsection 8.2.B Algebra: Evaluating \(f(n-1)\)

Proofs by mathematical induction can involve a lot of algebra. It would be a good moment to review: Subsection 2.1.D, Subsection 2.2.C, Subsection 2.4.D, Subsection 4.1.D, and Subsection 4.2.B.
Specifically, within proofs of mathematical induction, we often want to evaluate and simplify \(f(n-1)\) where \(f\) is a function and \(n\) is an integer. Let’s see a few examples.

Example 8.2.6 Evaluating \(f(n-1)\).

In each part, evaluate \(f(n-1)\) and simplify your answer.
  1. Consider the function \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=2^{n+1}-1\text{.}\)
    Solution.
    It may be helpful to think of
    \begin{equation*} f(\Box) = 2^{(\Box)+1} -1\text{.} \end{equation*}
    To calculate \(f(n-1)\text{,}\) we replace \(n\) in the original formula (or \(\Box\) in this new version) with \((n-1)\) in parentheses to get
    \begin{equation*} f(n-1) = 2^{(n-1)+1}-1=2^n-1\text{.} \end{equation*}
  2. Consider the function \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=n^2-n\text{.}\)
    Solution.
    It may be helpful to think of
    \begin{equation*} f(\Box) = (\Box)^2-(\Box)\text{.} \end{equation*}
    To calculate \(f(n-1)\text{,}\) we replace each occurrence of \(n\) in the original formula (or \(\Box\) in this new format) by \((n-1)\) in parentheses to get
    \begin{equation*} f(n-1) = (n-1)^2-(n-1) = n^2-2n+1-n+1=n^2-3n+2 \end{equation*}
Your turn to practice.

Activity 8.2.B Evaluating \(f(n-1)\).

In each part, evaluate \(f(n-1)\) and simplify your answer.
  1. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=3n+1\text{.}\)
  2. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=n(n+1)\text{.}\)
  3. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=3 \cdot 10^n\text{.}\)
  4. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(\displaystyle f(n)=a \left(\frac{r^{n+1}-1}{r-1}\right)\text{,}\) for constants \(a\) and \(r\text{.}\)

Subsection 8.2.C Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence

One special case where proof by mathematical induction is used is to prove an explicit rule for a recursively-defined sequence. We state this special case as its own proof format.
Note that in the base case we prove \(a_s=f(s)\text{.}\) The inductive hypothesis is \(a_{n-1}=f(n-1)\) for some integer \(n > s\text{.}\) In the inductive step, we prove \(a_n=f(n)\text{.}\) As usual, here is an example of the proof format for you to copy and edit.

Activity 8.2.C Use mathematical induction to prove the explicit form of a recursively-defined sequence.

 
  1. Copy the following proof. Consider the sequence \(a\) defined recursively by \(a_0= 1\) and \(a_n = 2a_{n-1}\) for \(n \ge 1\text{.}\) Prove that \(a_n=2^n\) for \(n \ge 0\text{.}\)

    Proof.
    Write \(f(n) = 2^n\text{.}\) Induct on \(n\text{.}\)
    First, when \(n=0\) we know that \(a_0 = 1\) and also \(f(0) = 2^0 = 1\text{.}\)
    Next, assume \(a_{n-1} = f(n-1)= 2^{n-1}\) for some integer \(n \ge 0\text{.}\)
    Then \(a_n = 2a_{n-1} = 2 \cdot 2^{n-1} = 2^n = f(n)\) \(\Box\)
  2. Edit the proof to prove if the sequence \(b\) is defined recursively by \(b_0=10\) and \(b_n = 3b_{n-1}\) for \(n \ge 1\text{,}\) then \(b_n=10\cdot3^n\) for \(n \ge 0\text{.}\)
  3. The sequence \(u\) is defined by \(u_0= 10\) and \(u_n = u_{n-1}^2\) for \(n \ge 1\text{.}\) Use mathematical induction to prove \(u_n = 10^{2^n}\) for \(n \ge 0\text{.}\) Be careful: \(10^{2^n}\) means \(10^{(2^n)}\text{.}\)

Subsection 8.2.D Exercises

Subsubsection Exercises for 8.2.A Proof Format: Mathematical Induction

1. Practice.

Use mathematical induction to prove that \(3 \mid (4^n-1)\) for all integers \(n \ge 1\text{.}\)
Check.
Hint: Copy and edit the proof from Activity 8.2.A.

2. Understand.

Use mathematical induction to prove every integer is either even or odd. Use that \(n=(n-1)+1\) and the inductive hypothesis to break into two cases: \(n-1\) is even or \(n-1\) is odd.

3. Understand.

Consider the function \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n) = \frac{n(n-1)}{2}\text{.}\)
  1. Evaluate and simplify \(f(1)\text{.}\)
  2. Evaluate and simplify \(f(n-1)\text{.}\) Leave the numerator in factored form.
  3. Copy the following outline of a proof by mathematical induction that the complete graph \(K_n\) has \(f(n)\) edges for \(n \ge 1\) and fill in the missing details.
    Proof.
    First, when \(n=1\text{,}\) the graph \(K_1\) is one vertex which has 0 edges and \(f(1)=\underline{\hspace{1in}}\text{.}\) Thus, \(K_1\) has \(f(1)\) edges.
    Next, assume \(\underline{\hspace{1in}}\) for some integer \(n > 1\text{.}\)
    Then, the graph \(K_n\) can be built from \(K_{n-1}\) by adding one more vertex, \(v\text{,}\) and adding an edge from \(v\) to each of the vertices of \(K_{n-1}\text{.}\) Notice that we are adding \(n-1\) new edges. Thus, the number of edges in \(K_n\) equals the number of edges in \(K_{n-1}\) and \(n-1\) new edges. That is, the number of edges of \(K_n\) is
    \begin{equation*} f(n-1) + (n-1) = \underline{\hspace{.25in} \text{ (show algebra) } \hspace{.25in}} = f(n) \end{equation*}
Check.
  1. Hint: \(1-1=0\)
  2. \(\displaystyle \frac{(n-1)(n-2)}{2}\)
  3. Hint for the first blank: Fill in the answer to 3.(a). Hint for the second blank: \(P(n)\) is “The graph \(K_n\) has \(f(n)\) edges.” Fill in the blank with \(P(n-1)\text{.}\) Hint for the third blank: First, use your answer to 3.(b), then write \(n-1 = \frac{2(n-1)}{2}\) so the fractions have a common denominator, and then add the fractions.

4. Understand.

Use mathematical induction to prove that there are \(2^n\) subsets of the set \(\{1,2,3,\ldots,n\}\text{.}\) Hint: Look at Example 8.2.4. In the inductive step, break the count into two cases based on whether the subset contains \(n\text{.}\) If the subset \(S\) does not contain \(n\text{,}\) then \(S \subseteq \{1,2,3, \ldots, n-1\}\text{.}\) If the subset \(S\) contains \(n\text{,}\) then remove \(n\) from the subset to get \(S - \{n\} \subseteq \{1,2,3, \ldots, n-1\}\text{.}\)

5. Recap.

Do you know …
  1. When we might use a proof by mathematical induction?
  2. Why proof by mathematical induction works (logically)?
  3. Why we need the base case?
  4. What we prove in the base case of a proof by mathematical induction?
  5. What the inductive hypothesis is in a proof by mathematical induction?
  6. What we prove in the inductive step of a proof by mathematical induction?

6. Explore.

Use mathematical induction to prove that there are \(n!\) permutations of the set \(\{1,2,3,\ldots,n\}\text{.}\) Recall that a permutation of the set \(\{1,2,3,\ldots,n\}\) is an \(n\)-tuple that uses each of \(1,2,3,\ldots,n\) exactly once. Hint: Given a permutation \(p\) of \(\{1,2,3,\ldots,n\}\) we can remove \(n\) to get a permutation \(p_0\) of \(\{1,2,3,\ldots,n-1\}\text{.}\) There are \((n-1)!\) such resulting permutations and there are \(n\) choices for the position where \(n\) appeared in \(p\text{:}\) directly before the 1, directly before the 2, directly before the 3, …, directly before the \(n-1\text{,}\) or at the very end. Use that steps multiply Theorem 2.2.3.

Subsubsection Exercises for 8.2.B Algebra: Evaluating \(f(n-1)\)

7. Practice.

In each part, evaluate \(f(n-1)\) and simplify your answer.
  1. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(\displaystyle f(n)=\frac{2n}{n+1}\text{.}\)
  2. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(\displaystyle f(n)=\frac{n}{2n+1}\text{.}\)
  3. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(\displaystyle f(n)=\frac{n(n+1)}{2}\text{.}\) Leave the answer in factored form.
Check.
The answers, in some order, are \(\frac{n-1}{2n-1}\text{,}\) \(\frac{n(n-1)}{2}\text{,}\) and \(\frac{2n-2}{n}\text{.}\)

8. Practice.

In each part, evaluate \(f(n-1)\) and simplify your answer.
  1. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=(-1)^n\text{.}\)
  2. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=2\cdot3^{n+1}-1\text{.}\)
  3. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n) =10^{2^n}\)
Check.
  1. Hint: If you evaluate your answer at \(n=3\text{,}\) you should get 7. If you did not get that, check that you calculated \((n-1)^2=(n-1)(n-1)\) correctly.
  2. Hint: One factor is \(2n-1\text{.}\) If you did not get that, check that you entered \((n-1)\) in parentheses.
  3. Hint: It does not simplify much.

9. Practice.

In each part, evaluate \(f(n-1)\) and simplify your answer.
  1. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=n^2+n+1\text{.}\)
  2. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=n(n+1)(2n+1)\text{.}\) Leave your answer factored.
  3. \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(n)=(n+1)!-1\text{.}\)

10. Understand.

Simplify each expression.
  1. \(\displaystyle (2(n-1)+1)+2\)
  2. \(\displaystyle 2\cdot (2^n-1)+1\)
  3. \(\displaystyle n(n-1)!\)

11. Understand.

Simplify each expression. To add the fractions, write over the common denominator 2.
  1. \(\displaystyle \displaystyle 3\left( \frac{3^n-1}{2} \right) + 1\)
  2. \(\displaystyle \displaystyle \frac{(n-1)n}{2} +n\)
Check.
  1. Hint: Your answer should be one fraction with denominator 2. It should involve \(3^{n+1}\text{.}\)
  2. Hint: \(n = \frac{2n}{2}\)

12. Recap.

Do you know …
  1. How to evaluate \(f(n-1)\) for a function \(f\) and why we might need parentheses?
  2. How to simplify \(2\cdot2^{n-1}\) and other related exponential expressions?
  3. How to simplify \(n(n-1)!\) and other related expressions involving factorials?

Subsubsection Exercises for 8.2.C Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence

13. Practice.

The sequence \(a\) is defined by \(a_0= 3\) and \(a_n = 10a_{n-1}\) for \(n \ge 1\text{.}\) Use mathematical induction to prove \(a_n = 3\cdot 10^n\) for \(n \ge 0\text{.}\)
Check.
Hint: Copy and edit the proof from Activity 8.2.C.

14. Practice.

The sequence \(b\) is defined by \(b_0= 1\) and \(b_n = b_{n-1} + 3\) for \(n \ge 1\text{.}\) Use mathematical induction to prove \(b_n = 3n+1\) for \(n \ge 0\text{.}\)
Check.
Hint: Copy and edit the proof from Activity 8.2.C. When you evaluate \(f(n-1)\text{,}\) make sure \((n-1)\) is in parentheses.

15. Practice.

The sequence \(t\) is defined by \(t_0= 5\) and \(t_k = -t_{k-1}\) for \(k \ge 1\text{.}\) Use mathematical induction to prove \(t_k = (-1)^k5\) for \(k \ge 0\text{.}\)

16. Practice.

The sequence \(c\) is defined by \(c_0=1\) and \(c_k = 2c_{k-1}+3\) for \(n \ge 1\text{.}\) Use mathematical induction to prove \(c_k = 2^{k+2}-3\) for \(k \ge 0\text{.}\) We saw this sequence in Example 8.1.5.
Check.
Hint: Notice that we are using \(k\) instead of \(n\text{.}\) Some useful algebra facts are \(2\cdot 2^{k+1}=2^{k+2}\) and \(2(-3)=-6\text{.}\)

17. Understand.

The sequence \(s\) is defined by \(s_0=0\) and \(s_m = 5s_{m-1}+1\) for \(m \ge 1\text{.}\) Use mathematical induction to prove \(s_m = \frac{5^m-1}{4}\) for \(m \ge 0\)
Check.
Hint: Notice that we are using \(m\) instead of \(n\text{.}\) Some useful algebra facts are \(5(5^m-1) = 5^{m+1}-5\) and \(1 = \frac{4}{4}\text{.}\)

18. Understand.

The sequence \(u_n\) is defined by \(u_1= 1\) and \(u_n = u_{n-1}+n\) for \(n \ge 2\text{.}\) Use mathematical induction to prove \(u_n = \frac{n(n+1)}{2}\) for \(n \ge 1\text{.}\)
Check.
Hint: Some useful algebraic facts are \((n-1)n = n^2-n\text{,}\) \(n = \frac{2n}{2}\text{,}\) and \(n^2+n=n(n+1)\text{.}\)

19. Understand.

The sequence \(v_n\) is defined by \(v_1= 1\) and \(v_n = nv_{n-1}\) for \(n \ge 2\text{.}\) Use mathematical induction to prove \(v_n = n!\) for \(n \ge 1\text{.}\)
Check.
Hint: \(7\cdot 6! = (7)(6)(5)(4)(3)(2)(1)=7!\) Use this idea to simplify \(n(n-1)!\)

20. Understand.

The sequence \(x_n\) is defined by \(x_0=1\) and \(x_n = x_{n-1}+2n\) for \(n\ge 1\text{.}\) Use mathematical induction to prove \(x_n =n^2 + n + 1\) for \(n \ge 0\)
Check.
Hint: Make sure you have correctly simplified \((n-1)^2=(n-1)(n-1)\text{.}\)

21. Recap.

Do you know …
  1. How to use mathematical induction to prove an explicit rule for a recursively-defined sequence?
  2. What the base case is in such proofs?
  3. What the inductive hypothesis is in such proofs?
  4. Which is used first in the final line — the recursion or the inductive hypothesis?

22. Explore.

We deposit \(10,000\) into a bank account that earns 3% interest annually. Write \(a_n=\) the account balance at the end of \(n\) years. We saw in Exercise 21 21.(a) that \(a_0=10,000\) and \(a_n=1.03a_{n-1}\) for \(n \ge 1\text{.}\) Let’s generalize. If we deposit \(p\) into a bank account that earns \(r\) interest annually, where \(r\) is the percentage written as a decimal, then \(a_0=p\) and \(a_n=(1+r)a_{n-1}\) for \(n \ge 1\text{.}\) Use mathematical induction to prove \(a_n=p(1+r)^n\) for \(n \ge 0\text{.}\)

23. Explore.

We deposit \(10,000\) into a bank account that earns 3% interest annually but then we deposit another \(10,000\) at the end of each year (just after interest is paid). Write \(b_n=\) the account balance at the end of \(n\) years. We saw in Exercise 21 21.(b) that \(b_0=10,000\) and \(b_n = 1.03b_{n-1}+ 10,000\text{.}\) Let’s generalize. If we deposit \(p\) into a bank account that earns \(r\) interest annually, where \(r\) is the percentage written as a decimal, but then we deposit another \(p\) at the end of each year (just after interest is paid), then \(b_0=p\) and \(b_n = (1+r)b_{n-1}+ p\text{.}\) Use mathematical induction to prove that \(b_n = p \displaystyle \left(\frac{(1+r)^{n+1}-1}{r}\right)\) for \(n \ge 0\text{.}\)
PrevTopNext