You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
Exercise 1.13: Prove that
|
|
|
|
Fib
|
|
(
|
|
n
|
|
)
|
|
|
|
is
|
|
the closest integer to
|
|
|
|
|
|
φ
|
|
n
|
|
|
|
|
|
/
|
|
|
|
|
|
5
|
|
|
|
|
|
, where
|
|
φ
|
|
=
|
|
|
|
(
|
|
1
|
|
+
|
|
|
|
5
|
|
|
|
)
|
|
|
|
/
|
|
|
|
2
|
|
|
|
.
|
|
Hint: Let
|
|
ψ
|
|
=
|
|
|
|
(
|
|
1
|
|
−
|
|
|
|
5
|
|
|
|
)
|
|
|
|
/
|
|
|
|
2
|
|
|
|
.
|
|
Use induction and the definition of the Fibonacci numbers (see 1.2.2)
|
|
to prove that
|
|
|
|
Fib
|
|
(
|
|
n
|
|
)
|
|
|
|
=
|
|
|
|
(
|
|
|
|
φ
|
|
n
|
|
|
|
−
|
|
|
|
ψ
|
|
n
|
|
|
|
)
|
|
|
|
/
|
|
|
|
|
|
5
|
|
|
|
|
|
.
|
|
|
