Discrete Mathematics for Computer Science

Exercises 79

Solution. We start with FirstPage = 1 and LastPage = 521. MiddlePage = L(1 +

521)/2] = 261. Since Joe Smith should appear after page 261, we let FirstPage = 262.

Now, MiddlePage = L(262 + 521)/2J = 391. Since Joe Smith is not on page 391 and we

are beyond the page we want, we let LastPage = 390 and compute MiddlePage = L(262 +

390)/2J = 326. We find Joe Smith on this page and return an appropriate message.

Theorem 5. Prove that the algorithm Binary Search of Phone Directory is correct.

Proof. Exercise for the reader. M

U Exercises

Assume that all variables not given an explicit domain are elements of N.

1. The terms of a sequence are given recursively as ao = 2, al = 6, and a, = 2a,_1 +

3 a,-2 for n > 2. Find the first eight terms of this sequence.

2. The terms of a sequence are given recursively as p0 = 3, pI = 7, and Pn = 3 Pn-1 -
   2 Pn-2 for n > 2. Find the first eight terms of this sequence.

3. The terms of a sequence are given recursively as a0 = 0, al = 4, and a, = 8 an-i -

16 an-2 for n > 2. Find the first eight terms of this sequence.

4. Prove that with just 3-cent and 5-cent stamps, you can make any amount of postage
   less than 35 cents (any natural number of cents) except 1 cent, 2 cents, 4 cents, and 7
   cents.


5. The terms of a sequence are given recursively as p0 = 1, p1 = 2, and Pn = 2 p,-1 -
   Pn-2 for n > 2. Write out the information that the inductive step assumes and what
   the step must prove in proving b, = 2- 3n is a closed form for the sequence. Suppose

no = 0 and the base cases are 0 and 1.

6. The terms of a sequence are given recursively as P0 = 3, pi = 7, and pn" = 3 Pn-1 -
   2 Pn-2 for n > 2. Write out the information that the inductive step assumes and what
   the step must prove in proving bn = 2 n+2 - 1 is a closed form for the sequence. Sup-
   pose no - 1 and the base cases are 0 and 1.


7. The terms of a sequence are given recursively as ao = 0, a 1 = 4, and a, = 8 an- -I
   16 an-2 for n > 2. Write out the information that the inductive step assumes and what
   the step must prove in proving bn = n 4n is a closed form for the sequence. Suppose

no = 1 and the base cases are 0 and 1.

8. Given that bn- 1 = 2 3 n-1 and bn-2 - 2. 3 n-2, prove that if bn = 2bn- 1 + 3bn-2,
   then bn = 2. 3n provided n > 2.


9. Given that bn 1 - 2 n+l - 1 and bn- 2 = 2' - 1, prove that if bn = 3bn-1 - 2bn-2,
   then b_ = 2n+2 - 1 provided n > 2.

10. Given that bn- 1 = (n - 1 ) 4 n-1 and bn-2 = (n - 2 ) 4 n-2, prove that if bn = 8bnI -

16b,- 2 , then bn = n4' provided n > 2.

11. The terms of a sequence are given recursively as ao = 2, al = 6, and an =^2 an-I +

3 an-2 for n > 2. Prove by induction that b, = 2. 3n is a closed form for the sequence.

12. The terms of a sequence are given recursively as p0 = 3, pl = 7, and Pn = 3 Pn-I -
    2 Pn-2 for n > 2. Prove by induction that bn = 2 n+2 - 1 is a closed form for the
    sequence.