4.3: Induction and Recursion

Preview Activity $\PageIndex{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, ..., a_n, ...$

The number $a_n$ is called the $n^{th}$ term of the sequence. One way to define a sequence is to give a specific formula for the $n^{th}$ term of the sequence such as $a_n = \dfrac{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, ..., 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, ..., 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$, and for each $n \in \mathbb{N}$, $b_{n + 1} = \dfrac{1}{2} b_n$.

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

$$\begin{array} bb_2 &= & \dfrac{1}{2} b_1\ \ \ \ \ \ \ \ \ \ \ \ \ b_3 &= & \dfrac{1}{2}b_2 \\ &= & \dfrac{1}{2} \cdot 16 &= & \dfrac{1}{2} \cdot 8 \\ &= & 8 &= & 4 \end{array}$$

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$, and for each $n \in \mathbb{N}$, $T_{n + 1} = 16 + \dfrac{1}{2}T_n$.
   
   Then $T_2 = 16 + \dfrac{1}{2} T_1 = 16 + 8 = 24$. Caluculate $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$, and for each $n \in \mathbb{N}$, $a_{n + 1} = r \cdot a_n$.

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

3. Determine formulas (in terms of $a$ and $r$) for $a_2$ through $a_6$. What do you think an is equal to (in terms of $a$, $r$, and $n$)?
4. Determine formulas (in terms of $a$ and $r$) for $S_2$ through $S_6$. What do you think an is equal to (in terms of $a$, $r$, and $n$)?
   
   In Preview Activity $\PageIndex{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$, ... as follows:
   
   $a_0 = 1$, 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.$$
5. Calculate $a_3$, $a_4$, $a_5$ and $a_6$.
6. Do you think that it is possible to calculate $a_{20}$ and $a_{100}$? Explain.
7. Do you think it is possible to calculate $a_n$ for any natural number $n$? Explain.
8. 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).

Preview Activity $\PageIndex{1}$: The Fibonacci Numbers

The Fibonacci numbers are a sequence of natural numbers $f_1$, $f_2$, $f_3$, ..., $f_n$, ... 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^{th}$ Fibonacci number is the sum of the two previous Fibonacci numbers. So we see that

$$\begin{array} ff_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, \end{array}$$

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.

The Fibonacci Numbers

The Fibonacci numbers form a famous sequence in mathematics that was investigated by Leonardo of Pisa (1170 – 1250), who is better known as Fibonacci. Fibonacci introduced this sequence to the Western world as a solution of the following problem:

Suppose that a pair of adult rabbits (one male, one female) produces a pair of rabbits (one male, one female) each month. Also, suppose that newborn rabbits become adults in two months and produce another pair of rabbits. Starting with one adult pair of rabbits, how many pairs of rabbits will be produced each month for one year?

Since we start with one adult pair, there will be one pair produced the first month, and since there is still only one adult pair, one pair will also be produced in the second month (since the new pair produced in the first month is not yet mature). In the third month, two pairs will be produced, one by the original pair and one by the pair which was produced in the first month. In the fourth month, three pairs will be produced, and in the fifth month, five pairs will be produced.

The basic rule is that in a given month after the first two months, the number of adult pairs is the number of adult pairs one month ago plus the number of pairs born two months ago. This is summarized in Table 4.1, where the number of pairs produced is equal to the number of adult pairs, and the number of adult pairs follows the Fibonacci sequence of numbers that we developed in Preview Activity $\PageIndex{2}$.

Table 4.1: Fibonacci Numbers

Months	1	2	3	4	5	6	7	8	9	10
Adult Pairs	1	1	2	3	5	8	13	21	34	55
Newborn Pairs	1	1	2	3	5	8	13	21	34	55
Month-Old Pairs	0	1	1	2	3	5	8	13	21	34

Historically, it is interesting to note that Indian mathematicians were studying these types of numerical sequences well before Fibonacci. In particular, about fifty years before Fibonacci introduced his sequence, Acharya Hemachandra (1089 – 1173) considered the following problem, which is from the biography of Hemachandra in the MacTutor History of Mathematics Archive:

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 hn 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, .... 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 Preview Activity $\PageIndex{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_{3n} = 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
$P$1	$(\exists m \in \mathbb{N})(f_{3k} = 2m)$	Definition of "even integer"
...	...	...
$Q$1	$(\exists q \in \mathbb{N})(f_{3(k + 1)} = 2q)$
$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_k$?” 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:

$$\begin{array} {rcl} {f_{3(k + 1)}} &= & {f_{3k + 3}} \\ {} &= & {f_{3k + 2} + f_{3k + 1}} \\ {} &= & {(f_{3k + 1} + f_{3k}) + f_{3k + 1}}. \end{array}$$

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.

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.

Answer

Add texts here. Do not delete this text first.

Geometric Sequences and Geometric Series

Let $a,\ r \in \mathbb{R}$. The following sequence was introduced in Preview Activity $\PageIndex{1}$.

$$\begin{array} {rcl} {\text{Initial condition}} &: & {a_1 = a.} \\ {\text{Recurrence relation}} &: & {\text{For each } n \in \mathbb{N}, a_{n + 1} = r \cdot a_n.} \end{array}$$

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 Preview Activity $\PageIndex{1}$ suggests that the following proposition is true.

Theorem 4.14

Let $a,\ r \in \mathbb{R}$, 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}$.

Proof

The proof of this proposition is Exercise (6).

Another sequence that was introduced in Preview Activity $\PageIndex{1}$ is related to geometric series and is defined as follows:

$$\begin{array} {rcl} {\text{Initial condition}} &: & {S_1 = a.} \\ {\text{Recurrence relation}} &: & {\text{For each } n \in \mathbb{N}, S_{n + 1} = r \cdot S_n.} \end{array}$$

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 Preview Activity $\PageIndex{1}$ suggests that the following proposition is true.

Theorem 4.15

Let $a,\ r \in \mathbb{R}$. If the sequence $S_1, S_2, ..., S_n, ...$ 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 + \cdot\cdot\cdot + 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.

Proof

Add proof here and it will automatically be hidden if you have a "AutoNum" template active on the page.

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 nterms of the corresponding geometric sequence. Another way to determine this sum 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 \mathbb{R}$ and $r \ne 1$. If the sequence $S_1, S_2, ..., S_n, ...$ 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(\dfrac{1 - r^n}{1 - r})$.

Proof

The proof of Proposition 4.16 is Exercise (8).

Exercises for Section 4.3

1. For the sequence $a_0, a_1, a_2, ..., a_n, ...$, 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, ..., f_n, ...$ are the Fibonacci numbers. Prove each of the following:
   
   (a) For each $n \in \mathbb{N}$, $f_{4n}$ is a multiple of 3.
   (b) For each $n \in \mathbb{N}$, $f_{5n}$ is a multiple of 5.
   (c) For each $n \in \mathbb{N}$, with $n \ge 2$, $f_1 + f_2 + \cdot\cdot\cdot + f_{n - 1} = f_{n + 1} - 1$.
   (d) For each $n \in \mathbb{N}$, $f_1 + f_3 + \cdot\cdot\cdot + f_{2n - 1} = f_{2n}$.
   (e) For each $n \in \mathbb{N}$, $f_2 + f_4 + \cdot\cdot\cdot + f_{2n} = f_{2n + 1} - 1$.
   (f) For each $n \in \mathbb{N}$, $f_1^2 + f_2^2 + \cdot\cdot\cdot + f_n^2 = f_n f_{n + 1}$.
   (g) For each $n \in \mathbb{N}$ such that $n \not\equiv 0$ (mod 3), $f_n$ is an odd integer.
3. Use the result in Part (f) of Exercise (2) to prove that
   $$\dfrac{f_1^2 + f_2^2 + \cdot\cdot\cdot + f_n^2 + f_{n+1}^2}{f_1^2 + f_2^2 + \cdot\cdot\cdot + f_n^2} = 1 + \dfrac{f_{n + 1}}{f_n}$$
4. The quadratic formula can be used to show that $\alpha = \dfrac{1 + \sqrt 5}{2}$ and $\beta = \dfrac{1 - \sqrt 5}{2}$ are the two real number solutions of the quadratic equation $x^2 - x - 1 = 0$. Notice that this implies that
   $$\begin{array} {rcl} {\alpha ^2} &= & {\alpha + 1,\text{ and}} \\ {\beta ^2} &= & {\beta + 1.} \end{array}$$
   It may be surprising to find out that these two irrational numbers are closely related to the Fibonacci numbers.
   
   (a) Verify that $f_1 = \dfrac{\alpha ^1 - \beta ^1}{\alpha - \beta}$ and that $f_2 = \dfrac{\alpha ^2 - \beta ^2}{\alpha - \beta}$
   (b) (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 = \dfrac{\alpha ^3 - \beta ^3}{\alpha - \beta}$.
   (c) Use induction to prove that for each natural number $n$, if $\alpha = \dfrac{1 + \sqrt 5}{2}$ and $\beta = \dfrac{1 - \sqrt 5}{2}$, then $f_n = \dfrac{\alpha ^n - \beta ^n}{\alpha - \beta}$. Note: This formula for the $n^{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, ..., f_m, ...$ 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 $(f_{n + 1} ^2 + f_{n + 2} ^2)$ form a Pythagorean triple.
6. Prove Proposition 4.14. Let $a,\ r \in \mathbb{R}$, 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 \mathbb{R}$. If the sequence $S_1, S_2, ..., S_n, ...$ 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 + \cdot\cdot\cdot + 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. Prove Proposition 4.16. Let $a,\ r \in \mathbb{R}$ and $r \ne 1$. If the sequence $S_1, S_2, ..., S_n, ...$ 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(\dfrac{1 - r^n}{1 - r})$.
9. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 2$ and that for each $n \in \mathbb{N}$, $a_{n + 1} = a_n + 5$.
   
   (a) Calculate $a_2$ through $a_6$.
   (b) Make a conjecture for a formula for $a_n$ for each $n$ for each $n \in \mathbb{N}$.
   (c) 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, ..., a_n, ...$ by $a_1 = c$ and for each $n \in \mathbb{N}$, $a_{n + 1} = a_n + d$.
    
    (a) Determine formulas for $a_3$ through $a_8$.
    (b) Make a conjecture for a formula for $a_n$ for each $n$ for each $n \in \mathbb{N}$.
    (c) Prove that your conjecture in Exercise (10b) is correct.
11. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 1$, $a_2 = 5$, and that for each $n \in \mathbb{N}$, $a_{n + 1} = a_n + 2a_{n - 1}$. Prove that for each natural number $n$, $a_n = 2^n + (-1)^n$.
12. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 1$ and that for each $n \in \mathbb{N}$, $a_{n + 1} = \sqrt {5 + a_n}$.
    
    (a) Calculate, or approximate, $a_2$ through $a_6$.
    (b) Prove that for each $n \in \mathbb{N}$, $a_n < 3$.
13. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 1$, $a_2 = 3$, and that for each $n \in \mathbb{N}$, $a_{n + 2} = 3a_{n + 1} - 2a_n$.
    
    (a) Calculate $a_3$ through $a_6$.
    (b) Make a conjecture for a formula for $a_n$ for each $n$ for each $n \in \mathbb{N}$.
    (c) Prove that your conjecture in Exercise (13b) is correct.
14. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 1$, $a_2 = 1$, and that for each $n \in \mathbb{N}$, $a_{n + 2} = \dfrac{1}{2} (a_{n + 1} + \dfrac{2}{a_n})$.
    
    (a) Calculate $a_3$ through $a_6$.
    (b) Prove that for each $n \in \mathbb{N}$, $1 \le a_n \le 2$.
15. For the sequence $a_1, a_2, ..., a_n, ...$, 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.$$
    (a) Compute $a_4$, $a_5$, $a_6$, and $a_7$.
    (b) Prove that for each natural number $n$ with $n > 1$, $a_n \le 2^{n - 2}$.
16. For the sequence $a_1, a_2, ..., a_n, ...$, assume that $a_1 = 1$, and for each natural number $n$,
    $$a_{n + 1} = a_n + n \cdot n!.$$
    (a) Compute $n!$ for the first 10 natural numbers.
    (b) Compute $a_n$ for the first 10 natural numbers.
    (c) Make a conjecture about a formula for $a_n$ in terms of $n$ that does not involve a summation or a recursion.
    (d) Prove your conjecture in Part (c).
17. For the sequence $a_1, a_2, ..., a_n, ...$, 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, ..., L_n, ...$, which are defined recursively as follows:
    
    $bullet$ $L_1 = 1$ and $L_2 = 3$, and
    $bullet$ 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.
    
    (a) For each natural number $n$, $L_n = 2f_{n + 1} - f_n$.
    (b) For each $n \in \mathbb{N}$ with $n \ge 2$, $5f_n = L_{n - 1} + L_{n + 1}$.
    (c) For each $n \in \mathbb{N}$ with $n \ge 3$, $L_n = f_{n + 1} - f_{n - 2}$.
19. There is a formula for the Lucas number similar to the formula for the Fibonacci numbers in Exercise (4). Let $\alpha = \dfrac{1 + \sqrt 5}{2}$ and $\beta = \dfrac{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.
    
    (a) For each $n \in \mathbb{N}$, $L_n = \dfrac{f_{2n}}{f_n}$
    (b) For each $n \in \mathbb{N}$, $f_{n + 1} = \dfrac{f_n + L_n}{2}$.
    (c) For each $n \in \mathbb{N}$, $L_{n + 1} = \dfrac{L_n + 5f_n}{2}$.
    (d) 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) on page 100 from Section 3.1.

    (a)

    Let $f_n$ be the $n$th Fibonacci number, and let $\alpha$ be the positive solution of the equation $x^2 = x + 1$. So $\alpha = \dfrac{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)$, ..., $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,

    \[\begin{array} {rcl} {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).} \end{array}\]

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

    $$\begin{array} {rcl} {f_{k + 1}} &\le & {\alpha ^{k - 2} \alpha ^2} \\ {f_{k + 1}} &\le & {\alpha ^k.} \end{array}$$

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

    Explorations and Activities
22. 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 \le 0$, let Vn be the amount of money in an account at the end of the nth compounding period. Then
    $$\begin{array} {rclrcl} {V_1} &= & {R + i \cdot R\ \ \ \ \ \ \ \ \ \ \ } {V_2} &= & {V_1 + i \cdot V_1} \\ {} &= & {R(1 + i)} {} &= & {(1 + i) V_1} \\ {} & & {} {} &= & {(1 + i)^2 R.} \end{array}$$
    
    (a) Explain why $V_3 = V_2 + i \cdot V_2$. Then use the formula for V2 to determine a formula for $V_3$ in terms of $i$ and $R$.
    (b) Determine a recurrence relation for $V_{n + 1}$ in terms of $i$ and $V_n$.
    (c) 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?
    (d) Use Proposition 4.14 to determine a formula for $V_n$ in terms of $I$, $R$, and $n$.
23. 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$$
    
    (a) 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$.
    (b) 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(\dfrac{(1 + i)^n - 1}{i}).$$
    (c) What is the future value of an ordinary annuity in 20 years if $200 dollars is deposited in an account at the end of each month where the interest rate for the account is 6% per year compounded monthly? What is the amount of interest that has accumulated in this account during the 20 years?

Answer

Add texts here. Do not delete this text first.