91Ó°ÊÓ

Solve the following recurrence relations by the method of generating functions. a) \(a_{n+1}-a_{n}=3^{n}, \quad n \geq 0, a_{0}=1\) b) \(a_{n+1}-a_{n}=n^{2}, \quad n \geq 0, a_{0}=1\) c) \(a_{n}-3 a_{n-1}=5^{n-1}, \quad n \geq 1, \quad a_{0}=1\) d) \(a_{n+2}-3 a_{n+1}+2 a_{n}=0, \quad n \geq 0, \quad a_{0}=1, \quad a_{1}=6\) e) \(a_{n+2}-2 a_{n+1}+a_{n}=2^{n}, \quad n \geq 0, a_{0}=1, a_{1}=2\)

Find a recurrence relation, with initial condition, that uniquely determines each of the following geometric progressions. a) \(2,10,50,250, \ldots\) b) \(6,-18,54,-162, \ldots\) c) \(1,1 / 3,1 / 9,1 / 27, \ldots\) d) \(7,14 / 5,28 / 25,56 / 125, \ldots\)

Let \(n, k \in \mathbf{Z}^{+}\), and define \(p(n, k)\) to be the number of partitions of \(n\) into exactly \(k\) (positive integer) summands. Prove that \(p(n, k)=p(n-1, k-1)+\) \(p(n-k, k)\).

The number of bacteria in a culture is 1000 (approximately), and this number increases \(250 \%\) every two hours. Use a recurrence relation to determine the number of bacteria present after one day.

Find and solve a recurrence relation for the number of ways to park motorcycles and compact cars in a row of \(n\) spaces if each cycle requires one space and each compact needs two. (All cycles are identical in appearance, as are the cars, and we want to use up all the \(n\) spaces.)

Consider a tennis tournament for \(n\) players, where \(n=2^{k}, k \in \mathbf{Z}^{+}\). In the first round \(n / 2\) matches are played, and the \(n / 2\) winners advance to round 2 , where \(n / 4\) matches are played. This halving process continues until a winner is determined. a) For \(n=2^{k}, k \in \mathbf{Z}^{+}\), let \(f(n)\) count the total number of matches played in the tournament. Find and solve a recurrence relation for \(f(n)\) of the form $$ \begin{aligned} &f(1)=d \\ &f(n)=a f(n / 2)+c, \quad n=2,4,8, \ldots, \end{aligned} $$ where \(a, c\), and \(d\) are constants. b) Show that your answer in part (a) also solves the recurrence relation $$ \begin{aligned} &f(1)=d \\ &f(n)=f(n / 2)+(n / 2), \quad n=2,4,8, \ldots \end{aligned} $$

Solve the following recurrence relations. a) \(a_{n+2}+3 a_{n+1}+2 a_{n}=3^{n}, \quad n \geq 0, a_{0}=0, a_{1}=1\) b) \(a_{n+2}+4 a_{n+1}+4 a_{n}=7, \quad n \geq 0, \quad a_{0}=1, a_{1}=2\) c) \(a_{n+2}-a_{n}=\sin (n \pi / 2), \quad n \geq 0, a_{0}=1, a_{1}=1\)

Paul invested the stock profits he received 15 years ago in an account that paid \(8 \%\) interest compounded quarterly. If his account now has \(\$ 7218.27\) in it, what was his initial investment?

For \(n \in \mathbf{Z}^{+}, d_{n}\) denotes the number of derangements of \(\\{1,2,3, \ldots, n\\}\), as discussed in Section \(8.3\). a) If \(n>2\), show that \(d_{n}\) satisfies the recurrence relation $$ d_{n}=(n-1)\left(d_{n-1}+d_{n-2}\right), \quad d_{2}=1, \quad d_{1}=0 . $$ b) How can we define \(d_{0}\) so that the result in part (a) is valid for \(n \geq 2 ?\) c) Rewrite the result in part (a) as \(d_{n}-n d_{n-1}=\) \(-\left[d_{n-1}-(n-1) d_{n-2}\right]\). How can \(d_{n}-n d_{n-1}\) be expressed in terms of \(d_{n-2}, d_{n-3}\) ? d) Show that \(d_{n}-n d_{n-1}=(-1)^{n}\). e) Let \(f(x)=\sum_{n=1}^{\infty}\left(d_{n} x^{n}\right) / n !\). After multiplying both sides of the equation in part (d) by \(x^{n} / n\) ! and summing for \(n \geq 2\), verify that \(f(x)=\left(e^{-x}\right) /\) \((1-x)\). Hence $$ d_{n}=n !\left[1-\frac{1}{1 !}+\frac{1}{2 !}-\frac{1}{3 !}+\cdots+\frac{(-1)^{n}}{n !}\right] $$

A particle moves horizontally to the right. For \(n \in \mathbf{Z}^{+}\), the distance the particle travels in the \((n+1)\) st second is equal to twice the distance it travels during the \(n\)th second. If \(x_{n}, n \geq 0\), denotes the position of the particle at the start of the \((n+1)\) st second, find and solve a recurrence relation for \(x_{n}\), where \(x_{0}=1\) and \(x_{1}=5\).