91Ó°ÊÓ

Find the first four terms of each of the recursively defined sequences in 1-8. \(u_{k}=k u_{k-1}-u_{k-2}\), for all integers \(k \geq 3\) \(u_{1}=1, u_{2}=1\)

Let \(b_{0}, b_{1}, b_{2}, \ldots\) be defined by the formula \(b_{n}=4^{n}\), for all integers \(n \geq 0 .\) Show that this sequence satisfies the recurrence relation \(b_{k}=4 b_{k-1}\), for all integers \(k \geq 1\).

Define a set \(S\) recursively as follows: I. BASE: \(0 \in S, 5 \in S\) II. RECURSION: If \(s \in S\) and \(t \in S\) then a. \(s+t \in S\) b. \(s-t \in S\) III. RESTRICTION: Nothing is in \(S\) other than objects defined in I and II above. Use structural induction to prove that every integer in \(S\) is divisible by 5 .

Give a recursive definition for the set of all strings of 0 's and 1's that have the same number of 0's as 1's.

Give a recursive definition for the set of all strings of \(a\) 's and \(b\) 's that contain an odd number of \(a\) 's.

Tower of Hanoi with Adjacency Requirement: Suppose that in addition to the requirement that they never move a larger disk on top of a smaller one, the priests who move the disks of the Tower of Hanoi are also allowed only to move disks one by one from one pole to an adjacent pole. Assume poles \(A\) and \(C\) are at the two ends of the row and pole \(B\) is in the middle. Let \(a_{n}=\left[\begin{array}{l}\text { the minimum number of moves } \\ \text { needed to transfer a tower of } n \\ \text { disks from pole } A \text { to pole } C\end{array}\right] .\) a. Find \(a_{\mathrm{r}}, a_{2}\), and \(a_{3}, \quad\) b. Find \(a_{4}\). c. Find a recurrence relation for \(a_{1}, a_{2}, a_{3} \ldots \ldots\)

Use the recursive definition of summation, together with mathematical induction, to prove the generalized distributive law that for all positive integers \(n\), if \(a_{1}, a_{2}, \ldots, a_{n}\) and \(c\) are real numbers, then $$ \sum_{i=1}^{n} c a_{i}=c\left(\sum_{i=1}^{n} a_{i}\right) . $$

Four-Pole Tower of Hanoi: Suppose that the Tower of Hanoi problem has four poles in a row instead of three. Disks can be transferred one by one from one pole to any other pole, but at no time may a larger disk be placed on top of a smaller disk. Let \(s_{n}\) be the minimum number of moves needed to transfer the entire tower of \(n\) disks from the left-most to the right-most pole. a. Find \(s_{1}, s_{2}\), and \(s_{3}\). b. Find \(s_{4}\) c. Show that \(s_{k} \leq 2 s_{k-2}+3\) for all integers \(k \geq 3\).

A runner targets herself to improve her time on a certain course by 3 seconds a day. If on day 0 she runs the course in 3 minutes, how fast must she run it on day 14 to stay on target?

Suppose \(r\) is a fixed constant and \(a_{0}, a_{1}, a_{2} \ldots\) is a sequence that satisfies the recurrence relation \(a_{k}=r a_{k-1}\), for all integers \(k \geq 1\) and \(a_{0}=a\). Use mathematical induction to prove that \(a_{n}=a r^{n}\), for all integers \(n \geq 0\).