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 Sk and is called the kth 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) = k2 − 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 Crbe 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 sk would be what you see in the kth second. It is convenient to use terminology like this in describing sequences. For example, the terms that precede the kth term of 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 Ck 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 Ck. If k ≥2, then every string of 0's and 1's with length k and no two consecutive 0's is either 1sk − 1 or 01sk − 2, where sk − 1 and sk − 2 are strings with no two consecutive 0's of length k − 1 and k − 2 respectively. From this observation we can see that Ck= Ck − 2 + Ck − 1 for k ≥ 2. The terms C0 = 1 and C1 = 2 are easy to determine by enumeration. Now, by iteration, any Ck can be easily determined. For example, C5 = 21 can be computed with five additions. A closed form expression for Ck would be an improvement. Note that the recurrence relation for Ck is identical to the one for The Fibonacci Sequence. Only the basis is different.
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.