Discrete Mathematics: Elementary and Beyond

4.3 A Formula for the Fibonacci Numbers 75

4.3.12Consider a sequence of numbersb 0 ,b 1 ,b 2 ,...such thatb 0 =0,b 1 =1,
andb 2 ,b 3 ,...are defined by the recurrence

bk+1=3bk− 2 bk− 1.

Find the value ofbk.

4.3.13Assume that the sequence (a 0 ,a 1 ,a 2 ,...) satisfies the recurrence

an+1=an+2an− 1.

We know thata 0 = 4 anda 2 = 13. What isa 5?

4.3.14Recalling the Lucas numbersLnintroduced in Exercise 4.3.2, prove the
following identities:

(a)F 2 n=FnLn;

(b) 2Fk+n=FkLn+FnLk;

(c) 2Lk+n=5FkFn+LkLn;

(d) L 4 k=L^22 k−2;

(e) L 4 k+2=L^22 k+1+2.

4.3.15Prove that ifnis a multiple of 4, thenFnis a multiple of 3.

4.3.16 (a) Prove that every positive integer can be written as the sum of

different Fibonacci numbers.

(b) Prove even more: every positive integer can be written as the sum of dif-

ferent Fibonacci numbers, so that no two consecutive Fibonacci numbers

are used.

(c) Show by an example that the representation in (a) is not unique, but also

prove that the more restrictive representation in (b) is.