91Ó°ÊÓ

Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are. $$ \begin{array}{ll}{\text { a) } a_{n}=3 a_{n-1}+4 a_{n-2}+5 a_{n-3}} \\ {\text { b) } a_{n}=2 n a_{n-1}+a_{n-2}} & {\text { c) } a_{n}=a_{n-1}+a_{n-4}} \\\ {\text { d) } a_{n}=a_{n-1}+2} & {\text { e) } a_{n}=a_{n-1}^{2}+a_{n-2}} \\\ {\text { f) } a_{n}=a_{n-2}} & {\text { g) } a_{n}=a_{n-1}+n}\end{array} $$

How many elements are in \(A_{1} \cup A_{2}\) if there are 12 elements in \(A_{1}, 18\) elements in \(A_{2},\) and $$ \begin{array}{ll}{\text { a) } A_{1} \cap A_{2}=\emptyset ?} & {\text { b) }\left|A_{1} \cap A_{2}\right|=1 ?} \\ {\text { c) }\left|A_{1} \cap A_{2}\right|=6 ?} & {\text { d) } A_{1} \subseteq A_{2} ?}\end{array} $$

How many comparisons are needed for a binary search in a set of 64 elements?

Find the generating function for the finite sequence \(2,2,\) \(2,2,2,2 .\)

Of 1000 applicants for a mountain-climbing trip in the Himalayas, 450 get altitude sickness, 622 are not in good enough shape, and 30 have allergies. An applicant qualifies if and only if this applicant does not get altitude sickness, is in good shape, and does not have allergies. If there are 111 applicants who get altitude sickness and are not in good enough shape, 14 who get altitude sickness and have allergies, 18 who are not in good enough shape and have allergies, and 9 who get altitude sickness, are not in good enough shape, and have allergies, how many applicants qualify?

a) Find a recurrence relation for the number of permutations of a set with n elements. b) Use this recurrence relation to find the number of permutations of a set with n elements using iteration.

A survey of households in the United States reveals that 96\(\%\) have at least one television set, 98\(\%\) have telephone service, and 95\(\%\) have telephone service and at least one television set. What percentage of households in the United States have neither telephone service nor a television set?

A vending machine dispensing books of stamps accepts only one-dollar coins, \(\$ 1\) bills, and \(\$ 5\) bills. a) Find a recurrence relation for the number of ways to deposit \(n\) dollars in the vending machine, where the order in which the coins and bills are deposited matters. b) What are the initial conditions? c) How many ways are there to deposit \(\$ 10\) for a book of stamps?

Find the number of elements in \(A_{1} \cup A_{2} \cup A_{3}\) if there are 100 elements in each set and if a) the sets are pairwise disjoint. b) there are 50 common elements in each pair of sets and no elements in all three sets. c) there are 50 common elements in each pair of sets and 25 elements in all three sets. d) the sets are equal.

An integer is called squarefree if it is not divisible by the square of a positive integer greater than \(1 .\) Find the number of squarefree positive integers less than 100 .