Solving Recurrence Relations by Iteration

Section 5.6 Solving Recurrence Relations by Iteration

Given a sequence defined recursively, we want to be able to find an explicit formula for the sequence. In general, this can be difficult and can involve very sophisticated mathematical tools. We will learn one method, the method of iteration, just to get a taste for the ideas.

🔗

To find an explicit formula for a recursive sequence using the methods of iteration:

🔗

Calculate several terms of the sequence, often without simplifying the terms.
See a pattern.
Guess an explicit formula for the pattern. Keep in mind your formula should just depend on $n .$
Prove your explicit formula using induction.

🔗

Example 5.6.1. Finding an Explicit Formula.

Find the first five terms of the sequence given by

a_{k} = a_{k - 1} + 3, k \geq 1,

a_{0} = 4 .

Answer.

a_{0} = 4, a_{1} = 7, a_{2} = 10, a_{3} = 13, a_{4} = 16

It might be difficult to see a pattern, so we will calculate the terms without simplifying at all.

\begin{aligned} a_{0} & = 4 \\ a_{1} & = 4 + 3 \\ a_{2} & = (4 + 3) + 3 \\ a_{3} & = ((4 + 3) + 3) + 3 \\ a_{4} & = (((4 + 3) + 3) + 3) + 3 \end{aligned}

Now it should be easier to see a pattern. It seems we have

a_{n} = 4 + 3 n,

which is an explicit formula.

To prove this is the correct formula, we would assume

a_{k} = a_{k - 1} + 3

and prove

a_{n} = 4 + 3 n

by induction.

Proof.

Let

a_{k} = a_{k - 1} + 3, a_{0} = 4 .

Prove

a_{n} = 4 + 3 n, n \geq 0

Base Step: Let

n = 0 .

Then

a_{n} = a_{0} = 4 .

And

4 + 3 n = 4 + 3 (0) = 4 .

Thus,

a_{n} = 4 + 3 n

for

n = 0 .

Induction Step: Assume

a_{k} = 4 + 3 k

for some

k \geq 0 .

Show

a_{k + 1} = 4 + 3 (k + 1) .

Proof of induction step: By the recursive definition of the sequence,

a_{k + 1} = a_{k} + 3 .

Thus,

\begin{aligned} a_{k + 1} & = a_{k} + 3 \\ = 4 + 3 k + 3 by induction assumption \\ = 4 + 3 (k + 1) \end{aligned}

Therefore, by induction,

a_{n} = 4 + 3 n, n \geq 0 .

Definition 5.6.2.

An arithmetic sequence is given recursively by

🔗

a_{k} = a_{k - 1} + d

where

d

is constant.

🔗

Activity 5.6.1.

Generalize Example 5.6.1 to find an explicit formula for an arithmetic sequence.

🔗

(a)

Let

d = 5, a_{0} = 2 .

Write out the first 6 terms of the arithmetic sequence. Can you find an explicit formula for the sequence (one that just depends on

n

🔗

(b)

Write out the first 6 terms of the sequence without simplifying at all. Now can you find an explicit formula?

🔗

(c)

Using the same technique of writing out the terms without simplifying, find an explicit formula for the general form,

a_{k} = a_{k - 1} + d,

of an arithmetic sequence.

🔗

Definition 5.6.3.

A geometric sequence is given recursively by

🔗

a_{k} = r a_{k - 1}

where

r

is constant.

🔗

Activity 5.6.2.

Use the method of iteration to find an explicit formula for a geometric sequence.

🔗

(a)

Let

r = 2, a_{0} = 3 .

Write out the first 6 terms of the geometric sequence. Can you find an explicit formula for the sequence (one that just depends on

n

🔗

(b)

Write out the first 6 terms of the sequence without simplifying at all. Now can you find an explicit formula?

🔗

(c)

Using the same technique of writing out the terms without simplifying, find an explicit formula for the general form,

a_{k} = r a_{k - 1},

of a geometric sequence.

🔗

Proving a Recursive Sequence Satisfies an Explicit Formula.

To prove a recursively defined sequence satisfies an explicit formula:

🔗

Assume the recursive formula for the sequence.
Show, using an induction proof, that the explicit formula holds. You need to prove the base step for all initial terms. You will need to use the recurrence relation in the inductive step.

🔗

Activity 5.6.3.

Prove if

a_{0} = 2

and

a_{k} = a_{k - 1} + 5,

then

a_{n} = 2 + 5 n

for

n \geq 0

by induction.

🔗

Hint.

You are assuming the recursive relationship holds. The statement you are proving by induction is that

a_{n} = 2 + 5 n

for

n \geq 0 .

🔗

Activity 5.6.4.

Prove if

a_{k} = r a_{k - 1},

then

a_{n} = a_{0} r^{n}

for

n \geq 0

by induction.

🔗

Hint.

You are assuming the recursive relationship holds. The statement you are proving by induction is that

a_{n} = a_{0} r^{n}

for

n \geq 0 .

🔗

As promised, in Example 5.6.4 we will prove an explicit formula for the Fibonacci sequence. We will not derive it as that is beyond the scope of this course. But we can prove that it works using induction. Before working through the proof, it will be helpful to see the algebraic simplification in the next activity.

🔗

Activity 5.6.5.

Simplify

(\frac{1 + \sqrt{5}}{2})^{2}

and

(\frac{1 - \sqrt{5}}{2})^{2} .

🔗

Example 5.6.4. Proving Explicit Formula for the Fibonacci Sequence.

Let

F_{k} = F_{k - 1} + F_{k - 2}, k \geq 1,

F_{0} = 1, F_{1} = 1

be the Fibonacci sequence.

Prove

F_{n} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{n + 1} - (\frac{1 - \sqrt{5}}{2})^{n + 1}] .

Proof.

Let

F_{k} = F_{k - 1} + F_{k - 2}, F_{0} = 1, F_{1} = 1 .

Base Step: Let

n = 0 .

Then

F_{0} = 1 .

And

\frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{0 + 1} - (\frac{1 - \sqrt{5}}{2})^{0 + 1}] = \frac{1}{\sqrt{5}} [\frac{2 \sqrt{5}}{2}] = 1

Let

n = 1 .

Then

F_{1} = 1 .

And

\frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{1 + 1} - (\frac{1 - \sqrt{5}}{2})^{1 + 1}] = \frac{1}{\sqrt{5}} [\frac{6 + 2 \sqrt{5}}{4} - \frac{6 - 2 \sqrt{5}}{4}] = 1

Induction Step: Assume

F_{i} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{i + 1} - (\frac{1 - \sqrt{5}}{2})^{i + 1}], 0 \leq i \leq k

for some

k \geq 0

(strong induction).

Show

F_{k + 1} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k + 2} - (\frac{1 - \sqrt{5}}{2})^{k + 2}] .

Proof of induction step: By the recursive definition of the sequence,

F_{k + 1} = F_{k} + F_{k - 1} .

Thus,

\begin{aligned} F_{k + 1} & = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k + 1} - (\frac{1 - \sqrt{5}}{2})^{k + 1}] + \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k} - (\frac{1 - \sqrt{5}}{2})^{k}] \\ = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k + 1} + (\frac{1 + \sqrt{5}}{2})^{k} - (\frac{1 - \sqrt{5}}{2})^{k + 1} - (\frac{1 - \sqrt{5}}{2})^{k}] \\ = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k} (\frac{1 + \sqrt{5}}{2} + 1) - (\frac{1 - \sqrt{5}}{2})^{k} (\frac{1 - \sqrt{5}}{2} + 1)] \\ = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k} (\frac{3 + \sqrt{5}}{2}) - (\frac{1 - \sqrt{5}}{2})^{k} (\frac{3 - \sqrt{5}}{2})] \\ = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k} (\frac{1 + \sqrt{5}}{2})^{2} - (\frac{1 - \sqrt{5}}{2})^{k} (\frac{1 - \sqrt{5}}{2})^{2}] \\ = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{k + 2} - (\frac{1 - \sqrt{5}}{2})^{k + 2}] \end{aligned}

Therefore, by induction,

F_{n} = \frac{1}{\sqrt{5}} [(\frac{1 + \sqrt{5}}{2})^{n + 1} - (\frac{1 - \sqrt{5}}{2})^{n + 1}] .

Note, the proof contains some algebraic steps that may not be obvious. But all of them can be checked. For example, it is easier to see that

(\frac{3 + \sqrt{5}}{2}) = (\frac{1 + \sqrt{5}}{2})^{2}

by squaring the RHS and simplifying.

It can be confusing to remember when to use induction and when to use a LHS/RHS proof. The following summary gives guidelines for when to use each technique.

🔗

Summary of Techniques for Sequences.

If you are given a sequence where each term is just a formula for

n :

🔗

You sequence is defined explicitly.
For example, $a_{n} = n^{2} + 5 .$
To prove a recurrence relation, use LHS/RHS proof.
You are assuming the explicit formula and proving the recurrence relation. Thus, use the explicit formula in your proof. Do not assume the recurrence relation.

🔗

If you are given a sequence where each term is defined by previous terms:

🔗

You sequence is defined recursively.
For example, $a_{n} = 3 a_{n - 1} + 2 a_{n - 2} .$
To prove an explicit formula, use induction on the explicit formula.
You are assuming the recurrence formula and proving the explicit formula. Thus, use the recurrence formula in your proof, generally in the induction step. Your base step, assume statement, and show statement all involve the explicit formula.