- Answers to Exercises 263
4.3 A Formula for the Fibonacci Numbers
4.3.1. True forn=0,1. Letn≥2. Then by the induction hypothesis,
Fn=Fn− 1 +Fn− 2=
1
√
5
(
1+
√
5
2
)n− 1
−(
1 −
√
5
2
)n− 1
+
1
√
5
(
1+
√
5
2
)n− 2
−(
1 −
√
5
2
)n− 2
=
1
√
5
(
1+
√
5
2
)n− 2 (
1+√
5
2
+1
)
+
(
1 −
√
5
2
)n− 2 (
1 −√
5
2
+1
)
=
1
√
5
((
1+
√
5
2
)n
−(
1 −
√
5
2
)n)
.4.3.2. Forn= 1 andn= 2, if we require thatLnbe of the given form,
then we get
L 1 =1=a+b, L 2 =3=a1+
√
5
2
+b1 −
√
5
2
.
Solving foraandb, we get
a=1+
√
5
2
,b=1 −
√
5
2
.
Then
Ln=(
1+
√
5
2
)n
+(
1 −
√
5
2
)n
,which follows by induction onnjust as in the previous problem.
4.3.3. (a) For example, every day Jack buys either an ice cream for $1 or
a giant sundae for $2. There are 4 different flavors of ice cream, but only
one kind of sundae. If he hasndollars, in how many ways can he spend
the money?
In=1
2
√
5
(
(2 +
√
5)n−(2−√
5)n)
.
4.3.4. The formula works forn=1, 2 ,...,10 but fails forn= 11, when
it gives 91. In fact, it will be more and more off as we increasen.Wehave
seen that
Fn∼1
√
5
(
1+
√
5
2
)n
=(0. 447 ...)·(1. 618 ...)n.