Chapter 1: Introduction
1.3 Because of round-off errors, it is customary to specify the number of decimal places that
should be included in the output and round up accordingly. Otherwise, numbers come out
looking strange. We assume error checks have already been performed; the routine
Separate
O
is left to the reader. Code is shown in Fig. 1.1.
1.4 The general way to do this is to write a procedure with heading
void ProcessFile( const char *FileName );
which opens FileName,
O
does whatever processing is needed, and then closes it. If a line of
the form
#include SomeFile
is detected, then the call
ProcessFile( SomeFile );
is made recursively. Self-referential includes can be detected by keeping a list of files for
which a call to ProcessFile
O
has not yet terminated, and checking this list before making a
new call to ProcessFile.
O
1.5 (a) The proof is by induction. The theorem is clearly true for 0 < X
O
≤ 1, since it is true for
X
O
= 1, and for X
O
< 1, log X
O
is negative. It is also easy to see that the theorem holds for
1 < X
O
≤ 2, since it is true for X
O
= 2, and for X
O
< 2, log X
O
is at most 1. Suppose the theorem
is true for p
O
< X
O
≤ 2p
O
(where p
O
is a positive integer), and consider any 2p
O
< Y
O
≤ 4p
O
(p
O
≥ 1). Then log Y
O
= 1 + log (Y
O
/ 2) < 1 + Y
O
/ 2 < Y
O
/ 2 + Y
O
/ 2 ≤ Y
O
, where the first ine-
quality follows by the inductive hypothesis.
(b) Let 2
X
O
= A
O
. Then A
O
B
O
= (2
X
O
)
B
O
= 2
XB
O
. Thus log A
O
B
O
= XB
O
. Since X
O
= log A
O
, the
theorem is proved.
1.6 (a) The sum is 4/3 and follows directly from the formula.
(b) S
O
=
4
1
__
+
4
2
2
___
+
4
3
3
___
+
. . .
.4S
O
= 1+
4
2
__
+
4
2
3
___
+
. . .
. Subtracting the first equation from
the second gives 3S
O
= 1 +
4
1
__
+
4
2
2
___
+
. . .
. By part (a), 3S
O
= 4/ 3soS
O
= 4/ 9.
(c) S
O
=
4
1
__
+
4
2
4
___
+
4
3
9
___
+
. . .
.4S
O
= 1 +
4
4
__
+
4
2
9
___
+
4
3
16
__ _
+
. . .
. Subtracting the first equa-
tion from the second gives 3S
O
= 1+
4
3
__
+
4
2
5
___
+
4
3
7
___
+
. . .
. Rewriting, we get
3S
O
= 2
i
O
=0
Σ
∞
4
i
O
i
___
+
i
O
=0
Σ
∞
4
i
O
1
___
. Thus 3S
O
= 2(4/ 9) + 4/ 3 = 20/ 9. Thus S
O
= 20/ 27.
(d) Let S
N
O
=
i
O
=0
Σ
∞
4
i
O
i
O
N
O
__ _
. Follow the same method as in parts (a) - (c) to obtain a formula for S
N
O
in terms of S
N
O
−1
, S
N
O
−2
, ..., S
O
0
and solve the recurrence. Solving the recurrence is very
difficult.
-1-
