91Ó°ÊÓ

On the first day of a new year, Joseph deposits \(\$ 1000\) in an account that pays \(6 \%\) interest compounded monthly. At the beginning of each month he adds \(\$ 200\) to his account. If he continues to do this for the next four years (so that he makes 47 additional deposits of \(\$ 200\) ), how much will his account be worth exactly four years after he opened it?

Meredith borrows \(\$ 2500\), at \(12 \%\) compounded monthly, to buy a computer. If the loan is to be paid back over two years, what is his monthly payment?

For \(n \geq 0\), evenly distribute \(2 n\) points on the circumference of a circle, and label these points cyclically with the integers \(1,2,3, \ldots, 2 n\). Let \(a_{n}\) be the number of ways in which these \(2 n\) points can be paired off as \(n\) chords where no two chords intersect. (The case for \(n=3\) is shown in Fig. 10.23.) Find and solve a recurrence relation for \(a_{n}, n \geq 0\).

a) For \(n \geq 1\), let \(a_{n}\) count the number of binary strings of length \(n\), where there are no consecutive 1 's. Find and solve a recurrence relation for \(a_{n}\). b) For \(n \geq 1\), let \(b_{n}\) count the number of binary strings of length \(n\), where there are no consecutive 1's and the first and last bit of the string are not both 1 . Find and solve a recurrence relation for \(b_{n}\).

. Let \(F_{n}\) denote the \(n\)th Fibonacci number, for \(n \geq 0\), and let \(\alpha=(1+\sqrt{5}) / 2\). For \(n \geq 3\), prove that (a) \(F_{n}>\alpha^{n-2}\) and (b) \(F_{n}<\alpha^{n-1}\)

Consider ternary strings - that is, strings where \(0,1,2\) are the only symbols used. For \(n \geq 1\), let \(a_{n}\) count the number of ternary strings of length \(n\) where there are no consecutive 1 's and no consecutive \(2^{\prime} s\). Find and solve a recurrence relation for \(a_{n}\) -

For \(n \geq 1\), let \(a_{n}\) count the number of ways to tile a \(2 \times n\) chessboard using horizontal \((1 \times 2)\) dominoes [ which can also be used as vertical \((2 \times 1)\) dominoes] and square \((2 \times 2)\) tiles. Find and solve a recurrence relation for \(a_{n}\).