74 4. Fibonacci Numbers
where the term we ignore is less than^12 ifn≥2 (and tends to 0 ifntends
to infinity); this implies thatFnis the integer nearest toGn.
The baseτ=(1+
√
5)/2 is a famous number: It is called thegolden ratio,
and it comes up all over mathematics; for example, it is the ratio between
the diagonal and side of a regular pentagon. Another way to characterize
it is the following: Ifb/a=τ, then (a+b)/b=τ. So if the ratio between
the longer and shorter sides of a rectangle isτ, then cutting off a square,
we are left with a rectangle that is similar to the original.
4.3.2Define a sequence of integersLnbyL 1 =1,L 2 = 3, andLn+1=Ln+
Ln− 1. (These numbers are calledLucas numbers.) Show thatLncan be expressed
in the forma·q 1 n+b·qn 2 (whereq 1 andq 2 are the same numbers as in the proof
above), and find the values ofaandb.
4.3.3Define a sequence of integersInbyI 0 =0,I 1 = 1, andIn+1=4In+In− 1.
(a) Find a combinatorial counting problem to which the answer isIn. (b) Find a
formula forIn.
4.3.4Alice claims that she knows another formula for the Fibonacci numbers:
Fn=
en/^2 −^1
forn=1, 2 ,...(wheree=2. 718281828 ...is, naturally, the base
of the natural logarithm). Is she right?
Review Exercises
4.3.5In how many ways can you cover a 2×nchessboard by dominoes?4.3.6How many subsets does the set{ 1 , 2 ,...,n}have that contain no two
consecutive integers if 0 andnalso count as consecutive?
4.3.7How many subsets does the set{ 1 , 2 ,...,n}have that contain no three
consecutive integers? Find a recurrence.
4.3.8Which number is larger, 2^100 orF 100?4.3.9Prove the following identities:
(a)F 2 +F 4 +F 6 +···+F 2 n=F 2 n+1−1;
(b) Fn^2 +1−Fn^2 =Fn− 1 Fn+2;
(c)n
0
F 0 +n
1
F 1 +n
2
F 2 +···+n
n
Fn=F 2 n;
(d)n
0
F 1 +n
1
F 2 +n
2
F 3 +···+n
n
Fn+1=F 2 n+1.4.3.10Prove (4.4).4.3.11Is it true that ifFnis a prime, thennis a prime?