Solved: Queries to a database of student records at a

a) What is a recurrence relation? b) Find a recurrence relation for the amount of money that will be in an account after n years if $1 ,000,000 is deposited in an account yielding 9% annually.

Explain how the Fibonacci numbers are used to solve Fibonacci's problem about rabbits.

a) Find a recurrence relation for the number of steps needed to solve the Tower of Hanoi puzzle. b) Show how this recurrence relation can be solved using iteration.

a) Explain how to find a recurrence relation for the number of bit strings of length n not containing two consecutive Is. b) Describe another counting problem that has a solution satisfying the same recurrence relation.

Define a linear homogeneous recurrence relation of degree k.

a) Explain how to solve linear homogeneous recurrence relations of degree 2. b) Solve the recurrence relation an = 13an-l - 22an-2 for n 2 if ao = 3 and al = 15. c) Solve the recurrence relation an = 14an-l - 49an-2 for n 2 if ao = 3 and al = 35.

a) Explain how to find f(bk ) where k is a positive integer if f (n ) satisfies the divide-and-conquer recurrence relation f(n) = af(n / b) + g(n) whenever b divides the positive integer n. b) Findf(256) iff(n) = 3f(n/4) + 5n/4 and f(l) = 7.

a) Derive a divide-and-conquer recurrence relation for the number of comparisons used to find a number in a list using a binary search. b) Give a big-O estimate for the number of comparisons used by a binary search from the divide-and-conquer recurrence relation you gave in (a) using Theorem I in Section 7.3.

a) Give a formula for the number of elements in the union ofthree sets. b) Explain why this formula is valid. c) Explain how to use the formula from (a) to find the number of integers not exceeding 1000 that are divisible by 6, 10, or 15. d) Explain how to use the formula from (a) to find the number of solutions in nonnegative integers to the equation Xl + X2 + X3 + X4 = 22 with Xl < 8, X2 < 6, and x3 < 5.

a) Give a formula for the number of elements in the union of four sets and explain why it is valid. b) Suppose the sets AI , A2, A3 , and A4 each contain 25 elements, the intersection of any two ofthese sets contains 5 elements, the intersection of any three of these sets contains 2 elements, and 1 element is in all four of the sets. How many elements are in the union of the four sets?

a) State the principle of inclusion-exclusion. b) Outline a proof of this principle.

Explain how the principle of inclusion-exclusion can be used to count the number of onto functions from a set with m elements to a set with n elements.

a) How can you count the number of ways to assign m jobs to n employees so that each employee is assigned at least one job? b) How many ways are there to assign seven jobs to three employees so that each employee is assigned at least one job?

Explain how the inclusion-exclusion principle can be used to count the number of primes not exceeding the positive integer n.

a) Define a derangement. b) Why is counting the number of ways a hatcheck person can return hats to n people, so that no one receives the correct hat, the same as counting the number of derangements of n objects? c) Explain how to count the number of derangements of n objects.

A group of 10 people begin a chain letter, with each person sending the letter to four other people. Each ofthese people sends the letter to four additional people. a) Find a recurrence relation for the number of letters sent at the nth stage of this chain letter, if no person ever receives more than one letter. b) What are the initial conditions for the recurrence relation in part (a)? c) How many letters are sent at the nth stage of the chain letter?

A nuclear reactor has created 18 grams of a particular radioactive isotope. Every hour 1 % of a radioactive isotope decays. a) Set up a recurrence relation for the amount of this isotope left after n hours. b) What are the initial conditions for the recurrence relation in part (a)? c) Solve this recurrence relation.

Every hour the U.S. government prints 10,000 more $1 bills, 4000 more $5 bills, 3000 more $10 bills, 2500 more $20 bills, 1000 more $50 bills, and the same number of $100 bills as it did the previous hour. In the initial hour 1000 of each bill were produced. a) Set up a recurrence relation for the amount of money produced in the nth hour. b) What are the initial conditions for the recurrence relation in part (a)? c) Solve the recurrence relation for the amount of money produced in the nth hour. d) Set up a recurrence relation for the total amount of money produced in the first n hours. e) Solve the recurrence relation for the total amount of money produced in the first n hours.

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?

Messages are sent over a communications channel using two different signals. One signal requires 2 microseconds for transmittal, and the other signal requires 3 microseconds for transmittal. Each signal of a message is followed immediately by the next signal. a) Find a recurrence relation for the number of different signals that can be sent in n microseconds. b) What are the initial conditions of the recurrence relation in part (a)? c) How many different messages can be sent in 12 microseconds?

A small post office has only 4-cent stamps, 6-cent stamps, and 10-cent stamps. Find a recurrence relation for the number of ways to form postage of n cents with these stamps if the order that the stamps are used matters. What are the initial conditions for this recurrence relation?

How many ways are there to form these postages using the rules described in Exercise 6? a) 12 cents b) 14 cents c) 18 cents d) 22 cents

Find the solutions of the simultaneous system of congruences an = an-I + bn-I bn = an-I - bn-I with ao = 1 and bo = 2.

Solve the recurrence relation an = a_dan-2 if ao = 1 and al = 2. [Hint: Take logarithms of both sides to obtain a recurrence relation for the sequence log an, n = 0, 1 , 2, ... .

Solvetherecurrencerelation an = a_l a_2 ifao = 2 and al = 2. (See the hint for Exercise 9.)

Find the solution of the recurrence relation an = 3an -1 - 3an -2 + an-3 + 1 if ao = 2, al = 4, and a2 = 8.

Find the solution ofthe recurrence relation an = 3an-1 - 3an-2 + an-3 if ao = 2, al = 2, and a2 = 4.

Suppose that in Example 4 of Section 7. l a pair of rabbits leaves the island after reproducing twice. Find a recurrence relation for the number of rabbits on the island in the middle of the nth month.

Find the solution to the recurrence relation f(n) = 3f(nI5) + 2n\ when n is divisible by 5, for n = 5k, where k is a positive integer and f(l) = 1 .

Estimate the size of f in Exercise 14 if f is an increasing function.

Find a recurrence relation that describes the number of comparisons used by the following algorithm: Find the largest and second largest elements of a sequence of n numbers recursively by splitting the sequence into two subsequences with an equal number of terms, or where there is one more term in one subsequence than in the other, at each stage. Stop when subsequences with two terms are reached.

Estimate the number of comparisons used by the algorithm described in Exercise 16.

Find flan, where a) an = 3. b) an = 4n + 7. c) an = n 2 + n + 1 .

Let an = 3n3 + n + 2. Find flkan, where k equals a) 2. b) 3. c) 4.

Suppose that an = P(n), where P is a polynomial of degree d. Prove that fld+ l an = 0 for all nonnegative integers n.

Let {an } and Ibn } be sequences of real numbers. Show that fl(anbn) = an+ l (flbn) + bn(flan).

Show that if F(x) and G(x) are the generating functions for the sequences {ad and {bk }, respectively, and c and d are real numbers, then (cF + dG )(x) is the generating function for {cak + dbd.

(Requires calculus) This exercise shows how generating functions can be used to solve the recurrence relation (n + l )an+1 = an + (lin !) for n ::: 0 with initial condition ao = 1 . a) Let G(x) be the generating function for {an}. Show that G'(x) = G(x) + eX and G (O) = 1 . b) Show from part (a) that (e - xG(x ' = 1, and conclude that G(x) = xex + eX. c) Use part (b) to find a closed form for an .

Suppose that 14 students receive an A on the first exam in a discrete mathematics class, and 18 receive an A on the second exam. If 22 students received an A on either the first exam or the second exam, how many students received an A on both exams?

There are 323 farms in Monmouth County that have at least one of horses, cows, and sheep. If 224 have horses, 85 have cows, 57 have sheep, and 18 farms have all three types of animals, how many farms have exactly two of these three types of animals?

Queries to a database of student records at a college produced the following data: There are 2175 students at the college, 1675 of these are not freshmen, 1074 students have taken a course in calculus, 444 students have taken a course in discrete mathematics, 607 students are not freshmen and have taken calculus, 350 students have taken calculus and discrete mathematics, 201 students are not freshmen and have taken discrete mathematics, and 143 students are not freshmen and have taken both calculus and discrete mathematics. Can all the responses to the queries be correct?

Students in the school of mathematics at a university major in one or more of the following four areas: applied mathematics (AM), pure mathematics (PM), operations research (OR), and computer science (CS). How many students are in this school if(includingjoint majors) there are 23 students majoring in AM; 17 students majoring in PM; 44 in OR; 63 in CS; 5 in AM and PM; 8 in AM and CS; 4 in AM and OR; 6 in PM and CS; 5 in PM and OR; 14 in OR and CS; 2 in PM, OR, and CS; 2 in AM, OR, and CS; 1 in PM, AM, and OR; 1 in PM, AM, and CS; and 1 in all four fields.

How many terms are needed when the inclusionexclusion principle is used to express the number of elements in the union of seven sets if no more than five of these sets have a common element?

How many solutions in positive integers are there to the equation Xl + X2 + X3 = 20 with 2 < Xl < 6, 6 < Xz < 10, and 0 < X3 < 5?

How many positive integers less than 1,000,000 are a) divisible by 2, 3, or 5? b) not divisible by 7, 1 1 , or 13? c) divisible by 3 but not by 7?

How many positive integers less than 200 are a) second or higher powers of integers? b) either second or higher powers of integers or primes? c) not divisible by the square of an integer greater than I? d) not divisible by the cube of an integer greater than I? e) not divisible by three or more primes?

How many ways are there to assign six different jobs to three different employees if the hardest job is assigned to the most experienced employee and the easiest job is assigned to the least experienced employee?

What is the probability that exactly one person is given back the correct hat by a hatcheck person who gives n people their hats back at random?

How many bit strings of length six do not contain four consecutive Is?

What is the probability that a bit string oflength six contains at least four Is?

Given a positive integer n, list all the moves required in the Tower of Hanoi puzzle to move n disks from one peg to another according to the rules of the puzzle.

Given a positive integer n and an integer k with I :s k :s n, list all the moves used by the Frame-Stewart algorithm (described in the preamble to Exercise 54 of Section 7. 1) to move n disks from one peg to another using four pegs according to the rules of the puzzle.

Given a positive integer n, list all the bit sequences of length n that do not have a pair of consecutive Os.

Given a positive integer n, write out all ways to parenthesize the product of n + I variables.

Given a recurrence relation an = Clan-l + C2an-2, where Cl and C2 are real numbers, initial conditions ao = Co and a 1 = C l , and a positive integer k, find ak using iteration.

Given a recurrence relationan = Clan-l + C2an-2 and initial conditions ao = Co and al = C l, determine the unique solution.

Given arecurrencerelation oftheform/(n) = al(n/b) + c, where a is a real number, b is a positive integer, and C is a real number, and a positive integer k, find I(bk) using iteration.

Given the number of elements in the intersection of three sets, the number of elements in each pairwise intersection of these sets, and the number of elements in each set, find the number of elements in their union.

Given a positive integer n, produce the formula for the number of elements in the union of n sets.

Given positive integers m and n, find the number of onto functions from a set with m elements to a set with n elements.

Given a positive integer n, list all the derangements of the set {I, 2, 3, ... , n}.

Find the exact value of 1100, 1500, and 11000, where In is the nth Fibonacci number

Find the smallest Fibonacci number greater than 1,000,000, greater than 1,000,000,000, and greater than 1,000,000,000,000.

Find as many prime Fibonacci numbers as you can. It is unknown whether there are infinitely many of these.

Write out all the moves required to solve the Tower of Hanoi puzzle with 10 disks.

Write out all the moves required to use the Frame-Stewart algorithm to move 20 disks from one peg to another peg using four pegs according to the rules of the Reve's pUzzle.

Verify the Frame conjecture for solving the Reve's puzzle for n disks for as many integers n as possible by showing that the puzzle cannot be solved using fewer moves than are made by the Frame-Stewart algorithm with the optimal choice of k.

Compute the number of operations required to multiply two integers with n bits for various integers n including 16, 64, 256, and 1024 using the fast multiplication described in Section 7.3 and the standard algorithm for multiplying integers (Algorithm 3 in Section 3.6).

Compute the number of operations required to multiply two n x n matrices for various integers n including 4, 16, 64, and 128 using the fast matrix multiplication described in Section 7.3 and the standard algorithm for multiplying matrices (Algorithm 1 in Section 3.8).

Use the sieve of Eratosthenes to find all the primes not exceeding 1000.

Find the number of primes not exceeding 10,000 using the method described in Section 7.6 to find the number of primes not exceeding 100.

List all the derangements of {I, 2, 3, 4, 5, 6, 7, 8} .

Compute the probability that a permutation of n objects is a derangement for all positive integers not exceeding 20 and determine how quickly these probabilities approach the number e.

Find the original source where Fibonacci presented his puzzle about modeling rabbit populations. Discuss this problem and other problems posed by Fibonacci and give some information about Fibonacci himself.

Explain how the Fibonacci numbers arise in a variety of applications, such as in phyllotaxis, the study of arrangement of leaves in plants, in the study of reflections by mirrors, and so on.

Describe different variations of the Tower of Hanoi puzzle, including those with more than three pegs (including the Reve's puzzle discussed in the text and exercises), those where disk moves are restricted, and those where disks may have the same size. Include what is known about the number of moves required to solve each variation

Discuss as many different problems as possible where the Catalan numbers arise.

Describe the solution of Ulam's problem (see Exercise 28 in Section 7.3) involving searching with one lie found by Andrzej Pe1c.

Discuss variations ofUlam's problem (see Exercise 28 in Section 7.3) involving searching with more than one lie and what is known about this problem.

Define the convex hull ofa set of points in the plane and describe divide-and-conquer algorithms for finding the convex hull of a set of points in the plane.

Look up the definition of the lucky numbers. Explain how they are found using a sieve technique similar to the sieve of Eratosthenes. Find all the lucky numbers less than 1000.

Describe how sieve methods are used in number theory. What kind of results have been established using such methods?

Look up the rules of the old French card game ofrencontres. Describe these rules and describe the work of Pierre Raymond de Montmort on Ie probleme de rencontres.

Describe how exponential generating functions can be used to solve a variety of counting problems.

Describe the Polyci theory of counting and the kind of counting problems that can be solved using this theory.

The probleme des menages (the problem of the households) asks for the number of ways to arrange n couples around a table so that the sexes alternate and no husband and wife are seated together. Explain the method used by E. Lucas to solve this problem.

Explain how rook polynomials can be used to solve counting problems.