Discrete Mathematics for Computer Science

80 CHAPTER 1 Sets, Proof Templates, and Induction

13. The terms of a sequence are given recursively as ao = 0, a 1 = 4, and a, = 8 anI --

16 an-2 for n > 2. Prove by induction that bn = n 4n is a closed form for the sequence.

14. The terms of a sequence are given recursively as po = 1, P1 = 2, and Pn = 2 Pn-I -
    Pn-2 for n > 2. Prove by induction that bn = 1 + n is a closed form for the
    sequence.


15. (a) Prove that with just 3-cent and 5-cent stamps, you can make any amount of postage
    (any natural number of cents) except^1 cent,^2 cents,^4 cents, and^7 cents.
    (Hint: That you can make 0-cent postage is obvious. You need to prove two things:
    (i) that you can assemble any amount of postage except 1 cent, 2 cents, 4 cents,
    and 7 cents; and (ii) that you cannot assemble these four amounts. Be careful about
    whether you use the Principle of Mathematical Induction or the Strong Form of
    Mathematical Induction.)
    (b) What amounts of postage can be assembled with 4-cent and 7-cent stamps only?
    (c) What amounts of postage can be assembled with 8-cent and 10-cent stamps only?
    (d) What amounts of postage can be assembled with 7-cent, 8-cent, and 10 cent stamps
    only?
    (e) What amounts of postage can be assembled with 2-cent and 5-cent stamps only?


16. Prove by induction that

1 +V5ý^1 I -

5n+l

Fn = V-= - 2

is a closed form for the Fibonacci sequence.

17. Prove that Fn+m = Fn " Fm + Fm-1 i Fn- 1 for m > 1. Prove the following

corollaries:

(a) Fn-1 [F2n-1.

(b) Fn- 1 F3n-1.

(c) F2 + Fn~l^2 is a Fibonacci number.

18. In how many ways can you climb a ladder with n rungs if at each step you can go

up either one or two rungs? The terms of a sequence are given recursively as al = 1,

a2 = 2, and an = an-1 + an-2 for n > 2. Prove by induction that bn = Fn+l gives

the terms of this sequence where Fn+i is the (n + 1)st Fibonacci number.

19. The Lucas numbers are defined as LO = 2, LI = 1, and Ln = Ln-1 + Ln- 2 for n > 2.

Prove that Ln+ -- Fn- 1 + Fn+l for n > 2.

20. Trace through the execution of the procedure FastPower on the following inputs:
    (a) base = 3, expont = 9.
    (b) base = 2, expont = 10.
    (c) base = 5, expont = 6.
    (d) Count the number of multiplications needed in (a)-(c).


21. What exactly is wrong with the following "proof" that for every real number x > 0,
    x = 2x:
    Suppose the result is true for all real numbers y where O<y < x.
    Case 1: x = 0. Then, 2x = 2- 0 = 0 = x.

Case 2: x > 0. Then, 0 < x/2 < x. So, by hypothesis, x/2 = 2(x/2) = x. Doubling

both sides, deduce that x = 2x. So, the result holds for every real number x > 0 by

the Strong Form of Mathematical Induction.