Problem 1. You take a job that pays $25, 000 annually.

(a) How much do you earn n years from now if you receive a three percent raise each year? (b) How much do you earn n years from now if you receive a five percent raise each year?

(c) How much do you earn n years from now if each year you receive a raise of $1, 000 plus two percent of your previous year’s salary?

Solution:  (a) 25, 000 . 1.03n .  (b) 25, 000 . 1.05n .  (c) 25, 000 . 1.02n + 1, 000

Problem 2.  Give a recursive definition for the function f (n) = 5n + 2, n = 1, 2, 3, . . .

Solution: f (n) = f (n - 1) + 5, f (1) = 7.

Problem 3.  Assume that the characteristic equation for a homogeneous linear recurrence relation with con- stant coefficients is (r - 5)3 = 0. Describe the form for the general solution to the recurrence relation.    Solution: an = c5n + dn5n + en2 5n .

Problem 4.  Use the Principle of Mathematical Induction to prove that 2|(n2 + n) for all n 2 0.

Solution: P (0) : 2|02+0, which is true since 2|0. P (k) → P (k +1) : (k +1)2 +(k +1) = (k2 +k)+2(k +1), which is divisible by 2 since 2|k2 + k and 2|2(k + 1).

Problem 5. In the questions below find the best big-oh function for the function.  Choose your answer from among the following: 1, log2 n, n, n log2 n, n2 , n3 , . . . , 2n , n!.

a. f (n) = 1 + 4 + 7 + ... + (3n + 1). Ans: n2 .

b. g(n) = 1 + 3 + 5 + 7 + ... + (2n - 1). Ans: n2 .

c.   Ans: n.

d. f (n) = 1 + 2 + 3 + ... + (n2 - 1) + n2 . Ans: n4 .

e.  [n + 21[n/31. Ans: n2 .

f. 3n4 + log2 n8 . Ans: n4 .

Problem 6.  Prove that if a|b and b|c then a|c.

Solution: Let b = ak and c = bl, for some k, l e Z . Then, c = bl = (ak)l = a(kl). Thus, a|c.

Problem 7.  A group of ten women and ten men are in a room.  If five of the 20 are selected at random and

put in a row for a picture, what is the probability that the five are of the same sex? Solution:   +  .

Problem 8. You pick a word at random from the set of all words of length six of letters of the alphabet with

no repeated letters. What is the probability that the word has exactly one vowel?

Solution: 5 . 6 . P (21, 5)/P (26, 6).

Problem 9.  Prove that there is no smallest positive rational number.

Solution: Proof by contradiction. Let a/b be the smallest rational number, where a, b are both positive (or both negative) integers. But, then, a/2b is smaller than a/b, contradiction.

Problem 10.  Determine whether f is a function from the set of all bit strings to the set of integers if f (S) is the largest integer i such that the ith bit of S is 0 and f (S) = 1 when S is the empty string (the string with no bits).

Solution: No; f is not defined for the string of all 1’s, for example S = 11111.

Problem 11.  A red and a green die are rolled. How many ways are there or getting a sum of six, given that

the number on the green die is odd?

Solution: 3.

Problem 12.  Find the number of subsets of S = {1, 2, 3, . . . , 10} that contain exactly five elements, the sum of which is even.

Solution: C(5, 1)C(5, 4) + C(5, 3)C(5, 2) + 1.

Problem 13.  Prove that the square of any odd number has a remainder of 1 when divided by 8.

Solution:  (2k + 1)2  = 4k2 + 4k + 1 = 4k(k + 1) + 1. Since k and k + 1 are consecutive numbers, one of them must be even. Thus, k(k + 1) = 2m, or (2k + 1)2 = 8m + 1, and the conclusion follows.

Problem 14.  Prove that if n3 + 1 is even, then n is odd.

Solution: Proof by contraposition. Let n be even, i.e. n = 2k for some k e Z. Then, n3 +1 = (2k)3 +1 = 8k3 + 1, which is odd, and we are done.

Problem 15.  Use mathematical induction to show that n lines in the plane passing through the same point divide the plane into 2n regions.

Solution: The basis step follows since one line divides the plane into 2 regions. Now assume that k lines passing through the same point divide the plane into 2k regions. Adding the (k + 1)st line splits exactly two of these regions into two parts each. Hence k + 1 concurrent lines split the plane into 2k + 2 = 2(k + 1) regions.

Problem 16.  Does 6 divide (3k + 1)(3k + 2)(3k + 3)?

Solution: Yes, because the product is of three consecutive numbers, so one of them must be divisible by 3, and at least one must be divisible by 2.

Problem 17. What is the smallest positive integer n such that 25 . 3 . 52 . 73 . n is a perfect square? Solution: n will be the product of primes that make the exponents even, so n = 2 . 3 . 7 = 42.

Problem 18.  Show that if five points are picked on or in the interior of a square of side length 2, then there are at least two of these points no farther than I2 apart.

Solution:  Divide the square into four congruent 1 x 1 squares.  At least two of the five points lie in or on the edge of one of these 1 x 1 squares.  The maximum distance between these two points is I2, the length of the diagonal of each square.