106 CHAPTER 2 Discrete Mathematics
- Solve the Fibonaccidifference equation un+2=un+1+un, n =
0 , 1 , 2 ,...whereu 0 =u 1 = 1. - LetF(n), n= 0, 1 , 2 , ...be the Fibonacci numbers. Use your re-
sult from Exercise #7 to compute the number of digits inF(1000000).
(Hint: use log 10 and focus on the “dominant term.”) - Consider the “generalized Fibonacci sequence,” defined by u 0 =
1 , u 1 = 1, and un+2 = aun+1+bun, n ≥ 0; here a and b are
positive real constants.
(a) Determine the conditions ona andb so that the generalized
Fibonacci sequence remains bounded.
(b) Determine conditions onaandbso thatun→0 asn→∞.
TheLucas numbersare the numbersL(n), n= 0, 1 , 2 , ...where
L(0) = 2, L(1) = 1, and where (just like the Fibonacci numbers)
L(n+ 2) =L(n+ 1) +L(n), n≥ 0 .Solve this difference equation,
thereby obtaining an explicit formula for the Lucas numbers.
LetF(n), L(n), n≥0 denote the Fibonacci and Lucas numbers,
respectively. Show that for eachn≥ 1 , L(n) =F(n+1)+F(n−1).
Solve the second-order difference equation un+2 = − 4 un, n =
0 , 1 , 2 ,...whereu 0 = 1 =u 1.
Solve the second-order difference equationun+2= 2un+1− (^2) n, n=
0 , 1 , 2 ,...,
u 0 = 0, u 1 = 2.
Solve the third-order difference equationun+3=− 3 un+2+un+1+
un, n= 0, 1 , 2 ,...,
u 0 = 1,u 1 = 1,u 2 =− 1.
Solve the inhomogeneous linear difference equation
un+2− 2 un+1+un= 2, n= 0, 1 , 2 ,..., u 0 = 2, u 1 = 6, u 2 = 12.