91Ó°ÊÓ

Prove that McCarthy's 91 function equals 91 for all positive integers less than or equal to 101 .

A person borrows \(\$ 3,000\) on a bank credit card at a nominal rate of \(18 \%\) per year, which is actually charged at a rate of \(1.5 \%\) per month. a. What is the annual percentage rate (APR) for the card? (See Example 8.1.8 for a definition of APR.) b. Assume that the person does not place any additional charges on the card and pays the bank \(\$ 150\) each month to pay off the loan. Let \(B_{n}\) be the balance owed on the card after \(n\) months. Find an explicit formula for \(B_{n}\). c. How long will be required to pay off the debt? d. What is the total amount of money the person will have paid for the loan?

Compownd Interest: Suppose a certain amount of moncy is deposited in an account paying \(4 \%\) annual interest compounded quarterly. For each positive integer \(n\), let \(R_{n}=\) the amount on deposit at the end of the \(n\)th quarter, assuming no additional deposits or withdrawais, and let \(R_{0}\) be the initial amount deposited. a. Find a recurrence relation for \(R_{0}, R_{1}, R_{2}, \ldots\) b. If \(R_{0}=\$ 5000\), find the amount of money on deposit at the end of one year, c. Find the APR for the account.

For each integer \(n \geq 2\) let \(a_{n}\) be the number of permutations of \(\\{1,2,3, \ldots, n\\}\) in which no number is more than one place removed from its "natural" position. Thus \(a_{1}=1\) since the one permutation of \(\\{1\\}\), namely 1 , does not move 1 from its natural position. Also \(a_{2}=2\) since neither of the two permutations of \(\\{1,2\\}\), namely 12 and 21 , moves cither number more than one place from its natural position. a. Find \(a_{3}\). b. Find a recurrence relation for \(a_{1}, a_{2}, a_{3}, \ldots .\)

Refer to the sequence of Stirling numbers of the second kind. If \(X\) is a set with \(n\) elements and \(Y\) is a set with \(m\) elements, express the number of onto functions from \(X\) and \(Y\) using Stirling numbers of the second kind. Justify your answer.

Assume that \(F_{0}, F_{1}, F_{2}, \ldots\) is the Fibonacci sequence. Use strong mathematical induction to prove that \(F_{n}<2^{n}\) for all integers \(n \geq 1\).

A single line divides a plane into two regions. Two lines (by crossing) can divide a plane into four regions; three lines can divide it into seven regions (see the figure). Let \(P_{n}\) be the maximum number of regions into which \(n\) lines divide a plane, where \(n\) is a positive integer. a. Derive a recurrence relation for \(P_{k}\) in terms of \(P_{k-1}\), for all integers \(k \geq 2\). b. Use iteration to guess an explicit formula for \(P_{n}\).

A derangement of the set \(\\{1,2, \ldots, n\\}\) is a permutation that moves every element of the set away from its "natural" position. Thus 21 is a derangement of \(\\{1,2\\}\), and 231 and 312 are derangements of \(\\{1,2,3\\} .\) For each positive integer \(n\), let \(d_{n}\) be the number of derangements of the set \(\\{1,2, \ldots, n\\}\). a. Find \(d_{1}, d_{2}\), and \(d_{3}\). b. Find \(d_{4}\). \(\boldsymbol{H}\) c. Find a recurrence relation for \(d_{1}, d_{2}, d_{3}, \ldots\)