## Sequences

In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes.

**8.2.1 Sequences and Ways They Are Defined**

**Definition 8.2.1 Sequence. **A sequence is a function from the natural numbers into some predetermined set. The image of any natural number *k *can be written as *S*(*k*) or *S** _{k }*and
is called the

*k*

^{th }*term*of

*S*. The variable

*k*is called the

*index*or

*argument*of the sequence.

For example, a sequence of integers would be a function *S *: ℕ *→ *ℤ.

**Example 8.2.2 Three sequences defined ****in different ways.**

(a) The sequence *A *defined by *A*(*k*) = *k*^{2 }*− **k*, *k *≥ 0, is a sequence of integers.

(b) The sequence *B *defined recursively by *B*(0) = 2 and *B*(*k*) = *B*(*k **−* 1) + 3 for *k *≥ 1 is a sequence of integers. The terms of *B *can be computed either by applying the recursion
formula or by iteration. For example,

*B*(3) = *B*(2) + 3

= (*B*(1) + 3) + 3

= ((*B*(0) + 3) + 3) + 3

= ((2 + 3) + 3) + 3 = 11

or

*B*(1) = *B*(0) + 3 = 2 + 3 = 5

*B*(2) = *B*(1) + 3 = 5 + 3 = 8

*B*(3) = *B*(2) + 3 = 8 + 3 = 11

(c) Let *C** _{r}*be the number of strings of 0's and 1's of length

*r*having no consecutive zeros. These terms define a sequence

*C*of integers.

Remarks:

(1) A sequence is often called a *discrete function*.

(2) Although it is important to keep in mind that a sequence is a function, another useful way of visualizing a sequence is as a list. For example, the sequence *A *in the previous example could be written as (0*, *0*, *2*, *6*, *12*, *20*, . . . *).
Finite sequences can appear much the same way when they are the input to or output from a computer. The index of a sequence can be thought of as a time variable. Imagine the terms of a sequence flashing on a screen every second. Then *s** _{k }*would
be what you see in the

*k*

*second. It is convenient to use terminology like this in describing sequences. For example, the terms that precede the*

^{th }*k*

*term of*

^{th }*A*would be

*A*(0)

*, A*(1)

*, ..., A*(

*k*

*−*1). They might be called the earlier terms.

**8.2.2 A Fundamental Problem**

Given the definition of any sequence, a fundamental problem that we will concern ourselves with is to devise a method for determining any specific term in a minimum amount of time. Generally, time can be equated with the number of operations needed. In counting operations, the application of a recursive formula would be considered an operation.

(a) The terms of *A *in Example 8.2.2 are very easy to compute because of the closed form expression. No matter what term you decide to compute, only three operations need to be performed.

(b) How to compute the terms of *B *is not so clear. Suppose that you wanted to know *B*(100). One approach would be to apply the definition recursively:

*B*(100) = *B*(99) + 3 = (*B*(98) + 3) + 3 = *· · ·*

The recursion equation for *B *would be applied 100 times and 100 additions would then follow. To compute *B*(*k*) by this method, 2 *k *operations are needed. An iterative computation of *B*(*k*) is an improvement:

*B*(1) = *B*(0) + 3 = 2 + 3 = 5

*B*(2) = *B*(1) + 3 = 5 + 3 = 8

etc*. *Only *k *additions are needed. This still isn't a good situation. As *k *gets large, we take more and more time to compute *B*(*k*). The formula *B*(*k*) = *B*(*k **− *1) + 3
is called a recurrence relation on *B*. The process of finding a closed form expression for *B*(*k*), one that requires no more than some fixed number of operations, is called solving the recurrence relation.

(c) The determination of *C** _{k }*is a standard kind of problem in combinatorics. One solution is by way of a recurrence relation. In fact, many problems in combinatorics are most easily solved by first searching
for a recurrence relation and then solving it. The following observation will suggest the recurrence relation that we need to determine

*C*

*. If*

_{k}*k*≥2, then every string of 0's and 1's with length

*k*and no two consecutive 0's is either 1

*s*

_{k }

_{− }_{1}or 01

*s*

_{k }

_{− }_{2}, where

*s*

_{k }

_{− }_{1}and

*s*

_{k }

_{− }_{2}are strings with no two consecutive 0's of length

*k*

*−*1 and

*k*

*−*2 respectively. From this observation we can see that

*C*

*=*

_{k}*C*

_{k }

_{− }_{2}+

*C*

_{k }

_{− }_{1}for

*k*≥ 2. The terms

*C*

_{0}= 1 and

*C*

_{1}= 2 are easy to determine by enumeration. Now, by iteration, any

*C*

*can be easily determined. For example,*

_{k }*C*

_{5}= 21 can be computed with five additions. A closed form expression for

*C*

*would be an improvement. Note that the recurrence relation for*

_{k }*C*

*is identical to the one for The Fibonacci Sequence. Only the basis is different.*

_{k }Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.