91Ó°ÊÓ

Find a formula for the probability of the union of \(n\) events in a sample space when no two of these events can occur at the same time.

In the Tower of Hanoi puzzle, suppose our goal is to transfer all \(n\) disks from peg 1 to peg \(3,\) but we cannot move a disk directly between pegs 1 and \(3 .\) Each move of a disk must be a move involving peg \(2 .\) As usual, we cannot place a disk on top of a smaller disk. a) Find a recurrence relation for the number of moves required to solve the puzzle for \(n\) disks with this added restriction. b) Solve this recurrence relation to find a formula for the number of moves required to solve the puzzle for \(n\) disks. c) How many different arrangements are there of the \(n\) disks on three pegs so that no disk is on top of a smaller disk? d) Show that every allowable arrangement of the \(n\) disks occurs in the solution of this variation of the puzzle.

Exercises 33–37 deal with a variation of the Josephus problem described by Graham, Knuth, and Patashnik in [GrKnPa94]. This problem is based on an account by the historian Flavius Josephus, who was part of a band of 41 Jewish rebels trapped in a cave by the Romans during the Jewish Roman war of the first century. The rebels preferred suicide to capture; they decided to form a circle and to repeatedly count off around the circle, killing every third rebel left alive. However, Josephus and another rebel did not want to be killed this way; they determined the positions where they should stand to be the last two rebels remaining alive. The variation we consider begins with n people, numbered 1 to n, standing around a circle. In each stage, every second person still left alive is eliminated until only one survives. We denote the number of the survivor by J(n). Determine the value of \(J(n)\) for each integer \(n\) with \(1 \leq\) \(n \leq 16 .\)

Use generating functions to solve the recurrence relation \(a_{k}=7 a_{k-1}\) with the initial condition \(a_{0}=5\)

Find the solution of the recurrence relation \(a_{n}=\) \(4 a_{n-1}-3 a_{n-2}+2^{n}+n+3\) with \(a_{0}=1\) and \(a_{1}=4 .\)

Use generating functions to solve the recurrence relation \(a_{k}=3 a_{k-1}+2\) with the initial condition \(a_{0}=1\)

(Calculus required) Let \(\left\\{C_{n}\right\\}\) be the sequence of Catalan numbers, that is, the solution to the recurrence relation \(C_{n}=\sum_{k=0}^{n-1} C_{k} C_{n-k-1}\) with \(C_{0}=C_{1}=1\) (see Example 5 in Section 8.1\()\) a) Show that if \(G(x)\) is the generating function for the sequence of Catalan numbers, then \(x G(x)^{2}-G(x)+\) \(1=0 .\) Conclude (using the initial conditions) that \(G(x)=(1-\sqrt{1-4 x}) /(2 x)\) b) Use Exercise 42 to conclude that $$ G(x)=\sum_{n=0}^{\infty} \frac{1}{n+1}\left(\begin{array}{c}{2 n} \\\ {n}\end{array}\right) x^{n} $$ so that $$ C_{n}=\frac{1}{n+1}\left(\begin{array}{c}{2 n} \\ {n}\end{array}\right) $$ c) Show that \(C_{n} \geq 2^{n-1}\) for all positive integers \(n\)

Exercises \(38-45\) involve the Reve's puzzle, the variation of the Tower of Hanoi puzzle with four pegs and \(n\) disks. Before presenting these exercises, we describe the Frame-Stewart algorithm for moving the disks from peg 1 to peg 4 so that no disk is ever on top of a smaller one. This algorithm, given the number of disks \(n\) as input, depends on a choice of an integer \(k\) with \(1 \leq k \leq n .\) When there is only one disk, move it from peg 1 to peg 4 and stop. For \(n>1\) , the algorithm proceeds recursively, using these three steps. Recursively move the stack of the \(n-k\) smallest disks from peg 1 to peg \(2,\) using all four pegs. Next move the stack of the \(k\) largest disks from peg 1 to peg \(4,\) using the three-peg algorithm from the Tower of Hanoi puzzle without using the peg holding the \(n-k\) smallest disks. Finally, recursively move the smallest \(n-k\) disks to peg \(4,\) using all four pegs. Frame and Stewart showed that to produce the fewest moves using their algorithm, \(k\) should be chosen to be the smallest integer such that \(n\) does not exceed \(t_{k}=k(k+1) / 2,\) the \(k\) th triangular number, that is, \(t_{k-1}

(Linear algebra required) Let \(\mathbf{A}_{n}\) be the \(n \times n\) matrix with 2 \(\mathrm{s}\) on its main diagonal, 1 \(\mathrm{s}\) in all positions next to a diagonal element, and 0 \(\mathrm{s}\) everywhere else. Find a recurrence relation for \(d_{n},\) the determinant of \(\mathbf{A}_{n} .\) Solve this recurrence relation to find a formula for \(d_{n} .\)

Use generating functions to prove Vandermonde's identity: \(C(m+n, r)=\sum_{k=0}^{r} C(m, r-k) C(n, k),\) whenever \(m, n,\) and \(r\) are nonnegative integers with \(r\) not exceeding either \(m\) or \(n .\left[\text { Hint: Look at the coefficient of } x^{r} \text { in }\right.\) both sides of \((1+x)^{m+n}=(1+x)^{m}(1+x)^{n} . ]\)