1. Determine if the following functions are one-to-one and/or onto. Clearly justify your reasoning.

(a) f(n) = n 3 1 where f : Z Z

(b) f(n) = dn/2e where f : Z Z

(c) f(m, n) = 2m n where f : Z Z Z

2. In most computer languages it is possible to cast a floating point value to an integer. Consider, for example, the following C++ code: float foo = 5.0; int bar = static_cast( foo / 2.0); int baz = static_cast(-foo / 3.0);

(a) What are the values of bar and baz in the code above? (You may think you know this off the top of your head, but make darn sure youre correct as your answers will affect part (b))

(b) Determine an equivalent mathematical function for static cast in terms of the floor (bxc) and ceiling (dxe) functions.

3. Prove or disprove each of the statements about the floor and/or ceiling function:

(a) bdxec = dxe for all real numbers x

(b) bx + yc = bxc + byc for all real numbers x and y

4. Show that the following sequences are solutions to the recurrence relation an = 3an1 + 4an2:

(a) an = (4)n

(b) an = 2(4)n + 3 5. The Lucas Numbers are a sequence very similar to the Fibonacci Sequence discussed in class, the only difference being that the Lucas Numbers start with L0 = 2 and L1 = 1 as opposed to Fibonaccis F0 = 0 and F1 = 1. Concretely, they are defined by L0 = 2, L1 = 1, and Ln := Ln1 + Ln2 for n > 1

(a) Write a function in your favorite language that takes an integer argument N and returns the sum of the first N + 1 even Lucas Numbers. Turn in a print-out of your code, as well as the value your function returns when N = 50. Example: Let N = 10. The first 10+1 = 11 Lucas Numbers are {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123}. Of those, the even numbers are {2, 4, 18, 76}. Their sum is 2 + 4 + 18 + 76 = 100, so your function should return evenLucasSum(10) = 100.

(b) Write a function in your favorite language that takes an integer argument D and returns the index and value of the first D-digit Lucas number. Turn in a print-out of your code, as well as the index and value your function returns when D = 15. Example: Let D = 3. The first 3-digit Lucas Number is L10 = 123, so your function should return something like firstDDigitLucas(3) = (10, 123). (My code is written in Python, so I return a tuple. You can return the index and value in any data structure you like).