- Answers to Exercises 261
1 ;ifnhas remainder 3 when divided by 5 , thenFnhas remainder 2 ;ifn
has remainder 4 when divided by 5 , thenFnhas remainder 3 .This is then
easily proved by induction onn.
4.2.3. By induction. All of them are true forn= 1 andn= 2. Assume
thatn≥3.
(a)F 1 +F 3 +F 5 +···+F 2 n− 1 =(F 1 +F 3 +···+F 2 n− 3 )+F 2 n− 1 =
F 2 n− 2 +F 2 n− 1 =F 2 n.
(b)F 0 −F 1 +F 2 −F 3 +···−F 2 n− 1 +F 2 n=(F 0 −F 1 +F 2 −···+F 2 n− 2 )+
(−F 2 n− 1 +F 2 n)=(F 2 n− 3 −1) +F 2 n− 2 =F 2 n− 1 −1.
(c)F 02 +F 12 +F 22 +···+Fn^2 =(F 02 +F 12 +···+Fn^2 − 1 )+Fn^2 =Fn− 1 Fn+Fn^2 =
Fn(Fn− 1 +Fn)=Fn·Fn+1.
(d)Fn− 1 Fn+1−Fn^2 =Fn− 1 (Fn− 1 +Fn)−Fn^2 =Fn^2 − 1 +Fn(Fn− 1 −Fn)=
Fn^2 − 1 −FnFn− 2 =−(−1)n−^1 =(−1)n.
4.2.4. We can write (4.1) asFn− 1 =Fn+1−Fn, and use this to compute
Fnfor negativenrecursively (going backwards):
...,− 21 , 13 ,− 8 , 5 ,− 3 , 2 ,− 1 , 1 , 0.It is easy to recognize that these are the same as the ordinary Fibonacci
numbers, except that every second number has a negative sign. As a for-
mula, we have
F−n=(−1)n+1Fn.
This is now easily proved by induction onn. It is true forn=0,1, and
assuming that it is true fornandn−1, we get forn+1,
F−(n+1)=F−(n−1)−F−n=(−1)nFn− 1 −(−1)n+1Fn
=(−1)n(Fn− 1 +Fn)=(−1)nFn+1=(−1)n+2Fn+1,which completes the induction.
4.2.5.
Fn+2=Fn+1+Fn=(Fn+Fn− 1 )+Fn=2Fn+(Fn−Fn− 2 )=3Fn−Fn− 2.
Replacingnby 2n−1, we get the recurrence for odd-index Fibonacci
numbers. Using this to prove (4.2):
Fn^2 +1+Fn^2 =(Fn+Fn− 1 )^2 +Fn^2 =2Fn^2 +Fn^2 − 1 +2FnFn− 1
=3Fn^2 +2Fn^2 − 1 −(Fn−Fn− 1 )^2 =3Fn^2 +2Fn^2 − 1 −Fn^2 − 2
=3(Fn^2 +Fn^2 − 1 )−(Fn^2 − 1 +Fn^2 − 2 )=3F 2 n− 1 −F 2 n− 3
=F 2 n+1.