- Answers to Exercises 259
We can divide the equation by
(n
k− 1)
and multiply byk(k+ 1) to get(n−k+ 1)(n−k)−2(n−k+ 1)(k+1)+k(k+1)≤ 0.Simplifying, we obtain
4 k^2 − 4 nk+n^2 −n− 2 < 0.Solving fork, we get that the left-hand side is nonpositive between the two
roots:
n
2
−
1
2
√
n+2≤k≤n
2+
1
2
√
n+2.So the first integerkfor which this is nonpositive is
k=⌈
n
2−
1
2
√
n+2⌉
.
3.8 An Eagle’s-Eye View: Fine Details
3.8.2. We apply the lower bound in Lemma 2.5.1 to the logarithms. For
a typical term, we get
ln(
m+t−k
m−k)
≥
m+t−k
m−k −^1
m+t−k
m−k=
t
m+t−k,
and so
ln(
m+t
m)
+ln(
m+t− 1
m− 1)
+···+ln(
m+1
m−t+1)
≥
t
m+t+
t
m+t− 1+···+
t
m+1.
We replace each denominator by thelargestone to decrease the sum:
t
m+t+
t
m+t− 1+···+
t
m+1≥
t^2
m+t.
Inverting the steps of taking the logarithm and taking the reciprocal, this
gives the upper bound in (3.9).
3.8.1. (a) We have to show thate−t
(^2) /(m−t+1)
≤e−t
(^2) /m
≤e−t
(^2) /(m+t)
.
This is straightforward using thatexis a monotone increasing function.
(b) Take the ratio of the upper and lower bounds; we obtain
e−t
(^2) /(m+t)
e−t^2 /(m−t+1)
=et
(^2) /(m−t+1)−t (^2) /(m+t)
.