262 16. Answers to Exercises
4.2.6. The identity is
(
n
0
)
+
(
n− 1
1)
+
(
n− 2
2)
+···+
(
n−k
k)
=Fn+1,wherek= n/ 2 . Proof by induction. True forn= 0 andn= 1. Letn≥2.
Assume thatnis odd; the even case is similar, except that the last term
below needs a little different treatment.
(
n
0
)
+
(
n− 1
1)
+
(
n− 2
2)
+···+
(
n−k
k)
=1+
((
n− 2
0)
+
(
n− 2
1))
+
((
n− 3
1)
+
(
n− 3
2))
+···
+
((
n−k− 1
k− 1)
+
(
n−k− 1
k))
=
((
n− 1
0)
+
(
n− 2
1)
+
(
n− 3
2)
+···+
(
n−k− 1
k))
+
((
n− 2
0)
+
(
n− 3
1)
+···+
(
n−k− 1
k− 1))
=Fn+Fn− 1 =Fn+1.4.2.7.(4.2) follows by takinga=b=n−1. (4.3), follows by takinga=n,
b=n−1.
4.2.8. Letn=km. We use induction onm.Form= 1 the assertion is
obvious. Ifm>1, then we use (4.5) witha=k(m−1),b=k−1:
Fka=F(k−1)aFa− 1 +F(k−1)a+1Fa.By the induction hypothesis, both terms are divisible byFa.
4.2.9. The “diagonal” is in fact a very long and narrow parallelogram
with area 1. The trick depends on the factFn+1Fn− 1 −Fn^2 =(−1)nis very
small compared toFn^2.