Induction and Recursion

Section 4.3 Induction and Recursion

Beginning Activity Beginning Activity 1: Recursively Defined Sequences
A4 US

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

N \cup {0}

). We often write a sequence in the following form:

a_{1}, a_{2}, \dots, a_{n}, \dots .

🔗

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} = \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}, \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}, \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,$ and for each $n \in N,$ $b_{n + 1} = \frac{1}{2} b_{n} .$

🔗

Using

n = 1

and then

n = 2,

we then see that

\begin{aligned} b_{2} & = \frac{1}{2} b_{1} & b_{3} & = \frac{1}{2} b_{2} \\ = \frac{1}{2} \cdot 16 & = \frac{1}{2} \cdot 8 \\ = 8 & = 4 \end{aligned}

🔗

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 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}

n

gets larger?

🔗

The sequences in Exercise 1 and Exercise 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 N,$ $a_{n + 1} = r \cdot a_{n} .$

$S_{1} = a,$ and for each $n \in 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 $a_{n}$ 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 $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}, \dots

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} = 2 a_{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.

🔗

Beginning Activity Beginning Activity 2: The Fibonacci Numbers
A4 US

🔗

The Fibonacci numbers are a sequence of natural numbers

f_{1}, f_{2}, f_{3}, \dots, f_{n}, \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 \geq 3,

the

n^{t h}

Fibonacci number is the sum of the two previous Fibonacci numbers. So we see that

\begin{aligned} f_{3} & = f_{2} + f_{1} = 1 + 1 = 2, \\ f_{4} & = f_{3} + f_{2} = 2 + 1 = 3, and \\ f_{5} & = f_{4} + f_{3} = 3 + 2 = 5 . \end{aligned}

🔗

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)^{s t}$ 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.

🔗

Subsection 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.14, 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 Beginning Activity 2.

🔗

Table 4.14. 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 (sometimes spelled Hemchandra) (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

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, …. 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_{3 n} 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_{3 n}

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 N,

if $P (k)$ is true, then $P (k + 1)$ is true.

That is, we need to prove that for each

k \in N,

f_{3 k}

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_{3 k}$ is even.	Inductive hypothesis
$P 1$	$(\exists m \in N) (f_{3 k} = 2 m)$	Definition of “even integer”
$⋮$	$⋮$	$⋮$
$Q 1$	$(\exists q \in N) (f_{3 (k + 1)} = 2 q)$
$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_{3 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) = 3 k + 3,

then we get

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

For

f_{3 k + 3},

the two previous Fibonacci numbers are

f_{3 k + 2}

and

f_{3 k + 1} .

This means that

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

🔗

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

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

🔗

The preceding equation states that

f_{3 (k + 1)} = 2 f_{3 k + 1} + f_{3 k} .

This equation can be used to complete the proof of the induction step.

🔗

Progress Check 4.15. Every Third Fibonacci Number Is Even.

Complete the proof of Proposition 4.16.

🔗

Proposition 4.16.

For each natural number $n,$ the Fibonacci number $f_{3 n}$ 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_{3 k}$ is even, then $f_{3 (k + 1)}$ is even.

Solution.

🔗

Proof.

We will use a proof by induction. For each natural number $n,$ we let $P (n)$ be, $f_{3 n}$ is an even natural number.

Since $f_{3} = 2,$ we see that $P (1)$ is true and this proves the basis step.

For the inductive step, we let $k$ be a natural number and assume that $P (k)$ is true. That is, assume that $f_{3 k}$ is an even natural number. This means that there exists an integer $m$ such that

\begin{matrix} (35) & f_{3 k} = 2 m . \end{matrix}

We need to prove that $P (k + 1)$ is true or that $f_{3 (k + 1)}$ is even. Notice that $3 (k + 1) = 3 k + 3$ and, hence, $f_{3 (k + 1)} = f_{3 k + 3} .$ We can now use the recursion formula for the Fibonacci numbers to conclude that

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

Using the recursion formula again, we get $f_{3 k + 2} = f_{3 k + 1} + f_{3 k} .$ Putting this all together, we see that

\begin{aligned} f_{3 (k + 1)} & = f_{3 k + 3} \\ = f_{3 k + 2} + f_{3 k + 1} \\ = (f_{3 k + 1} + f_{3 k}) + f_{3 k + 1} \\ (36) & = 2 f_{3 k + 1} + f_{3 k} \end{aligned}

We now substitute the expression for $f_{3 k}$ in equation (35) into equation (36). This gives

\begin{aligned} f_{3 (k + 1)} & = 2 f_{3 k + 1} + 2 m \\ f_{3 (k + 1)} & = 2 (f_{3 k + 1} + m) \end{aligned}

This preceding equation shows that $f_{3 (k + 1)}$ is even. Hence it has been proved that if $P (k)$ is true, then $P (k + 1)$ is true and the inductive step has been established. By the Principle of Mathematical Induction, this proves that for each natural number $n,$ the Fibonacci number $f_{3 n}$ is an even natural number.

🔗

Subsection Geometric Sequences and Geometric Series

🔗

Let

a, r \in R .

The following sequence was introduced in Beginning Activity 1.

\begin{aligned} Initial condition: & a_{1} = a \\ Recurrence relation: & For each n \in N, a_{n + 1} = r \cdot a_{n} . \end{aligned}

🔗

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.17.

Let $a, r \in R .$ If a geometric sequence is defined by $a_{1} = a$ and for each $n \in N,$ $a_{n + 1} = r \cdot a_{n},$ then for each $n \in 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:

\begin{aligned} Initial condition: & S_{1} = a \\ Recurrence relation: & For each n \in N, S_{n + 1} = a + r \cdot S_{n} . \end{aligned}

🔗

For each

n \in 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.18.

Let $a, r \in R .$ If the sequence $S_{1}, S_{2}, \dots, S_{n}, \dots$ is defined by $S_{1} = a$ and for each $n \in N,$ $S_{n + 1} = a + r \cdot S_{n},$ then for each $n \in N,$ $S_{n} = a + a \cdot r + a \cdot r^{2} + \dots + 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 Theorem 4.18 is Exercise 7. The recursive definition of a geometric series and Theorem 4.18 give two different ways to look at geometric series. Theorem 4.18 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.19, which gives a formula for the sum of a geometric series that does not use a summation.

🔗

Theorem 4.19.

Let $a, r \in R$ and $r \neq 1 .$ If the sequence $S_{1}, S_{2}, \dots, S_{n}, \dots$ is defined by $S_{1} = a$ and for each $n \in N,$ $S_{n + 1} = a + r \cdot S_{n},$ then for each $n \in N,$ $S_{n} = a (\frac{1 - r^{n}}{1 - r}) .$

🔗

The proof of Theorem 4.19 is Exercise 8.

🔗

Exercises Exercises

🔗

1.

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

Answer.

Let $P (n)$ be $a_{n} = n! .$ Since $a_{0} = 1$ and $0! = 1,$ we see that $P (0)$ is true. For the inductive step, we assume that $k \in N \cup {0}$ and that $P (k)$ is true or that $a_{k} = k! .$

\begin{aligned} a_{k + 1} & = (k + 1) a_{k} \\ = (k + 1) k! \\ = (k + 1)! . \end{aligned}

This proves the inductive step that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

2.

Assume that $f_{1}, f_{2}, \dots, f_{n}, \dots$ are the Fibonacci numbers. Prove each of the following:

🔗

(a)

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

Answer.

Let $P (n)$ be, “ $f_{4 n}$ is a multiple of 3.” Since $f_{4} = 3,$ $P (1)$ is true. If $P (k)$ is true, then there exists an integer $m$ such that $f_{4 k} = 3 m .$ We now need to prove that $P (k + 1)$ is true or that $f_{4 (k + 1)}$ is a multiple of 3. We use the following:

\begin{aligned} f_{4 (k + 1)} & = f_{4 k + 4} \\ = f_{4 k + 3} + f_{4 k + 2} \\ = (f_{4 k + 2} + f_{4 k + 1}) + (f_{4 k + 1} + f_{4 k}) \\ = f_{4 k + 2} + 2 f_{4 k + 1} + f_{4 k} \\ = (f_{4 k + 1} + f_{4 k}) + 2 f_{4 k + 1} + f_{4 k} \\ = 3 f_{4 k + 1} + 2 f_{4 k} \end{aligned}

We now use the assumption that $f_{4 k} = 3 m$ and the last equation to obtain $f_{4 (k + 1)} = 3 f_{4 k + 1} + 2 \cdot 3 m$ and hence, $f_{4 (k + 1)} = 3 (f_{4 k + 1} + 2 m) .$ Therefore, $f_{4 (k + 1)}$ is a multiple of 3 and this completes the proof of the inductive step.

🔗

(b)

For each $n \in N,$ $f_{5 n}$ is a multiple of 5.

🔗

(c)

For each $n \in N$ with $n \geq 2,$ $f_{1} + f_{2} + \dots + f_{n - 1} = f_{n + 1} - 1 .$

Answer.

Let $P (n)$ be, “ $f_{1} + f_{2} + \dots + f_{n - 1} = f_{n + 1} - 1 .$ ” Since $f_{1} = f_{3} - 1,$ $P (2)$ is true. For $k \geq 2,$ if $P (k)$ is true, then $f_{1} + f_{2} + \dots + f_{k - 1} = f_{k + 1} - 1 .$ Then

\begin{aligned} (f_{1} + f_{2} + \dots + f_{k - 1}) + f_{k} & = (f_{k + 1} - 1) + f_{k} \\ = (f_{k + 1} + f_{k}) - 1 \\ = f_{k + 2} - 1 . \end{aligned}

This proves that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

(d)

For each $n \in N,$ $f_{1} + f_{3} + \dots + f_{2 n - 1} = f_{2 n} .$

🔗

(e)

For each $n \in N,$ $f_{2} + f_{4} + \dots + f_{2 n} = f_{2 n + 1} - 1 .$

🔗

(f)

For each $n \in N,$ $f_{1}^{2} + f_{2}^{2} + \dots + f_{n}^{2} = f_{n} f_{n + 1} .$

Answer.

Let $P (n)$ be, “ $f_{1}^{2} + f_{2}^{2} + \dots + f_{n}^{2} = f_{n} f_{n + 1} .$ ” For the basis step, we notice that $f_{1}^{2} = 1$ and $f_{1} \cdot f_{2} = 1$ and hence, $P (1)$ is true. For the inductive step, we need to prove that if $P (k)$ is true, then $P (k + 1)$ is true. That is, we need to prove that if $f_{1}^{2} + f_{2}^{2} + \dots + f_{k}^{2} = f_{k} f_{k + 1},$ then $f_{1}^{2} + f_{2}^{2} + \dots + f_{k}^{2} + f_{k + 1}^{2} = f_{k + 1} f_{k + 2} .$ To do this, we can use

\begin{aligned} (f_{1}^{2} + f_{2}^{2} + \dots + f_{k}^{2}) + f_{k + 1}^{2} & = f_{k} f_{k + 1} + f_{k + 1}^{2} \\ f_{1}^{2} + f_{2}^{2} + \dots + f_{k}^{2} + f_{k + 1}^{2} & = f_{k + 1} (f_{k} + f_{k + 1}) \\ = f_{k + 1} f_{k + 2} . \end{aligned}

🔗

(g)

For each $n \in N$ such that $n ≢ 0 (\mod 3),$ $f_{n}$ is an odd integer.

🔗

3.

Use the result in Task 2.f of Exercise 2 to prove that

\frac{f_{1}^{2} + f_{2}^{2} + \dots + f_{n}^{2} + f_{n + 1}^{2}}{f_{1}^{2} + f_{2}^{2} + \dots + f_{n}^{2}} = 1 + \frac{f_{n + 1}}{f_{n}} .

🔗

4.

The quadratic formula can be used to show that $α = \frac{1 + \sqrt{5}}{2}$ and $β = \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

\begin{aligned} α^{2} & = α + 1, and \\ β^{2} & = β + 1 . \end{aligned}

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

🔗

(a)

Verify that $f_{1} = \frac{α^{1} - β^{1}}{α - β}$ and that $f_{2} = \frac{α^{2} - β^{2}}{α - β} .$

🔗

(b)

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

🔗

(c)

Use induction to prove that for each natural number $n,$ if $α = \frac{1 + \sqrt{5}}{2}$ and $β = \frac{1 - \sqrt{5}}{2},$ then $f_{n} = \frac{α^{n} - β^{n}}{α - β} .$

This formula for the $n^{t h}$ 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?

🔗

Conjecture 4.20.

Let $f_{1}, f_{2}, \dots, f_{m}, \dots$ be the sequence of the Fibonacci numbers. For each natural number $n,$ the numbers $f_{n} f_{n + 3},$ $2 f_{n + 1} f_{n + 2},$ and $(f_{n + 1}^{2} + f_{n + 2}^{2})$ form a Pythagorean triple.

🔗

6.

Prove Theorem 4.17. Let $a, r \in R .$ If a geometric sequence is defined by $a_{1} = a$ and for each $n \in N,$ $a_{n + 1} = r \cdot a_{n},$ then for each $n \in N,$ $a_{n} = a \cdot r^{n - 1} .$

Answer.

For the inductive step, if $a_{k} = a \cdot r^{k - 1},$ then

\begin{aligned} a_{k + 1} & = r \cdot a_{k} \\ = r (a \cdot r^{k - 1}) \\ = a \cdot r^{k} . \end{aligned}

🔗

7.

Prove Theorem 4.18. Let $a, r \in R .$ If the sequence $S_{1}, S_{2}, \dots, S_{n}, \dots$ is defined by $S_{1} = a$ and for each $n \in N,$ $S_{n + 1} = a + r \cdot S_{n},$ then for each $n \in N,$ $S_{n} = a + a \cdot r + a \cdot r^{2} + \dots + 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 Theorem 4.19. Let $a, r \in R$ and $r \neq 1 .$ If the sequence $S_{1}, S_{2}, \dots, S_{n}, \dots$ is defined by $S_{1} = a$ and for each $n \in N,$ $S_{n + 1} = a + r \cdot S_{n},$ then for each $n \in N,$ $S_{n} = a (\frac{1 - r^{n}}{1 - r}) .$

Answer.

For the inductive step, use the assumption that $S_{k} = a (\frac{1 - r^{k}}{1 - r})$ and the recursive definiton to write $S_{k + 1} = a + r \cdot S_{k} .$

🔗

9.

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

🔗

(a)

Calculate $a_{2}$ through $a_{6} .$

Answer.

$a_{2} = 7,$ $a_{3} = 12,$ $a_{4} = 17,$ $a_{5} = 22,$ $a_{6} = 27 .$

🔗

(b)

Make a conjecture for a formula for $a_{n}$ for each $n \in N .$

Answer.

One possibility is: For each $n \in N,$ $a_{n} = 2 + 5 (n - 1) .$

🔗

(c)

Prove that your conjecture in Task 9.b 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}, \dots, a_{n}, \dots$ by $a_{1} = c$ and for each $n \in 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 \in N .$

🔗

(c)

Prove that your conjecture in Task 10.b is correct.

🔗

11.

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

🔗

12.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \dots$ , assume that $a_{1} = 1$ and that for each $n \in N,$ $a_{n + 1} = \sqrt{5 + a_{n}} .$

🔗

(a)

Calculate, or approximate, $a_{2}$ through $a_{6} .$

Answer.

$a_{2} = \sqrt{6},$ $a_{3} = \sqrt{\sqrt{6} + 5} \approx 2.729,$ $a_{4} \approx 2.780,$ $a_{5} \approx 2.789,$ $a_{6} \approx 2.791$

🔗

(b)

Prove that for each $n \in N,$ $a_{n} < 3 .$

Answer.

Let $P (n)$ be, “ $a_{n} < 3 .$ ” Since $a_{1} = 1,$ $P (1)$ is true. For $k \in N,$ if $P (k)$ is true, then $a_{k} < 3 .$ Now

a_{k + 1} = \sqrt{5 + a_{k}} .

Since $a_{k} < 3,$ this implies that $a_{k + 1} < \sqrt{8}$ and hence, $a_{k + 1} < 3 .$ This proves that if $P (k)$ is true, then $P (k + 1)$ is true.

🔗

13.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \dots$ , assume that $a_{1} = 1,$ $a_{2} = 3,$ and that for each $n \in N,$ $a_{n + 2} = 3 a_{n + 1} - 2 a_{n} .$

🔗

(a)

Calculate $a_{3}$ through $a_{6} .$

Answer.

$a_{3} = 7,$ $a_{4} = 15,$ $a_{5} = 31,$ $a_{6} = 63$

🔗

(b)

Make a conjecture for a formula for $a_{n}$ for each $n \in N .$

Hint.

Think in terms of powers of 2.

🔗

(c)

Prove that your conjecture in Task 13.b is correct.

🔗

14.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \dots$ , assume that $a_{1} = 1,$ $a_{2} = 1,$ and that for each $n \in N,$ $a_{n + 2} = \frac{1}{2} (a_{n + 1} + \frac{2}{a_{n}}) .$

🔗

(a)

Calculate $a_{3}$ through $a_{6} .$

Answer.

$a_{3} = \frac{3}{2},$ $a_{4} = \frac{7}{4},$ $a_{5} = \frac{37}{24},$ $a_{6} = \frac{451}{336}$

🔗

(b)

Prove that for each $n \in N,$ $1 \leq a_{n} \leq 2 .$

🔗

15.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \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} .

🔗

(a)

Compute $a_{4},$ $a_{5},$ $a_{6},$ and $a_{7} .$

🔗

(b)

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

🔗

16.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \dots,$ assume that $a_{1} = 1,$ and that 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.

Answer.

\begin{aligned} a_{2} & = 5 & a_{5} & = 719 & a_{8} & = 362879 \\ a_{3} & = 23 & a_{6} & = 5039 & a_{9} & = 3628799 \\ a_{4} & = 119 & a_{7} & = 40319 & a_{10} & = 39916799 \end{aligned}

🔗

(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 Task 16.c.

🔗

17.

For the sequence $a_{1}, a_{2}, \dots, a_{n}, \dots$ , assume that $a_{1} = 1,$ $a_{2} = 1,$ and for each $n \in N,$ $a_{n + 2} = a_{n + 1} + 3 a_{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}, \dots, L_{n}, \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.

🔗

(a)

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

Answer.

Let $P (n)$ be, “ $L_{n} = 2 f_{n + 1} - f_{n} .$ ” First, verify that $P (1)$ and $P (2)$ are true. Now let $k$ be a natural number with $k \geq 2$ and assume that $P (1),$ $P (2),$ …, $P (k)$ are all true. Since $P (k)$ and $P (k - 1)$ are both assumed to be true, we can use them to help prove that $P (k + 1)$ must then be true as follows:

\begin{aligned} L_{k + 1} & = L_{k} + L_{k - 1} \\ = (2 f_{k + 1} - f_{k}) + (2 f_{k} - f_{k - 1}) \\ = 2 (f_{k + 1} + f_{k}) - (f_{k} + f_{k - 1}) \\ = 2 f_{k + 2} - f_{k + 1} . \end{aligned}

🔗

(b)

For each $n \in N$ with $n \geq 2,$ $5 f_{n} = L_{n - 1} + L_{n + 1} .$

🔗

(c)

For each $n \in N$ with $n \geq 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 $α = \frac{1 + \sqrt{5}}{2}$ and $β = \frac{1 - \sqrt{5}}{2} .$ Prove that for each $n \in N,$ $L_{n} = α^{n} + β^{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 N,$ $L_{n} = \frac{f_{2 n}}{f_{n}} .$

🔗

(b)

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

🔗

(c)

For each $n \in N,$ $L_{n + 1} = \frac{L_{n} + 5 f_{n}}{2} .$

🔗

(d)

For each $n \in N$ with $n \geq 2,$ $L_{n} = f_{n + 1} + f_{n - 1} .$

🔗

21. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

🔗

(a)

Proposition

Let $f_{n}$ be the $n^{th}$ Fibonacci number, and let $α$ be the positive solution of the equation $x^{2} = x + 1 .$ So $α = \frac{1 + \sqrt{5}}{2} .$ For each natural number $n,$ $f_{n} \leq α^{n - 1} .$

Proof

We will use a proof by mathematical induction. For each natural number $n,$ we let $P (n)$ be, “ $f_{n} \leq α^{n - 1} .$ ”

We first note that $P (1)$ is true since $f_{1} = 1$ and $α^{0} = 1 .$ We also notice that $P (2)$ is true since $f_{2} = 1$ and, hence, $f_{2} \leq α^{1} .$

We now let $k$ be a natural number with $k \geq 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} \leq α^{k} .$

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

\begin{aligned} f_{k + 1} & = f_{k} + f_{k - 1} \\ f_{k + 1} & \leq α^{k - 1} + α^{k - 2} \\ f_{k + 1} & \leq α^{k - 2} (α + 1) . \end{aligned}

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

\begin{aligned} f_{k + 1} & \leq α^{k - 2} α^{2} \\ f_{k + 1} & \leq α^{k} \end{aligned}

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 for each natural number $n,$ $f_{n} \leq α^{n - 1} .$

🔗

Activity 25. 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 \geq 0,$ let $V_{n}$ be the amount of money in an account at the end of the $n$ th compounding period. Then

\begin{aligned} 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{aligned}

🔗

(a)

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 .$

🔗

(b)

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

🔗

(c)

Write the recurrence relation in Task 25.b 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 Theorem 4.17 to determine a formula for $V_{n}$ in terms of $I,$ $R,$ and $n .$

🔗

Activity 26. 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 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 Theorem 4.19 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 (\frac{{(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?

mathshistory.st-andrews.ac.uk/Biographies/Hemchandra

Section 4.3 Induction and Recursion

Beginning Activity Beginning Activity 1: Recursively Defined Sequences A4US

1.

2.

3.

4.

5.

6.

7.

8.

Beginning Activity Beginning Activity 2: The Fibonacci Numbers A4US

1.

2.

3.

4.

Subsection The Fibonacci Numbers

Progress Check 4.15. Every Third Fibonacci Number Is Even.

Proposition 4.16.

Proof.

Subsection Geometric Sequences and Geometric Series

Theorem 4.17.

Theorem 4.18.

Theorem 4.19.

Exercises Exercises

1.

2.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

3.

4.

(a)

(b)

(c)

5.

Conjecture 4.20.

6.

7.

8.

9.

(a)

(b)

(c)

10.

(a)

(b)

(c)

11.

12.

(a)

(b)

13.

(a)

(b)

(c)

14.

(a)

(b)

15.

(a)

(b)

16.

(a)

(b)

(c)

(d)

17.

18.

(a)

(b)

(c)

19.

20.

(a)

(b)

(c)

Beginning Activity Beginning Activity 1: Recursively Defined Sequences
A4 US

Beginning Activity Beginning Activity 2: The Fibonacci Numbers
A4 US