260 16. Answers to Exercises
Here the exponent is
t^2
m−t+1−
t^2
m+t=
(2t−1)t^2
(m−t+ 1)(m+t).
In our case, this is 1900/(41∗60)≈ 0 .772, and so the ratio ise^0.^772 ≈ 2 .1468.
3.8.3. By (3.9), we have
(
2 m
m)/(
2 m
m−t)
≥et(^2) /(m+t)
.
Here the exponent is a monotone increasing function oftfort≥0 (to
see this, write it ast(1−mm+t), or take its derivative), and so from our
assumption thatt≥
√
mlnC+lnCit follows thatt^2
m+t≥
(
√
mlnC+lnC)^2
m+√
mlnC+lnC=
lnC(m+2√
mlnC+lnC)
m+√
mlnC+lnC
>lnC,which implies that (
2 m
m
)/(
2 m
m−t)
>C.
The proof of the other half is similar.
4 Fibonacci Numbers
4.1 Fibonacci’s Exercise
4.1.1. Because we use the two previous elements to compute the next.
4.1.2. Fn+1.
4.1.3. Let us denote bySnthe number of good subsets. Ifn= 1, then
S 1 = 2 (the empty set and the set{ 1 }.Ifn= 2, then∅,{ 1 },{ 2 },soS 2 =3.
For anyn, if the subset containsn, then it can not containn− 1 ,so there
areSn− 2 subsets of this type; if it does not containn, then there areSn− 1
subsets. So we have the same recursive formula, soSn=Fn+2.
4.2 Lots of Identities
4.2.1. It is clear from the recurrence that two odd members are followed
by an even, then by two odd numbers again.
4.2.2.We formulate the following nasty-looking statement:Ifnis divisible
by 5 , then so isFn;ifnhas remainder 1 when divided by 5 , thenFnhas
remainder 1 ;ifnhas remainder 2 when divided by 5 , thenFnhas remainder