Answers/Hints to Selected Problems
Chapter 1
0
1.3 m(n + 1)/2 ≈ mn/2.
0
1.4 The minimum occurs when all the m elements of b are conveniently located in the first m positions of A.
0
1.8 Assume a > b, then there are 2⌊b⌋+ 1 horizontal rows of points (x,y) in the ell ipse. Since the ellipse
is convex, determining the end points of each row determines the size of the entire row. By handling separately
the cases x = 0 and y = 0, we then find that the number of such points can be written as 2⌊a⌋+ 2⌊b⌋+ 1 +
4
∑
⌊b⌋
j=1
a
√
b
2
−j
2
b
. Hence the entire computational effort is linear in the smaller dimension of the elli pse.
0
1.9 The costs “crosses” between n = 32 and n = 64, and quite closer to the latter.
0
1.18 (a) n + 1; (b) 15; (c) 50; (d) 13.
0
1.23 r
3
= 6.
0
1.30 Induction does not work because the equation does not hold for initial values: m = n = 1.
0
1.45 A possible tighter lower bound is L
n
= 2
2
n
+n
.
0
1.49 View the formula F
2
n
−F
2
n−1
−F
n
F
n−1
= (−1)
n+1
as a quadratic equation for F
n
.
0
1.50 In Power1 w e have n + 1 operations. In Power2 we have at most 2 + 2
λ
(n), where
λ
(n) ≡ ⌊lg n⌋,
the floor of the binary logarithm of n.
Chapter 2
0
2.3 (a) All values. (b) All values. (c) All values. (d) When x is an integer, the equation is true.
If not, let x = n + s. The equation holds for either 0 < s 6
1
3
or
2
3
< s < 1.
0
2.4 Let m = ⌊
√
x⌋, then B(x) = A(x) −1 unless x ∈{m
2
, m(m +1)} or (m +1)
2
−1 6 x < (m +1)
2
in which
case A(x) = B(x).
0
2.9 (a) ⌈n/2⌉
2
. (b) Let N =
n−2
3
, then the sum becomes
N+1
2
[8 + 15N + 6N
2
].
0
2.10 (a) n(n +1)(2n +1)/6. If m > n, the number of squares is n(n+ 1)(3m +1 −n)/6. (b) n
2
(n+ 1)
2
/4.
If m > n, t he number of rectangles is mn(m + 1)(n + 1)/4.
0
2.12 (a)
n
2
(6n
2
−3n −1). (b) Φ
4
(n) = Φ
2
(n)(3n
2
+ 3n −1)/5. (c)
n(3n+5)
2(n+1)(n+2)
. (d) 1 −
1
n!
. (e)
1
x
2
(−ln(1−x) −x).
0
2.13 (a) H
⌊n/2⌋
. (b)
1
2
+ 3H
⌊(n−1)/2⌋
−3H
n−1
−H
⌊(n+1)/2⌋
+ 3H
n+1
. (c) −4m
3
−9m
2
−6m −1 =
−(4m + 1)(m + 1)
2
. (d) H
n−1
+
3
4
−
1
2n
−
1
2(n+1)
. No limit. (e)
5
4
+
1
2(n+1)
−
3
2n
. (f)
a−1
a
2
e
a
+
1
a
2
−
1
2
.
753
754
Answers/Hints to Selected Problems
0
2.14
∑
n
k=1
k
2
x
k
= x
d
dx
x
d
dx
∑
n
k=1
x
k
. The limit is
x(1+x)
(1−x)
3
.
0
2.18 (a)
∑
i>1
∑
n>i+1
a
ni
. (b)
∑
i>1
∑
n>i+2
a
ni
. (c)
∑
i>1
∑
n>max{1,i−1}
a
ni
. (d)
n−1
∑
k=0
n−k
∑
j=1
a
k j
.
0
2.19 (a)
ab
1−b
1−(ab)
n
1−ab
−
ab
n+1
1−b
1−a
n
1−a
. (b)
ab
b−1
h
1−a
n
1−a
−
1
b
n
1−(ab)
n
1−ab
i
.
0
2.20 (a
2
b)
n(n+1)(n+2)/6
.
0
2.26 ln2.
0
2.34 (a) ∆
(x + 3)(4x −1)
= 8x + 15. ( b)
5
(3x+2)(3x+5)
.
0
2.35 ∇
−1
1 = x +C, ∇
−1
x =
x
2
(x + 1) +C, ∇
−1
x
2
=
x
6
(x + 1)(2x + 1) +C.
0
2.40 In all problems we use the equation ∆q
k
= q
k
(q−1). (a) (2n−1)2
n+1
+3; (b) 3n 4
n+2
−4
n+3
+
4
3
; (c)
1
b
R
1
0
1−u
b
1−u
udu.
0
2.41 (a)
∑
n−1
k=1
∑
n
m=1
a
km
. (b)
∑
n−1
k=1
∑
n
m=k+1
a
km
. (c)
∑
n
k=1
∑
n
m=k
a
km
.
0
2.46
asinb−a
n+1
sinb(n+1)+a
n+2
sin bn
1−2ac os b+a
2
.
0
2.51 336, so no.
0
2.52 74.
0
2.53 (a) n
m
; (b) n
m
.
0
2.54 (a) n!; (b) n(n
2
+ 1)/2.
0
2.56 (a) n
n
2
; (b) n
1+(n−1)
2
; (c) n
1+n(n−1)/2
.
0
2.63 (a) m(x + 1)
m−1
; (b) m x
m−1
; (c) mx
m−1
; (d) m (x −1)
m−1
; (e) m(x + a + 1)
m−1
.
0
2.64 (a)
n
2(n+2)
; (b)
77
180
.
0
2.65 (a) k
2
= k(k −1) = k
2
−k k
3
= k
3
−3k
2
+2k; (b) k
2
= k
2
+k k
3
= k(k +1)(k + 2) = k
3
+3k
2
+
2k.
0
2.69 17850.
0
2.71 194,594,400 distinct anagrams.
0
2.79
a
1
+a
2
+···+a
n
a
1
,a
2
,...,a
n
.
0
2.87 n = 14.
0
2.88
13
2
4
2
4
2
44 = 123,552 and
13
1
4
2
12
3
4
1
4
1
4
1
= 1,098,240.
0
2.91 480.
Answers/Hints to Selected Problems
755
0
2.92 (a) 120; (b) 12.
0
2.93 (a)
9
2
20
5
= 558,144. (b) 2 ×558,144 = 1,116,288.
0
2.94 16
8
= 518,918,400 choices.
0
2.95 1350.
0
2.97 3,960,000.
0
2.99 (a) 220; (b) 4
9
= 262,144; (c) 220 ×9! = 79,833,600.
0
2.101 (a) 0; (b) −
1
16
; (c) −4; (d) 1; (e) 0; (f) 2
32
63!!.
0
2.103 (a)
(−4)
−n
1−2n
2n
n
; (b)
1
2
2n
n
; (c)
2n−1
n
.
0
2.109 The total number of inversions in a permutation and its inverse must be equal t o
n
2
.
0
2.116 (−1)
r
δ
t,r
, where Kronecker’s delta is defined in Eq. (2.5).
0
2.117 Calculate the sum of the sequence, using the symmetry relation
n
k
=
n
n−k
(n−1)/2
∑
k=1
n
k
=
1
2
(n−1)/2
∑
k=1
n
k
+
n
n −k
=
1
2
n−1
∑
k=1
n
k
=
1
2
(2
n
−2) = 2
n−1
−1.
This is an odd number, which implies the claim.
0
2.121 Substitute a
n
(−1)
n
in E q. (2.69) instead of a
n
.
0
2.126 (H ∗H)
n
= (n + 1)
h
H
2
n−1
−H
(2)
n−1
i
−2nH
n−1
+ 2n −2.
0
2.130
∑
m
k=0
k+(−n−1)
k
=
−n−1+m+1
m
=
m−n
m
= (−1)
m
n−1
m
.
0
2.132
∑
k>0
m+k
n
x
k
=
∑
k>0
m+k
m−n+k
x
k
= x
n−m
∑
k>0
n+(m−n+k)
m−n+k
x
m−n+k
= x
n−m
∑
j>m−n
n+ j
j
x
j
= x
n−m
∑
j>m−n
−n−1
j
(−x)
j
=
x
n−m
(1−x)
n+1
.
0
2.136
∑
m
i=1
∑
n
j=1
(−1)
i+ j+m+n
n−1
j−1
m−1
i−1
i+ j
i
=
∑
m
i=1
(−1)
m+i
m−1
i−1
∑
n
j=1
(−1)
n+ j
n−1
j−1
i+ j
i
=
∑
m
i=1
(−1)
m+i
m−1
i−1
i+1
n
= (−1)
m+m−1+1
1+1
n−m+1
=
2
n−m+1
.
0
2.144 (a) (1+ z)
a
; (b)
1
z
sinz; (c)
1
z
sin
[−1]
z.
0
2.147 F
t+1, t−m−q, −p
t+1−p−q,t−m+1
1
.
0
2.150 (a)
2n
n
=
(2n)!
n!n!
≈
(2n)
2n
√
2
π
2ne
−2n
(
n
n
√
2
π
n e
−n
)
2
; (b)
4n
n
=
(4n)!
n!(3n)!
≈
(4n)
4n
√
2
π
4n e
−4n
n
n
√
2
π
ne
−n
(3n)
3n
√
2
π
3ne
−3n
.
Chapter 3
Get Methods in Algorithmic Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
