Chapter Eight

Recursion

Section 8.1

Recursively Defined Sequences

The following solutions make use of information found on pages 424 - 438 of the textbook.

Exercise 8.1.1:  Definitions

Fill in the blanks to complete the following sentences.

  1. A sequence can be defined in a variety of different ways. One informal way is to write the first few terms with the expectation that the general pattern will be obvious.
  2. A second way to define a sequence is to give an explicit formula for its nth term.
  3. A third way to define a sequence is to use recursion.   This requires giving both an equation, called a recurrence relation, that relates later terms in the sequence to earlier terms and a specification, called initial conditions, of the values of the first few terms of the sequence.
  4. A recurrence relation for a sequence a0, a1, a2, ...  is a formula that relates each term ak to certain of its predecessors ak-1, ak-2, ..., ak-i, where i is a fixed integer and k is any integer greater than or equal to i.
    The initial conditions for such a recurrence relation specify the values of a0, a1, a2, ..., ai-1.

Exercise 8.1.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Let c0, c1, c2, ... be a sequence that satisfies the following recurrence relation: for all integers kgeq.jpg (602 bytes)2,
(1)  ck  = (k-1) · ck-1 + k · ck-2 + k
(2)  c0  = 1    and     c1=2.

Calculate the values of c2, c3, and c4.

Hint
Full solution

2. Let b0, b1, b2, ... be a sequence that satisfies the following recurrence relation: for all integers  igeq.jpg (602 bytes)2,   bi = 5 · bi-1 - 6 · bi-2.

Write expressions for bi+1 and for bi+2.

Hint
Full solution


3. Show that the sequence 1, 1, 2, 6, 24, 120, ... , n!, ...  for  ngeq.jpg (602 bytes)0 satisfies the recurrence relation  bk = k · bk-1  for all integers kgeq.jpg (602 bytes)1.

Hint
Full solution

4. Show that the sequence 5, 10, 20, 40, ... , 5 · 2k, ... for  kgeq.jpg (602 bytes)0 satisfies the recurrence relation  an = 2 · an-1  for all integers ngeq.jpg (602 bytes)1.

Hint
Full solution


5. Read the discussion of the tower of Hanoi on pages 427 - 430 of the textbook. For each integer  ngeq.jpg (602 bytes)1 let mn be the minimum number of moves needed to move a tower of n disks from one pole to another.

a) Find m1.
b) Find a formula for mn in terms of mn-1.
c) Work out the minimum number of moves required to move a tower of 7 disks from one pole to another.
d) Find m32.

Hint
Full solution


6. Read the discussion on the Fibonacci Numbers on pages 431 - 432.  For each integer n, ngeq.jpg (602 bytes)1, let
Fn = the number of rabbit pairs alive at the end of month n     and let     F0  =  the initial number of rabbit pairs = 1. 

a) Find F1.
b) Find a formula for Fn in terms of Fn-1 and Fn-2.
c) How many rabbit pairs will there be at the end of two years? (Assume no rabbits die.)

Hint
Full solution


7. Bit strings

a) Make a list of all bit strings of lengths 0, 1, 2, and 3 that do not contain the bit pattern 10.
b) For each integer ngeq.jpg (602 bytes)0 let Sn = the number of bit strings of length n that do not contain the pattern 10.  Find S0, S1, S2 and S3.
c) Find the number of bit strings of length ten that do not contain the pattern 10. (Use a recurrence relation for Sn.)

Hint
Full solution

Section 8.3

Second-Order Linear Homogeneous Recurrence Relations With Constant Coefficients

The following solutions make use of information found on pages 453 - 464 of the textbook.

Exercise 8.3.1:  Definitions

Fill in the blanks to complete the following sentences.

  1. A  second-order linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form
    ak = A · ak-1 + B · ak-2    for all integers k     geqred.jpg (896 bytes) some fixed integer, where A and B are fixed real numbers with B noteqred.jpg (905 bytes)0.
  2. Use the discussion at the bottom of page 454 `The Distinct Roots Case' to fill in the following details. 
    Suppose ak = - ak-1 + 12 ak-2  is a second-order linear homogeneous recurrence relation. Suppose that for some number t with tnoteq.jpg (604 bytes)0, the sequence  1, t, t2, t3, ..., tn,... satisfies the above relation. So for all integers kgeq.jpg (602 bytes)2, 
    tk = -1 · tk-1 + 12 · tk-2.
    Since t is not equal to 0, this equation may be divided by tk-2 to obtain t2 = -1 · t + 12. Or, equivalently, t2 + t - 12 = 0.
    The only possible values of t are - 4 and 3.
    Therefore the two sequences will be
    1, -4, 16, -64, 256, ..., (-4)n, ...    and     1, 3, 9, 27, 81, ..., 3n, ...
  3. Lemma 8.3.1 Let A and B be real numbers.  A recurrence relation of the form ak = A · ak-1 + B · ak-2  is satisfied by the sequence 1, t, t2, t3, ..., tn,... where t is a nonzero real number, if, and only if, t satisfies the equation  t2 - A · t - B = 0.
  4. Given a second-order linear homogeneous recurrence relation with constant coefficients: ak = A · ak-1 + B · ak-2    for all integers k geqred.jpg (896 bytes) 2, the characteristic equation of the relation   t2 - A · t - B = 0.
  5. Lemma 8.3.2 If r0, r1, r2, ... and  s0, s1, s2, ... are sequences that satisfy the same second-order linear homogeneous recurrence relation with constant coefficients, and if C and D are any numbers, then the sequence a0, a1, a2, ... defined by the formula
    an = C · rn + D · sn     for all integers n     geqred.jpg (896 bytes) 0
    also satisfies the same recurrence relation.
  6. Distinct Roots Theorem Suppose a sequence a0, a1, a2, ...   satisfies a recurrence relation ak = A · ak-1 + B · ak-2  for some real numbers A and B and all integers kgeq.jpg (602 bytes)2. If the characteristic equation t2 - A · t - B = 0   has two distinct roots r and s, then a0, a1, a2, ... satisfies the explicit formula
    an = C · rn + D · sn, where C and D are the numbers whose values are determined by the values a0 and a1.

Exercise 8.3.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Which of the following defines a second-order linear homogeneous recurrence relation with constant coefficients? 
a) ak+1 = 4 ak - 1/2 ak-1

b) bk = - bk-1 + 5

c) ck = a · ck-1 + ck-2  (where a is a particular real number)

d) dk = dk-1 · dk-2

e) ek = 2 ek-1 + 3 ek-2 - sqrt2.jpg (659 bytes) ek-3 

Hint
Full solution

2. Consider the recurrence relation  ak = 2 ak-1 + 15 ak-2   for all integers kgeq.jpg (602 bytes)2. Find all the sequences of the form 1, t, t2, t3, ..., tn,... which satisfy this recurrence relation.

Hint
Full solution

3. Consider the second-order linear homogeneous recurrence relation  rk = rk-1 + 2 rk-2.
a) Find the two sequences which satisfy this relation; call these sequences bk  and ck.
b) Now let  an = 3 bn -  cn  for all ngeq.jpg (602 bytes)0.  Show that for all integers kgeq.jpg (602 bytes)2, the sequence ak also satisfies the recurrence relation rk = rk-1 + 2 rk-2. 

Hint
Full solution

4. Find a sequence that satisfies the recurrence relation bk = 5 bk-1 - 4 bk-2  and that also satisfies the initial conditions b0 = 2   and  b1 = 3.

Hint
Full solution


5. Find an explicit formula for the sequence a0, a1, a2, ...  which satisfies the recurrence relation ak = ak-1 + 6 ak-2  
and that also satisfies the initial conditions a0 = 13  and a1 = -1.

Hint
Full solution

Section 8.4

General Recursive Definitions

The following solutions make use of information found on pages 466 - 470 of the textbook.

Exercise 8.4.1:  Definitions

Fill in the blanks to complete the following sentences.

  1. Formally, a recursive definition for a set consists of the following three components:
    I. Base: A statement that certain objects belong to the set.
    II. Recursion: A collection of rules indicating how to form new set objects from those already known to be in the set.
    III. Restriction: A statement that no objects belong to the set other than those coming from I and II.
  2. Given numbers a1, a2, a3, ..., an, where n is a positive integer, the summation from i = 1 to n of the ai,  denoted Sni=1 ai, is defined as follows:
    1 ai

    =

    		 a1

    and

    		 n ai

    =

    (

    		 n-1 ai )

    +

    		 an, if n > 1.
    S S S
    i=1 i=1 i=1
  3. Given numbers a1, a2, a3, ..., an, where n is a positive integer, the product from i = 1 to n of the ai, denoted Pni=1 ai, is defined as follows: 
    1 ai

    =

    		 a1

    and

    		 n ai

    =

    (

    		 n-1 ai )

    ·

    		 an, if n > 1.
    P P P
    i=1 i=1 i=1

 

Exercise 8.4.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Complete the following program to show how you might compute the product of a[1],  a[2], ..., a[n].

prod := 0
for k := 1 to n
        prod := prod · a[k]
next k.

2. Prove, using mathematical induction or otherwise, that for any positive integer n, if a1, a2, ..., an  and  b1, b2, ..., bn are real numbers then:

n (ai · bi)

=

 n ai

·

 n bi.
P P P
i=1 i=1 i=1

Hint
Full solution