Find a recurrence relation and initial condition for the number of fruit ies in a jar if there are 12 ies initially and every week there are six times as many ies in the jar as there were the previous week. (10 points)

Find the solution of the recurrence relation a_n = 3a_n1, with a₀ = 2. (5 points)

Find the solution of the linear homogeneous recurrence relation a_n = 7a_n1 6a_n2with a₀ = 1 and a₁ = 4. (6 points)

Suppose that f(n) satises the divide-and-conquer relation f(n) = 2f(n/3) + 5 and f(1) = 7. What is f(81)? (5 points)

Suppose that |A| = |B| = |C| = 100, |AB| = 60, |AC| = 50, |B C| = 40, and |AB C| = 175. How many elements are in ABC? (5 points)

How many positive integers not exceeding 1000 are not divisible by either 4 or 6? (5 points)

How many onto functions are there from a set with six elements to a set with four elements? (7 points)

List the derangements of the set {1,2,3,4}. (6 points)

What is the solution to the recurrence relation a_n = 8a_n1+ 9a_n2if a₀ = 3 and a₁ = 7? (6 points)

Suppose that f(n) satises the divide-and-conquer recurrence relation f(n) = 3f(n/4)+n²/8 with f(1) = 2. What is f(64)? (5 points)

How many positive integers not exceeding 1000 are not divisible by 4, 6, or 9? (7 points)

How many ways are there to assign six jobs to four employees so that every employee is assigned at least one job? (6 points)

How many permutations are there of the digits in the string 12345 that leave 3 xed but leave no other integer xed? (For instance, 24351 is such a permutation.) (5 points)

How many students are enrolled in a course either in calculus, discrete mathematics, data structures, or programming languages at a school if there are 507, 292, 312, and 344 students in these courses, respectively; 14 in both calculus and data structures; 213 in both calculus and programming languages; 211 in both discrete mathematics and data structures; 43 in both discrete mathematics and programming languages; and no student may take calculus and discrete mathematics, or data structures and programming languages, concurrently? (7 points)

Suppose that every hour there are two new bacteria in a colony for each bacterium that was present the previous hour, and that all bacteria 2 hours old die. The colony starts with 100 new bacteria.

a) Set up a recurrence relation for the number of bacteria present after n hours. b) What is the solution of this recurrence relation?

c) When will the colony contain more than 1 million bacteria? (15 points)