CHAPTER 1
Introduction
1.4 The general way to do this is to write a procedure with heading
void processFile( String fileName );
1.5 public static int ones( int n )
{
1.7 (a) The proof is by induction. The theorem is clearly true for 0 < X 1, since it is true for X = 1, and for X <
1, log X is negative. It is also easy to see that the theorem holds for 1 < X 2, since it is true for X = 2, and
1.8 (a) The sum is 4/3 and follows directly from the formula.
(d) Let SN =
4
0
.
N
i
i
i
=
Follow the same method as in parts (a) – (c) to obtain a formula for SN in terms of SN–1,
1.10 24 = 16
1 (mod 5). (24)25
125 (mod 5). Thus 2100
1 (mod 5).
1.11 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for N = 1, 2, … , k.
(b) As in the text, the proof is by induction. Observe that
+ 1 =
2. This implies that
–1 +
–2 = 1. For N =
1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, … , k.
(c) See any of the advanced math references at the end of the chapter. The derivation involves the use of
generating functions.
1.12 (a)
1 1 1
(2 1) 2 1
N N N
i i i
ii
= = =
− = −
= N(N + 1) – N = N2.
(b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,
