4 Mathematical Induction

4.3 Induction and Recursion

4.3.1 Beginning Activity 1 (Recursively Defined Sequences)

In a proof by mathematical induction, we "start with a first step" and then prove that we can always go from one step to the next step. We can use this same idea to define a sequence as well. We can think of a sequence as an infinite list of numbers that are indexed by the natural numbers (or some infinite subset of $\mathbb{N}\cup \{0\}$). We often write a sequence in the following form:

$$a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }.$$

The number $a_n$ is called the $n^{\text{th }}$ term of the sequence. One way to define a sequence is to give a specific formula for the $n^{\text{th }}$ term of the sequence such as $a_n=\frac{1}{n}$.

Another way to define a sequence is to give a specific definition of the first term (or the first few terms) and then state, in general terms, how to determine $a_{n+1}$ in terms of $n$ and the first $n$ terms $a_1,a_2,\mathrm{\dots },a_n$. This process is known as definition by recursion and is also called a recursive definition. The specific definition of the first term is called the initial condition, and the general definition of $a_{n+1}$ in terms of $n$ and the first $n$ terms $a_1,a_2,\mathrm{\dots },a_n$ is called the recurrence relation. (When more than one term is defined explicitly, we say that these are the initial conditions.) For example, we can define a sequence recursively as follows:

$$b_1=16,\text{ and for each }n\in \mathbb{N},b_{n+1}=\frac{1}{2}{b}_n.$$

Using $n=1$ and then $n=2$, we then see that

1. Calculate $b_4$ through $b_{10}$. What seems to be happening to the values of $b_n$ as $n$ gets larger?

2. Define a sequence recursively as follows:

   $$T_1=16,\text{ and for each }n\in \mathbb{N},T_{n+1}=16+\frac{1}{2}{T}_n$$

   Then $T_2=16+\frac{1}{2}{T}_1=16+8=24$. Calculate $T_3$ through $T_{10}$. What seems to be happening to the values of $T_n$ as $n$ gets larger?

The sequences in Parts (1) and (2) can be generalized as follows: Let $a$ and $r$ be real numbers. Define two sequences recursively as follows:

$a_1=a,\text{ and for each }n\in \mathbb{N},a_{n+1}=r\cdot a_n.$

$S_1=a,\text{ and for each }n\in \mathbb{N},S_{n+1}=a+r\cdot S_n.$

1. Determine formulas (in terms of $a$ and $r$) for $a_2$ through $a_6$. What do you think $a_n$ is equal to (in terms of $a,r$, and $n$)?

2. Determine formulas (in terms of $a$ and $r$) for $S_2$ through $S_6$. What do you think $S_n$ is equal to (in terms of $a,r$, and $n$)?

In Beginning Activity 1 in Section 4.2, for each natural number $n$, we defined $n!$, read $n$ factorial, as the product of the first $n$ natural numbers. We also defined $0!$ to be equal to 1. Now recursively define a sequence of numbers $a_0,a_1,a_2,\mathrm{\dots }$ as follows:

$$a_0=1,\text{ and }$$

for each nonnegative integer $n,a_{n+1}=(n+1)\cdot a_n$.

Using $n=0$, we see that this implies that $a_1=1\cdot a_0=1\cdot 1=1$. Then using $n=1$, we see that

$$a_2=2a_1=2\cdot 1=2$$

1. Calculate $a_3,a_4,a_5$, and $a_6$.

2. Do you think that it is possible to calculate $a_{20}$ and $a_{100}$? Explain.

3. Do you think it is possible to calculate $a_n$ for any natural number $n$? Explain.

4. Compare the values of $a_0,a_1,a_2,a_3,a_4,a_5$, and $a_6$ with those of $0!,1!,2!,3!,4!,5!$, and $6!$. What do you observe? We will use mathematical induction to prove a result about this sequence in Exercise (1).

4.3.2 Beginning Activity 2 (The Fibonacci Numbers)

The Fibonacci numbers are a sequence of natural numbers $f_1,f_2,f_3,\mathrm{\dots },f_n,\mathrm{\dots }$ defined recursively as follows:

• $f_1=1$ and $f_2=1$, and

• For each natural number $n,f_{n+2}=f_{n+1}+f_n$.

In words, the recursion formula states that for any natural number $n$ with $n\ge 3$, the $n^{\text{th }}$ Fibonacci number is the sum of the two previous Fibonacci numbers. So we see that

$f_3=f_2+f_1=1+1=2,$

$f_4=f_3+f_2=2+1=3,\text{ and}$

$f_5=f_4+f_3=3+2=5.$

1. Calculate $f_6$ through $f_{20}$.

2. Which of the Fibonacci numbers $f_1$ through $f_{20}$ are even? Which are multiples of 3?

3. For $n=2,n=3,n=4$, and $n=5$, how is the sum of the first $(n-1)$ Fibonacci numbers related to the ${(n+1)}^{st}$ Fibonacci number?

4. Record any other observations about the values of the Fibonacci numbers or any patterns that you observe in the sequence of Fibonacci numbers. If necessary, compute more Fibonacci numbers.

Suppose we assume that lines are composed of syllables which are either short or long. Suppose also that each long syllable takes twice as long to articulate as a short syllable. A line of length $n$ contains $n$ units where each short syllable is one unit and each long syllable is two units. Clearly a line of length $n$ units takes the same time to articulate regardless of how it is composed. Hemchandra asks: How many different combinations of short and long syllables are possible in a line of length $n$ ?

This is an important problem in the Sanskrit language since Sanskrit meters are based on duration rather than on accent as in the English Language. The answer to this question generates a sequence similar to the Fibonacci sequence. Suppose that $h_n$ is the number of patterns of syllables of length $n$. We then see that $h_1=1$ and $h_2=2$. Now let $n$ be a natural number and consider pattern of length $n+2$. This pattern either ends in a short syllable or a long syllable. If it ends in a short syllable and this syllable is removed, then there is a pattern of length $n+1$, and there are $h_{n+1}$ such patterns. Similarly, if it ends in a long syllable and this syllable is removed, then there is a pattern of length $n$, and there are $h_n$ such patterns. From this, we conclude that

$$h_{n+2}=h_{n+1}+h_n.$$

This actually generates the sequence $1,2,3,5,8,13,21,\mathrm{\dots }$. For more information about Hemachandra, see the article Math for Poets and Drummers by Rachel Wells Hall in the February 2008 issue of Math Horizons.

We will continue to use the Fibonacci sequence in this book. This sequence may not seem all that important or interesting. However, it turns out that this sequence occurs in nature frequently and has applications in computer science. There is even a scholarly journal, The Fibonacci Quarterly, devoted to the Fibonacci numbers.

The sequence of Fibonacci numbers is one of the most studied sequences in mathematics, due mainly to the many beautiful patterns it contains. Perhaps one observation you made in Beginning Activity 2 is that every third Fibonacci number is even. This can be written as a proposition as follows:

For each natural number $n,f_{3n}$ is an even natural number.

As with many propositions associated with definitions by recursion, we can prove this using mathematical induction. The first step is to define the appropriate open sentence. For this, we can let $P(n)$ be, "$f_{3n}$ is an even natural number."

Notice that $P(1)$ is true since $f_3=2$. We now need to prove the inductive step. To do this, we need to prove that for each $k\in \mathbb{N}$,
if $P(k)$ is true, then $P(k+1)$ is true.
That is, we need to prove that for each $k\in \mathbb{N}$, if $f_{3k}$ is even, then $f_{3(k+1)}$ is even.
So let’s analyze this conditional statement using a know-show table.

Step	Know	Reason
$P$	$f_{3k}$ is even.	Inductive hypothesis
P1	$(\exists m\in \mathbb{N})\left(f_{3k}=2m\right)$	Definition of "even integer"
$\mathrm{⋮}$	$\mathrm{⋮}$	$\mathrm{⋮}$
$Q1$	$(\exists q\in \mathbb{N})\left(f_{3(k+1)}=2q\right)$
$Q$	$f_{3(k+1)}$ is even.	Definition of "even integer"
Step	Show	Reason

The key question now is, "Is there any relation between $f_{3(k+1)}$ and $f_{3k}$ ?" We can use the recursion formula that defines the Fibonacci sequence to find such a relation.

The recurrence relation for the Fibonacci sequence states that a Fibonacci number (except for the first two) is equal to the sum of the two previous Fibonacci numbers. If we write $3(k+1)=3k+3$, then we get $f_{3(k+1)}=f_{3k+3}$. For $f_{3k+3}$, the two previous Fibonacci numbers are $f_{3k+2}$ and $f_{3k+1}$. This means that

$$f_{3k+3}=f_{3k+2}+f_{3k+1}$$

Using this and continuing to use the Fibonacci relation, we obtain the following:

$f_{3(k+1)}$ $=f_{3k+3}$

$=f_{3k+2}+f_{3k+1}$

$=\left(f_{3k+1}+f_{3k}\right)+f_{3k+1}$

The preceding equation states that $f_{3(k+1)}=2f_{3k+1}+f_{3k}$. This equation can be used to complete the proof of the induction step.

4.3.3 Progress Check 4.12 (Every Third Fibonacci Number Is Even)

Complete the proof of Proposition 4.13.
Proposition 4.13. For each natural number $n$, the Fibonacci number $f_{3n}$ is an even natural number.

Hint: We have already defined the predicate $P(n)$ to be used in an induction proof and have proved the basis step. Use the information in and after the preceding know-show table to help prove that if $f_{3k}$ is even, then $f_{3(k+1)}$ is even.

4.3.4 Geometric Sequences and Geometric Series

Let $a,r\in ℝ$. The following sequence was introduced in Beginning Activity 1 .
Initial condition: $a_1=a$.
Recurrence relation: For each $n\in \mathbb{N},a_{n+1}=r\cdot a_n$.
This is a recursive definition for a geometric sequence with initial term $a$ and (common) ratio $r$. The basic idea is that the next term in the sequence is obtained by multiplying the previous term by the ratio $r$. The work in Beginning Activity 1 suggests that the following proposition is true.

Theorem 4.14. Let $a,r\in ℝ$. If a geometric sequence is defined by $a_1=a$ and for each $n\in \mathbb{N},a_{n+1}=r\cdot a_n$, then for each $n\in \mathbb{N},a_n=a\cdot r^{n-1}$.

The proof of this proposition is Exercise (6).
Another sequence that was introduced in Beginning Activity 1 is related to geometric series and is defined as follows:

Initial condition: $S_1=a$.
Recurrence relation: For each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$.
For each $n\in \mathbb{N}$, the term $S_n$ is a (finite) geometric series with initial term $a$ and (common) ratio $r$. The work in Beginning Activity 1 suggests that the following proposition is true.

Theorem 4.15. Let $a,r\in ℝ$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N},S_n=a+a\cdot r+a\cdot r^2+\mathrm{\cdots }+a\cdot r^{n-1}$. That is, the geometric series $S_n$ is the sum of the first $n$ terms of the corresponding geometric sequence.

The proof of Proposition 4.15 is Exercise (7). The recursive definition of a geometric series and Proposition 4.15 give two different ways to look at geometric series. Proposition 4.15 represents a geometric series as the sum of the first $n$ terms of the corresponding geometric sequence. Another way to determine the sum of a geometric series is given in Theorem 4.16, which gives a formula for the sum of a geometric series that does not use a summation.

Theorem 4.16. Let $a,r\in ℝ$ and $r\ne 1$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N}$, $S_n=a\left(\frac{1-r^n}{1-r}\right)$.

The proof of Proposition 4.16 is Exercise (8).

4.3.5 Exercises for Section 4.3

1. $(\star )$ For the sequence $a_0,a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_0=1$ and that for each $n\in \mathbb{N}\cup \{0\},a_{n+1}=(n+1)a_n$. Use mathematical induction to prove that for each $n\in \mathbb{N}\cup \{0\},a_n=n!$.

2. Assume that $f_1,f_2,\mathrm{\dots },f_n,\mathrm{\dots }$ are the Fibonacci numbers. Prove each of the following: $(\star )$

   1. For each $n\in \mathbb{N},f_{4n}$ is a multiple of 3.

   2. For each $n\in \mathbb{N},f_{5n}$ is a multiple of 5. $(\star )$

   3. For each $n\in \mathbb{N}$ with $n\ge 2,f_1+f_2+\mathrm{\cdots }+f_{n-1}=f_{n+1}-1$.

   4. For each $n\in \mathbb{N},f_1+f_3+\mathrm{\cdots }+f_{2n-1}=f_{2n}$.

   5. For each $n\in \mathbb{N},f_2+f_4+\mathrm{\cdots }+f_{2n}=f_{2n+1}-1$.

   6. For each $n\in \mathbb{N},f_1^2+f_2^2+\mathrm{\cdots }+f_n^2=f_n{f}_{n+1}$.

   7. For each $n\in \mathbb{N}$ such that $n\not\equiv 0(mod3),f_n$ is an odd integer.

3. Use the result in Part (f) of Exercise (2) to prove that

   $$\frac{f_1^2+f_2^2+\mathrm{\cdots }+f_n^2+f_{n+1}^2}{f_1^2+f_2^2+\mathrm{\cdots }+f_n^2}=1+\frac{f_{n+1}}{f_n}$$

4. The quadratic formula can be used to show that $\alpha =\frac{1+\sqrt{5}}{2}$ and $\beta =\frac{1-\sqrt{5}}{2}$ are the two real number solutions of the quadratic equation $x^2-x-1=0$. Notice that this implies that

   ${\alpha }^2=\alpha +1,\text{ and}$

   ${\beta }^2=\beta +1$

   It may be surprising to find out that these two irrational numbers are closely related to the Fibonacci numbers.

   1. Verify that $f_1=\frac{{\alpha }^1-{\beta }^1}{\alpha -\beta }$ and that $f_2=\frac{{\alpha }^2-{\beta }^2}{\alpha -\beta }$.

   2. (This part is optional, but it may help with the induction proof in part (c).) Work with the relation $f_3=f_2+f_1$ and substitute the expressions for $f_1$ and $f_2$ from part (a). Rewrite the expression as a single fraction and then in the numerator use ${\alpha }^2+\alpha =\alpha (\alpha +1)$ and a similar equation involving $\beta$. Now prove that $f_3=\frac{{\alpha }^3-{\beta }^3}{\alpha -\beta }$.

   3. Use induction to prove that for each natural number $n$, if $\alpha =\frac{1+\sqrt{5}}{2}$ and $\beta =\frac{1-\sqrt{5}}{2}$, then $f_n=\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta }$. Note: This formula for the $n^{\text{th }}$ Fibonacci number is known as Binet’s formula, named after the French mathematician Jacques Binet (1786-1856).

5. Is the following conjecture true or false? Justify your conclusion.

   Conjecture. Let $f_1,f_2,\mathrm{\dots },f_m,\mathrm{\dots }$ be the sequence of the Fibonacci numbers. For each natural number $n$, the numbers $f_n{f}_{n+3},2f_{n+1}{f}_{n+2}$, and $\left(f_{n+1}^2+f_{n+2}^2\right)$ form a Pythagorean triple.

6. $(\star )$ Prove Theorem 4.14. Let $a,r\in ℝ$. If a geometric sequence is defined by $a_1=a$ and for each $n\in \mathbb{N},a_{n+1}=r\cdot a_n$, then for each $n\in \mathbb{N}$, $a_n=a\cdot r^{n-1}$.

7. Prove Proposition 4.15. Let $a,r\in ℝ$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N},S_n=a+a\cdot r+a\cdot r^2+\mathrm{\cdots }+a\cdot r^{n-1}$. That is, the geometric series $S_n$ is the sum of the first $n$ terms of the corresponding geometric sequence.

8. $(\star )$ Prove Proposition 4.16. Let $a,r\in ℝ$ and $r\ne 1$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N},S_n=a\left(\frac{1-r^n}{1-r}\right)$.

9. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=2$ and that for each $n\in \mathbb{N},a_{n+1}=a_n+5$.

   1. Calculate $a_2$ through $a_6$. $(\star )$

   2. Make a conjecture for a formula for $a_n$ for each $n\in \mathbb{N}$.

   3. Prove that your conjecture in Exercise (9b) is correct.

10. The sequence in Exercise (9) is an example of an arithmetic sequence. An arithmetic sequence is defined recursively as follows: Let $c$ and $d$ be real numbers. Define the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$ by $a_1=c$ and for each $n\in \mathbb{N},a_{n+1}=a_n+d$.

    1. Determine formulas for $a_3$ through $a_8$.

    2. Make a conjecture for a formula for $a_n$ for each $n\in \mathbb{N}$.

    3. Prove that your conjecture in Exercise (10b) is correct.

11. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1,a_2=5$, and that for each $n\in \mathbb{N}$ with $n\ge 2,a_{n+1}=a_n+2a_{n-1}$. Prove that for each natural number $n,a_n=2^n+{(-1)}^n$.

12. $(\star )$ For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1$ and that for each $n\in \mathbb{N},a_{n+1}=\sqrt{5+a_n}$.

    1. Calculate, or approximate, $a_2$ through $a_6$.

    2. Prove that for each .

13. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1,a_2=3$, and that for each $n\in \mathbb{N},a_{n+2}=3a_{n+1}-2a_n$. $(\star )$

    1. Calculate $a_3$ through $a_6$. $(\star )$

    2. Make a conjecture for a formula for $a_n$ for each $n\in \mathbb{N}$.

    3. Prove that your conjecture in Exercise (13b) is correct.

14. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1,a_2=1$, and that for each $n\in \mathbb{N},a_{n+2}=\frac{1}{2}\left(a_{n+1}+\frac{2}{a_n}\right)$. $(\star )$

    1. Calculate $a_3$ through $a_6$.

    2. Prove that for each $n\in \mathbb{N},1\le a_n\le 2$.

15. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1,a_2=1,a_3=1$, and for that each natural number $n$,

    $$a_{n+3}=a_{n+2}+a_{n+1}+a_n$$

    1. Compute $a_4,a_5,a_6$, and $a_7$.

    2. Prove that for each natural number $n$ with $n>1,a_n\le 2^{n-2}$.

16. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1$, and that for each natural number $n$,

    $$a_{n+1}=a_n+(n+1)\cdot (n+1)!.$$

    1. Compute $n!$ for the first 10 natural numbers.

    2. $(\star )$ Compute $a_n$ for the first 10 natural numbers.

    3. Make a conjecture about a formula for $a_n$ in terms of $n$ that does not involve a summation or a recursion.

    4. Prove your conjecture in Part (c).

17. For the sequence $a_1,a_2,\mathrm{\dots },a_n,\mathrm{\dots }$, assume that $a_1=1,a_2=1$, and for each $n\in \mathbb{N},a_{n+2}=a_{n+1}+3a_n$. Determine which terms in this sequence are divisible by 4 and prove that your answer is correct.

18. The Lucas numbers are a sequence of natural numbers $L_1,L_2,L_3,\mathrm{\dots },L_n,\mathrm{\dots }$, which are defined recursively as follows:

    • $L_1=1$ and $L_2=3$, and

    • For each natural number $n,L_{n+2}=L_{n+1}+L_n$.

    List the first 10 Lucas numbers and the first ten Fibonacci numbers and then prove each of the following propositions. The Second Principle of Mathematical Induction may be needed to prove some of these propositions.

    1. For each natural number $n,L_n=2f_{n+1}-f_n$.

    2. For each $n\in \mathbb{N}$ with $n\ge 2,5f_n=L_{n-1}+L_{n+1}$.

    3. For each $n\in \mathbb{N}$ with $n\ge 3,L_n=f_{n+2}-f_{n-2}$.

19. There is a formula for the Lucas numbers similar to the formula for the Fibonacci numbers in Exercise (4). Let $\alpha =\frac{1+\sqrt{5}}{2}$ and $\beta =\frac{1-\sqrt{5}}{2}$. Prove that for each $n\in \mathbb{N},L_n={\alpha }^n+{\beta }^n$.

20. Use the result in Exercise (19), previously proven results from Exercise (18), or mathematical induction to prove each of the following results about Lucas numbers and Fibonacci numbers.

    1. For each $n\in \mathbb{N},L_n=\frac{f_{2n}}{f_n}$.

    2. For each $n\in \mathbb{N},f_{n+1}=\frac{f_n+L_n}{2}$.

    3. For each $n\in \mathbb{N},L_{n+1}=\frac{L_n+5f_n}{2}$.

    4. For each $n\in \mathbb{N}$ with $n\ge 2,L_n=f_{n+1}+f_{n-1}$.

21. Evaluation of proofs. See the instructions for Exercise (19) from Section 3.1. Proposition. Let $f_n$ be the $n^{\text{th }}$ Fibonacci number, and let $\alpha$ be the positive solution of the equation $x^2=x+1$. So $\alpha =\frac{1+\sqrt{5}}{2}$. For each natural number $n,f_n\le {\alpha }^{n-1}$.

    Proof. We will use a proof by mathematical induction. For each natural number $n$, we let $P(n)$ be, "$f_n\le {\alpha }^{n-1}$."

    We first note that $P(1)$ is true since $f_1=1$ and ${\alpha }^0=1$. We also notice that $P(2)$ is true since $f_2=1$ and, hence, $f_2\le {\alpha }^1$.

    We now let $k$ be a natural number with $k\ge 2$ and assume that $P(1),P(2)$, $\mathrm{\dots },P(k)$ are all true. We now need to prove that $P(k+1)$ is true or that $f_{k+1}\le {\alpha }^k$.

    Since $P(k-1)$ and $P(k)$ are true, we know that $f_{k-1}\le {\alpha }^{k-2}$ and $f_k\le {\alpha }^{k-1}$. Therefore,

    $f_{k+1}=f_k+f_{k-1}$

    $f_{k+1}\le {\alpha }^{k-1}+{\alpha }^{k-2}$

    $f_{k+1}\le {\alpha }^{k-2}(\alpha +1)$

    We now use the fact that $\alpha +1={\alpha }^2$ and the preceding inequality to obtain

    $f_{k+1}$ $\le {\alpha }^{k-2}{\alpha }^2$

    $f_{k+1}$ $\le {\alpha }^k$

    This proves that if $P(1),P(2),\mathrm{\dots },P(k)$ are true, then $P(k+1)$ is true. Hence, by the Second Principle of Mathematical Induction, we conclude that for each natural number $n,f_n\le {\alpha }^{n-1}$.

4.3.6 Explorations and Activities

1. Compound Interest. Assume that $R$ dollars is deposited in an account that has an interest rate of $i$ for each compounding period. A compounding period is some specified time period such as a month or a year.

   For each integer $n$ with $n\ge 0$, let $V_n$ be the amount of money in an account at the end of the $n$th compounding period. Then

   1. Explain why $V_3=V_2+i\cdot V_2$. Then use the formula for $V_2$ to determine a formula for $V_3$ in terms of $i$ and $R$.

   2. Determine a recurrence relation for $V_{n+1}$ in terms of $i$ and $V_n$.

   3. Write the recurrence relation in Part (22b) so that it is in the form of a recurrence relation for a geometric sequence. What is the initial term of the geometric sequence and what is the common ratio?

   4. Use Proposition 4.14 to determine a formula for $V_n$ in terms of $I,R$, and $n$.

2. The Future Value of an Ordinary Annuity. For an ordinary annuity, $R$ dollars is deposited in an account at the end of each compounding period. It is assumed that the interest rate, $i$, per compounding period for the account remains constant.

   Let $S_t$ represent the amount in the account at the end of the $t$ th compounding period. $S_t$ is frequently called the future value of the ordinary annuity.

   So $S_1=R$. To determine the amount after two months, we first note that the amount after one month will gain interest and grow to $(1+i)S_1$. In addition, a new deposit of $R$ dollars will be made at the end of the second month. So

   $$S_2=R+(1+i)S_1$$

   1. For each $n\in \mathbb{N}$, use a similar argument to determine a recurrence relation for $S_{n+1}$ in terms of $R,i$, and $S_n$.

   2. By recognizing this as a recursion formula for a geometric series, use Proposition 4.16 to determine a formula for $S_n$ in terms of $R,i$, and $n$ that does not use a summation. Then show that this formula can be written as

      $$S_n=R\left(\frac{{(1+i)}^n-1}{i}\right)$$

   3. What is the future value of an ordinary annuity in 20 years if $\mathrm{\$}200$ dollars is deposited in an account at the end of each month with an interest rate of $6\%$ per year compounded monthly? What is the amount of interest that has accumulated in this account during the 20 years?

4.4 Chapter 4 Summary

4.4.1 Important Definitions

• Inductive set, Section 4.1

• Factorial, Section 4.2

• Recursive definition, Section 4.2

• Fibonacci numbers, Section 4.2

• Geometric sequence, Section 4.2

• Geometric series, Section 4.2

4.4.2 The Various Forms of Mathematical Induction

1. The Principle of Mathematical Induction If $T$ is a subset of $\mathbb{N}$ such that

   1. $1\in T$, and

   2. For every $k\in \mathbb{N}$, if $k\in T$, then $(k+1)\in T$,

   then $T=\mathbb{N}$.

   Procedure for a Proof by Mathematical Induction

   To prove $(\forall n\in \mathbb{N})(P(n))$
   Basis step: Prove $P(1)$.

   Inductive step: Prove that for each $k\in \mathbb{N}$, if $P(k)$ is true, then $P(k+1)$ is true.

2. The Extended Principle of Mathematical Induction Let $M$ be an integer. If $T$ is a subset of $\mathbb{Z}$ such that

   1. $M\in T$, and

   2. For every $k\in \mathbb{Z}$ with $k\ge M$, if $k\in T$, then $(k+1)\in T$,

   then $T$ contains all integers greater than or equal to $M$.

   Using the Extended Principle of Mathematical Induction

   Let $M$ be an integer. To prove $(\forall n\in \mathbb{Z}$ with $n\ge M)(P(n))$
   Basis step: Prove $P(M)$.

   Inductive step: Prove that for every $k\in \mathbb{Z}$ with $k\ge M$, if $P(k)$ is true, then $P(k+1)$ is true.
   We can then conclude that $P(n)$ is true for all $n\in \mathbb{Z}$ with $n\ge M$.

3. The Second Principle of Mathematical Induction

   Let $M$ be an integer. If $T$ is a subset of $\mathbb{Z}$ such that

   1. $M\in T$, and

   2. For every $k\in \mathbb{Z}$ with $k\ge M$, if $\{M,M+1,\mathrm{\dots },k\}\subseteq T$, then $(k+1)\in T$,

   then $T$ contains all integers greater than or equal to $M$.

   Using the Second Principle of Mathematical Induction

   Let $M$ be an integer. To prove $(\forall n\in \mathbb{Z}$ with $n\ge M)(P(n))$
   Basis step: Prove $P(M)$.

   Inductive step: Let $k\in \mathbb{Z}$ with $k\ge M$. Prove that if $P(M),P(M+1),\mathrm{\dots },P(k)$ are true, then $P(k+1)$ is true.

   We can then conclude that $P(n)$ is true for all $n\in \mathbb{Z}$ with $n\ge M$.

4.4.3 Important Results

• Theorem 4.9. Each natural number greater than 1 either is a prime number or is a product of prime numbers.

• Theorem 4.14. Let $a,r\in ℝ$. If a geometric sequence is defined by $a_1=a$ and for each $n\in \mathbb{N},a_{n+1}=r\cdot a_n$, then for each $n\in \mathbb{N},a_n=a\cdot r^{n-1}$.

• Theorem 4.15. Let $a,r\in ℝ$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N}$, $S_n=a+a\cdot r+a\cdot r^2+\mathrm{\cdots }+a\cdot r^{n-1}$. That is, the geometric series $S_n$ is the sum of the first $n$ terms of the corresponding geometric sequence.

• Theorem 4.16. Let $a,r\in ℝ$ and $r\ne 1$. If the sequence $S_1,S_2,\mathrm{\dots },S_n,\mathrm{\dots }$ is defined by $S_1=a$ and for each $n\in \mathbb{N},S_{n+1}=a+r\cdot S_n$, then for each $n\in \mathbb{N},S_n=a\left(\frac{1-r^n}{1-r}\right)$.