CSCE 3110  Homework #1


        Due date:  Wednesday, 01/28/2009


        Do the following exercises in Chapter 1 of the text, pages
        39-40:

        1.5, 1.7(b), 1.8(a,b,c), 1.9, 1.10, and 1.11(a,b).


        1.5  Write a recursive function that returns the number of
             1's in the binary representation of N.  Use the fact 
             that this is equal to the number of 1's in the repre-
             sentation of N/2, plus 1, if N is odd.

        1.7  Prove the following formula:
             b)  log(A^B) = B log A.  (A^B means A to the power B.)

        1.8  Evaluate the following sums:
             a)  sum(i = 0 to infinity) 1/4^i
             b)  sum(i = 0 to infinity) i/4^i
             c)  sum(i = 0 to infinity) i*i/4^i

        1.9  Estimate sum(i = floor(N/2) to N) 1/i.
 
        1.10  What is 2^100 (mod 5)?

        1.11  Let F_i be the Fibonacci numbers as defined in Section
              1.2 and in class.  Prove the following:
              a)  sum(i = 1 to N-2) F_i = F_N - 2
              b)  F_N < p^N, where p = (1+sqrt(5))/2