CS202: Discrete Structures

Fibonacci sequence

An essential tool that anyone interested in computer science must master is how to think recursively. The ability to understand definitions, concepts, al- gorithms, etc., that are presented recursively and the ability to put thoughts into a recursive framework are essential in computer science. One of our goals in this chapter is to help the reader become more comfortable with recursion in its commonly encountered forms.

A second goal is to discuss recurrence relations. We will concentrate on methods of solving recurrence relations, including an introduction to generating functions.

8.1 The Many Faces of Recursion

Consider the following definitions, all of which should be somewhat familiar to you. When reading them, concentrate on how they are similar.

8.1.1 Binomial Coefficients 

Here is a recursive definition of binomial coefficients, which we introduced in Chapter 2.

Definition 8.1.1 Binomial Coefficient - Recursion Definition. Assume n ≥0 and n ≥k ≥0. We define (n) by $\binom{n}{k}$ by

• $\binom{n}{0} = 1$
• $\binom{n}{n} = 1$ and
• $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ if n > k > 0

Observation 8.1.2 A word about definitions: Strictly speaking, when mathematical objects such as binomial coefficients are defined, they should be defined just once. Since we defined binomial coefficients earlier, in Definition 2.4.3, other statements describing them should be theorems. The theorem, in this case, would be that the “definition” above is consistent with the original definition. Our point in this chapter in discussing recursion is to observe alternative definitions that have a recursive nature. In the exercises, you will have the opportunity to prove that the two definitions are indeed equivalent.

Here is how we can apply the recursive definition to compute $\binom{5}{2}$.

$\begin{align*} \binom{5}{2} &= \binom{4}{2} + \binom{4}{1} \\ &= (\binom{3}{2} + \binom{3}{1}) + (\binom{3}{1} + \binom{3}{0})\\ &= \binom{3}{2} + 2\binom{3}{1}) + 1 \\ &= (\binom{2}{2} + \binom{2}{1}) + 2(\binom{2}{1} + \binom{2}{0}) + 1\\ &= (1 + \binom{2}{1}) + 2\binom{2}{1} + 1) + 1 \\ &= 3\binom{2}{1} + 4 \\ &= 3(\binom{1}{1} + \binom{1}{0}) + 4 \\ &= 3(1+1) + 4 = 10 \end{align*}$

8.1.2 Polynomials and Their Evaluation

Definition 8.1.3 Polynomial Expression in x over S (Non-Recursive).

Let n be an integer, n ≥ 0. An nth degree polynomial in x is an expression of the form a_nxⁿ+ a_{n - 1}x^n − 1 + · · · + a₁x + a₀, where a_n, a_{n - 1}, . . . , a₁, a₀ are elements of some designated set of numbers, S, called the set of coefficients and a_n= 0.

We refer to x as a variable here, although the more precise term for x is an indeterminate. There is a distinction between the terms indeterminate and variable, but that distinction will not come into play in our discussions.

Zeroth degree polynomials are called constant polynomials and are simply elements of the set of coefficients.

This definition is often introduced in algebra courses to describe expressions such as f(n) = 4n³ + 2n²− 8n + 9, a third-degree, or cubic, polynomial in n. This definition has a drawback when the variable is given a value and the expression must be evaluated. For example, suppose that n = 7. Your first impulse is likely to do this:

$\begin{align*} f(7) &= 4 \cdot 7^3 + 2 \cdot 7^2 - 8 \cdot 7 + 9 \\ &= 3 \cdot 343 + 2 \cdot 49 -8 \cdot 7 + 9 \\ &= 1423 \end{align*}$

A count of the number of operations performed shows that five multiplica- tions and three additions/subtractions were performed. The first two multipli- cations compute 7² and 7³ , and the last three multiply the powers of 7 times the coefficients. This gives you the four terms; and adding/subtracting a list of k numbers requires k − 1 addition/subtractions. The following definition of a polynomial expression suggests another more efficient method of evaluation.

Definition 8.1.4 Polynomial Expression in x over S(Recursive). Let S be a set of coefficients and x a variable.

(a) A zeroth degree polynomial expression in x over S is a nonzero element of S.

(b) For n ≥1, an n^thdegree polynomial expression in x over S is an expression of the form p(x)x + a where p(x) is an (n − 1)^stdegree polynomial expression in x and a ∈S.

We can easily verify that f (n) = 4n³ + 2n²− 8n + 9 is a third-degree polynomial expression in n over Z based on this definition:

f (n) = 4n³ + 2n²− 8n + 9 = ((4n + 2)n − 8)n + 9

Notice that 4 is a zeroth degree polynomial since it is an integer. Therefore

4n + 2 is a first-degree polynomial; therefore, (4n + 2)n − 8 is a second-degree polynomial in n over ℤ; therefore, f (n) is a third-degree polynomial in n over ℤ. The final expression for f (n) is called its telescoping form. If we use it to calculate f (7), we need only three multiplications and three additions/ subtractions. This is called Horner’s method for evaluating a polynomial expression.

Example 8.1.5 More Telescoping Polynomials.

(a) The telescoping form of p(x) = 5x⁴ + 12x³− 6x² + x + 6 is (((5x + 12)x − 6)x + 1)x + 6. Using Horner’s method, computing the value of p(c) requires four multiplications and four additions/subtractions for any real number c.

(b) g(x) = −x⁵ + 3x⁴ + 2x² + x has the telescoping form ((((−x + 3)x)x + 2)x + 1)x.

Many computer languages represent polynomials as lists of coefficients, usually starting with the constant term. For example, g(x) = −x⁵ + 3x⁴ + 2x² + x would be represented with the list {0, 1, 2, 0, 3, −1}. In both Mathematica and Sage, polynomial expressions can be entered and manipulated, so the list rep- resentation is only internal. Some programming languages require users to program polynomial operations with lists. We will leave these programming issues to another source.

8.1.3 Recursive Searching - The Binary Search

Next, we consider a recursive algorithm for a binary search within a sorted list of items. Suppose r = {r(1), r(2), . . . , r(n)} represent a list of n items sorted by a numeric key in descending order. The j^thitem is denoted r(j) and its key value by r(j).key. For example, each item might contain data on the buildings in a city and the key value might be the height of the building. Then r(1) would be the item for the tallest building and r(1).key would be its height. The algorithm BinarySearch(j,k) can be applied to search for an item in r with key value C . This would be accomplished by the execution of BinarySearch(1, n). When the algorithm is completed, the variable Found will have a value of true if an item with the desired key value was found, and the value of location will be the index of an item whose key is C . If Found keeps the value false, no such item exists in the list. The general idea behind the algorithm is illustrated in Figure 8.1.6

Figure 8.1.6 General Scheme for a Binary Search

def BinarySearch (r ,j ,k , C ) :
   found = False
   if j <= k :
      mid = floor (( j + k ) /2)
      print ( ' probing ␣ at ␣ position ␣ ' + str ( mid ) )
      if r [ mid ] == C :
         location = mid
         found = True
         print ( ' found ␣ in ␣ position ␣ ' + str ( location ) )
         return location
      else :
         if r [ mid ] > C :
            BinarySearch (r ,j , mid - 1 , C )
         else :
            BinarySearch (r , mid + 1 ,k , C )
    else :
         print ( ' not ␣ found ' )
         return False
s =[1 ,9 ,13 ,16 ,30 ,31 ,32 ,33 ,36 ,37 ,38 ,45 ,49 ,50 ,52 ,61 ,63 ,64 ,69 ,77 ,79 ,80 ,81 ,83 ,86 ,90 ,93 ,96]
BinarySearch (s ,0 , len ( s ) -1 ,30)

probing at position 13
probing at position 6
probing at position 2
probing at position 4
found in position 4

8.1.4 Recursively Defined Sequences

For the next two examples, consider a sequence of numbers to be a list of numbers consisting of a zeroth number, first number, second number, ... . If a sequence is given the name S, the k^thnumber of S is usually written S_kor S(k).

Example 8.1.7 Geometric Growth Sequence. Define the sequence of numbers B by

B₀ = 100 and

B_k= 1.08B_k − 1 for k ≥ 1.

These rules stipulate that each number in the list is 1.08 times the previous number, with the starting number equal to 100. For example

$\begin{align*} B_3 &= 1.08B_2\\ &= 1.08(1.08B_1) \\ &= 1.08(1.08(1.08B_0))\\ &= 1.08(1.08(1.08 \cdot 100)) \\ &= 1.08^3 \cdot 100 = 125.971 \end{align*}$

Example 8.1.8 The Fibonacci Sequence. The Fibonacci sequence is the sequence F defined by

F₀ = 1, F₁ = 1 and

F_k= F_k − 2 + F_k − 1 for k ≥ 2

8.1.5 Recursion

All of the previous examples were presented recursively. That is, every “ob- ject” is described in one of two forms. One form is by a simple definition, which is usually called the basis for the recursion. The second form is by a re- cursive description in which objects are described in terms of themselves, with the following qualification. What is essential for a proper use of recursion is that the objects can be expressed in terms of simpler objects, where “simpler” means closer to the basis of the recursion. To avoid what might be consid- ered a circular definition, the basis must be reached after a finite number of applications of the recursion.

To determine, for example, the fourth item in the Fibonacci sequence we repeatedly apply the recursive rule for F until we are left with an expression involving F₀ and F₁:

 $\begin{align*} F_4 &= F_2 + F_3\\ &= (F_0 + F_1) + (F_1 + F_2) \\ &= (F_0 + F_1) + (F_1 + (F_0 + F_1)) \\ &= (1+1) + (1+(1+1)) \\ &= 5 \end{align*}$

8.1.6 Iteration

On the other hand, we could compute a term in the Fibonacci sequence such as F5 by starting with the basis terms and working forward as follows:

Table 8.1.9

F₂ = F₀ + F₁ = 1 + 1 = 2

F₃ = F₁ + F₂ = 1 + 2 = 3

F₄ = F₂ + F₃ = 2 + 3 = 5

F₅ = F₃ + F₄ = 3 + 5 = 8

This is called an iterative computation of the Fibonacci sequence. Here we start with the basis and work our way forward to a less simple number, such as 5. Try to compute F₅ using the recursive definition for F as we did for F₄. It will take much more time than it would have taken to do the computations above. Iterative computations usually tend to be faster than computations that apply recursion. Therefore, one useful skill is being able to convert a recursive formula into a nonrecursive formula, such as one that requires only iteration or a faster method, if possible.

An iterative formula for $\binom{n}{k}$ is also much more efficient than an application of the recursive definition. The recursive definition is not without its merits, however. First, the recursive equation is often useful in manipulating algebraic expressions involving binomial coefficients. Second, it gives us an insight into the combinatoric interpretation of $\binom{n}{k}$. In choosing k elements from {1, 2, ..., n}, there are $\binom{n-1}{k}$ ways of choosing all k from {1, 2, ..., n - 1}, and there are $\binom{n-1}{k-1}$ ways of choosing the k elements if n is to be selected and the remaining k − 1 elements come from {1, 2, ..., n − 1}. Note how we used the Law of Addition from Chapter 2 in our reasoning.

BinarySearch Revisited. In the binary search algorithm, the place where recursion is used is easy to pick out. When an item is examined and the key is not the one you want, the search is cut down to a sublist of no more than half the number of items that you were searching in before. Obviously, this is a simpler search. The basis is hidden in the algorithm. The two cases that complete the search can be thought of as the basis. Either you find an item that you want, or the sublist that you have been left to search in is empty, when j > k.

BinarySearch can be translated without much difficulty into any language that allows recursive calls to its subprograms. The advantage to such a program is that its coding would be much shorter than a nonrecursive program that does a binary search. However, in most cases the recursive version will be slower and require more memory at execution time.

8.1.7 Induction and Recursion

The definition of the positive integers in terms of Peano’s Postulates is a re- cursive definition. The basis element is the number 1 and the recursion is that if n is a positive integer, then so is its successor. In this case, n is the simple object and the recursion is of a forward type. Of course, the validity of an induction proof is based on our acceptance of this definition. Therefore, the appearance of induction proofs when recursion is used is no coincidence.

Example 8.1.10 Proof of a formula for B. A formula for the sequence B in Example 8.1.7 is B = 100(1.08)^kfor k ≥0. A proof by induction follow. If k = 0, then B = 100(1.08)⁰ = 100, as defined. Now assume that for some k ≥1, the formula for B_kis true.

B_{k + 1} = 1.08B_kby the recursive definition

= 1.08 (100(1.08)^k) by the induction hypothesis

= 100(1.08)^{k + 1}

hence the formula is true for k + 1

The formula that we have just proven for B is called a closed form expression. It involves no recursion or summation signs.

Definition 8.1.11 Closed Form Expression. Let E = E (x₁, x₂, . . . , x_n) be an algebraic expression involving variables x₁, x₂, . . . , x_nwhich are allowed to take on values from some predetermined set. E is a closed form expression if there exists a number T such that the evaluation of E with any allowed values of the variables will take no more than T operations (alternatively, T time units).

Example 8.1.12 Reducing a summation to closed form. The sum $E(n) = \sum_{k=1}^{n} k$ is not a closed form expression because the number of additions needed to evaluate E(n) grows indefinitely with n. A closed form expression that computes the value of E(n) is $\frac{n(n+1)}{2}$, which only requires T = 3 operations.

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.