91Ó°ÊÓ

Tell whether or not each recurrence relation in Exercises \(1-10\) is a linear homogeneous recurrence relation with constant coefficients. Give the order of each linear homogeneous recurrence relation with constant coefficients. \(a_{n}=-3 a_{n-1}\)

Describe how the closest-pair algorithm finds the closest pair of points if the input is \((8,4),(3,11),(12,10),(5,4),(1,2),\) \((17,10),(8,7),(8,9),(11,3),(1,5),(11,7),(5,9),(1,9),(7,6),(3,7),(14,7).\)

In Exercises \(1-3\), find a recurrence relation and initial conditions that generate a sequence that begins with the given terms. $$ 1,1,2,4,16,128,4096, \ldots $$

In Exercises \(4-8,\) assume that a person invests \(\$ 2000\) at 14 percent interest compounded annually. Let \(A_{n}\) represent the amount at the end of \(n\) years. Find a recurrence relation for the sequence \(A_{0}, A_{1}, \ldots\)

In Exercises \(4-8,\) assume that a person invests \(\$ 2000\) at 14 percent interest compounded annually. Let \(A_{n}\) represent the amount at the end of \(n\) years. Find \(A_{1}, A_{2},\) and \(A_{3}\).

If a person invests in a tax-sheltered annuity, the money invested, as well as the interest earned, is not subject to taxation until with. drawn from the account. In Exercises \(9-12,\) assume that a person invest \(\$ 2000\) each year in a tax-sheltered annuity at 10 percent interest compounded annually. Let \(A_{n}\) represent the amount ar the end of \(n\) years. Find a recurrence relation for the sequence \(A_{0}, A_{1} \ldots \ldots\).

In exercises \(13-17,\) assume that a person invests \(\$ 3000\) at 12 per. cent annual interest compounded quarterly. Let \(A_{n}\) represent the amount at the end of \(n\) years. Find a recurrence relation for the sequence \(A_{0}, A_{1}, \ldots\).

List all inversions in the permutation 1,2,3,4 .

Show a permutation of \\{1,2,3,4\\} having the maximum number of inversions.

In Exercises 34 and 35 , let \(S_{n}\) denote the number of routes from the lower.left corner of an \(n \times n\) grid to the upper-right comer in which we are restricted to traveling to the right, upward, or diagonally northeast [i.e., from \((i, j)\) to \((i+1, j+1)]\) and in which we are allowed to touch but not go above a diagonal line from the lower. left corner to the upper-right comer. The numbers \(S_{0}, S_{1} \ldots .\) are called the Schroder numbers. Show that \(S_{0}=1, S_{1}=2, S_{2}=6,\) and \(S_{3}=22\)