Defining Sequences Recursively

Section 5.5 Defining Sequences Recursively

We’ve seen sequences defined explicitly, such as

a_{n} = n^{2} .

Another common way to generate a sequence is by giving a rule for how to generate the next term from the previous term. For example,

a_{n} = a_{n - 1} + 2

where

a_{1} = 1 .

Such sequences are called recursively defined sequences.

🔗

Example 5.5.1. Explicitly Defined Sequences.

Find the first five terms of the sequence given by

a_{n} = n^{2}, n \geq 0 .

Answer 1.

a_{0} = 0, a_{1} = 1, a_{2} = 4, a_{3} = 9, a_{4} = 16

Find the first five terms of the sequence given by

a_{n} = \frac{1}{n}, n \geq 1 .

Answer 2.

a_{1} = 1, a_{2} = 1 / 2, a_{3} = 1 / 3, a_{4} = 1 / 4, a_{5} = 1 / 5

Activity 5.5.1.

Write out the first 6 terms of the sequence

a_{n} = 2^{n}, n \geq 0 .

🔗

Example 5.5.2. Recursively Defined Sequences.

Find the first five terms of the sequence given by

a_{n} = a_{n - 1} + 2, a_{1} = 1 .

Answer 1.

a_{1} = 1, a_{2} = 3, a_{3} = 5, a_{4} = 7, a_{5} = 9

Find the first five terms of the sequence given by

a_{n} = a_{n - 1} + 2, a_{1} = 0 .

Answer 2.

a_{1} = 0, a_{2} = 2, a_{3} = 4, a_{4} = 6, a_{5} = 8

Find the first five terms of the sequence given by

a_{n} = a_{n - 1} + 5 a_{n - 2}, a_{0} = 1, a_{1} = 1 .

Answer 3.

a_{0} = 1, a_{1} = 1, a_{2} = 6, a_{3} = 11, a_{4} = 41

Activity 5.5.2.

Write out the first 6 terms of the sequence

a_{n} = a_{n - 1} + 2 a_{n - 2}, a_{0} = 1, a_{1} = 1 .

🔗

Although both types of sequences use an equation to find

a_{n},

the recursive sequence also needs to define the first few terms. If we change the initial terms, we get a different sequence. The formula used to generate the recursive sequence is called a recurrence relation, while the first term (or terms) is called the initial condition(s).

🔗

An advantage of an explicitly defined sequence is that it is easy to find any particular term. For example, it would be easy to calculate

a_{500}

in Example 5.5.1. In order to find

a_{500}

in Example 5.5.2, we would need to know

a_{499},

and all the terms before that. So we would need to have generated the sequence up to that point to calculate a specific term.

🔗

Recursive sequences have the advantage that they can be faster (or computationally simpler) to calculate, especially if you need to generate many terms of the sequence. Computers are good at generating recursive sequences. It also may be the case that we can easily define a recursive sequence in which it is difficult, or even impossible, to express with an explicit formula.

🔗

Example 5.5.3. The Fibonacci Sequence.

The Fibonacci sequence is defined recursively by

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

Give the first 6 terms of the Fibonacci sequence.

Answer.

1, 1, 2, 3, 5, 8

Activity 5.5.3.

Write out the 7th, 8th, and 9th terms of the Fibonacci sequence.

🔗

The Fibonacci sequence is a good example of a recursively defined sequence where it is difficult to find an explicit formula. An explicit formula for the Fibonacci sequence does exist, we will see it in the next section and in Exercise 5.5.7, but it requires much more sophisticated mathematics to find it than anything we will see in this course. If you are interested, though, this is the sort of thing you would see if you take a combinatorics course. When we do see the formula, it should be clear that it is computationally much harder to work with than the recursive definiton (which is why you rarely see it when working with the Fibonacci sequence).

🔗

Activity 5.5.4.

We would like to explore the connection between recursive and explicit sequences.

🔗

(a)

Write out the first 6 terms of

a_{n} = \frac{(- 1)^{n}}{n!}, n \geq 0 .

Is this an explicitly or recursively defined sequence?

🔗

(b)

Consider the recurrence relationship

a_{k} = \frac{- a_{k - 1}}{k}, k \geq 1 .

Write out several terms of the sequence for a couple different choices of initial terms.

🔗

(c)

How do the sequences in (a) and (b) compare?

🔗

We want to be able to show the relationship between the recursive definition and the explicit definition for a sequence. In this section we will look at proving an explicit sequence satisfies a given recurrence relation. Since, in general, explict formulas contain more information than a recurrence relation, we can use simpler proof techniques to show an explicit sequence satisfies a recurrence relation.

🔗

Proving a Sequence Satisfies a Recurrence Relation.

To prove an explicity defined sequence satisfies a recurrence relation:

🔗

Assume the explicit formula for the sequence.
Show, using a LHS/RHS proof, that the recurrence relation holds.

This is always a direct proof. Do not use induction. We will see induction in the next section.

🔗

Example 5.5.4. Proving a Recurrence Relation for an Explicit Sequence.

Let

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

Show this sequence satisfies the recurrence relation

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

for

k \geq 1 .

Proof.

Assume

a_{n} = 3 n + 1

for all

n \geq 0 .

Show this sequence statisfies the recurrence relation

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

LHS:

a_{k} = 3 k + 1,

since we know that

a_{k}

satisfies the explicit formula.

RHS:

a_{k - 1} + 3 = (3 (k - 1) + 1) + 3,

since we know that

a_{k - 1}

satisfies the explicit formula.

Simplifying, we get

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

Thus, the LHS=RHS, hence

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

Activity 5.5.5.

Prove

a_{n} = \frac{(- 1)^{n}}{n!}, n \geq 0

satisfies the recurrence relationship

a_{k} = \frac{- a_{k - 1}}{k}, k \geq 1,

by assuming the sequence is given by

a_{n} = \frac{(- 1)^{n}}{n!}, n \geq 0,

and showing

a_{k} = \frac{- a_{k - 1}}{k} .

🔗

To show an explicitly defined sequence satisfies a recurrence relationship always assume the explicit formula and show the recursive one. This can almost always be done with a direct proof.

🔗

We can use the recurrence relation for the Fibonacci numbers to prove additional properties.

🔗

Activity 5.5.6.

For the Fibonacci sequence, prove

{F_{k}}^{2} - {F_{k - 1}}^{2} = F_{k} F_{k + 1} - F_{k + 1} F_{k - 1}

for all

k \geq 1 .

🔗

Hint.

Pick whichever side of the equation looks easier to start with. Do some algebra and, where appropriate, use the recursive definition for

F_{k} .

If you get stuck, try working with the other side of the equation.

🔗

Reading Questions Check Your Understanding

1.

Find the 4th term of the sequence:

a_{n} = 5 a_{n - 1} - 4, a_{1} = 2 .

🔗

2.

Find the 4th term of the sequence:

a_{n} = \frac{a_{n - 1}}{a_{n - 2}}, a_{0} = 1, a_{1} = 2 .

🔗

3.

Find the 4th term of the sequence:

a_{n} = n^{2} + n, n \geq 1 .

🔗

4.

Find the 4th term of the sequence:

a_{n} = n + a_{n - 1}, a_{1} = 1 .

🔗

5.

Determine if the following sequence is explicitly defined or recursively defined:

a_{n} = 5 a_{n - 1} - 4, a_{1} = 2 .

🔗

Explicitly defined
Recursively defined

🔗

6.

Determine if the following sequence is explicitly defined or recursively defined:

a_{n} = \frac{a_{n - 1}}{a_{n - 2}}, a_{0} = 1, a_{1} = 2 .

🔗

Explicitly defined
Recursively defined

🔗

7.

Determine if the following sequence is explicitly defined or recursively defined:

a_{n} = n^{2} + n, n \geq 1 .

🔗

Explicitly defined
Recursively defined

🔗

8.

Determine if the following sequence is explicitly defined or recursively defined:

a_{n} = n + a_{n - 1}, a_{1} = 1 .

🔗

Explicitly defined
Recursively defined

🔗

9.

Let

a_{n} = 2 n + 1, n \geq 0 .

Show this sequence satisfies the recurrence relation

a_{k} = a_{k - 1} + 2 .

🔗

Hint.

This is a LHS/RHS proof showing the recurrence relation is true when you assume

a_{n} = 2 n + 1 .

In particular, you know

a_{k} = 2 k + 1

and

a_{k - 1} = 2 (k - 1) + 1 .

🔗

10.

Let

a_{n} = 2 n, n \geq 0 .

Show this sequence satisfies the recurrence relation

a_{k} = a_{k - 1} + 2 .

🔗

Hint.

This is a LHS/RHS proof showing the recurrence relation is true when you assume

a_{n} = 2 n .

In particular, you know

a_{k} = 2 k

and

a_{k - 1} = 2 (k - 1) .

🔗

11.

Let

a_{n} = 2 n + d, n \geq 0 .

Show this sequence satisfies the recurrence relation

a_{k} = a_{k - 1} + 2 .

🔗

Hint.

This is a LHS/RHS proof showing the recurrence relation is true when you assume

a_{n} = 2 n + d .

In particular, you know

a_{k} = 2 k + d

and

a_{k - 1} = 2 (k - 1) + d .

🔗

Exercises Exercises

1.

Find the first 4 terms of the sequence defined by

🔗

a_{1} = 1

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

🔗

2.

Find the first 4 terms of the sequence defined by

🔗

b_{0} = - 1, b_{1} = 2

b_{k} = b_{k - 1} + 2 b_{k - 2}, k \geq 2.

🔗

3.

Let

a_{0}, a_{1}, a_{2}, \dots

be the sequence defined by the formula

a_{n} = 3 n + 1,

for all integers

n \geq 0 .

Show that this sequence satisfies the recurrence relation

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

for all integers

k \geq 1 .

🔗

4.

Let

b_{0}, b_{1}, b_{2}, \dots

be the sequence defined by the formula

b_{n} = 4^{n},

for all integers

n \geq 0 .

Show that this sequence satisfies the recurrence relation

b_{k} = 4 b_{k - 1}

for all integers

k \geq 1 .

🔗

5.

Let

c_{0}, c_{1}, c_{2}, \dots

be the sequence defined by the formula

c_{n} = 2 + n,

for all integers

n \geq 0 .

Show that this sequence satisfies the recurrence relation

🔗

c_{k} = 2 c_{k - 1} - c_{k - 2} .

🔗

6.

Let

F_{0}, F_{1}, F_{2}, \dots

be the Fibonacci sequence. Prove that

🔗

F_{k} = 3 F_{k - 3} + 2 F_{k - 4}

for all integers

k \geq 4 .

🔗

7.

It turns out that the Fibonacci sequence satisfies the following explicit formula:

🔗

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

Verify that the sequence defined by this explicit formula satisfies the Fibonacci recurrence relation

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

for all integers

k \geq 2 .

🔗

You have attempted 1 of 12 activities on this page.

🔗

Prev Top Next