91Ó°ÊÓ

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\).

Fibonacci Variation: A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions (which are more realistic than Fibonacci's): (1) Rabbit pairs are not fertile during their first month of life but thereafter give birth to four new male/female pairs at the end of every month. (2) No rabbits die. a. Let \(r_{n}=\) the number of pairs of rabbits alive at the end of month \(n\), for each integer \(n \geq 1\), and let \(r_{0}=1\). Find a recurrence relation for \(r_{0}, r_{1}, r_{2}, \ldots\) b. Compute \(r_{0}, r_{t}, r_{2}, r_{3}, r_{4}, r_{5}\), and \(r_{6}\) c. How many rabbits will there be at the end of the year?

The triangle inequality for absolute value states that for all real numbers \(a\) and \(b,|a+b| \leq|a|+|b|\). Use the recursive definition of summation, the triangle inequality, the definition of absolute value, and mathematical induction to prove that for all positive integers \(n\), if \(a_{1}, a_{2}, \ldots, a_{n}\) are real numbers, then $$ \left|\sum_{i=1}^{n} a_{i}\right| \leq \sum_{i=1}^{n}\left|a_{i}\right| $$

As shown in Example 8.1.8, if a bank pays interest at a rate of \(i\) compounded \(m\) times a year, then the amount of money \(P_{k}\) at the end of \(k\) time periods (where one time period \(=1 / m\) th of a year) satisfies the recurrence relation \(P_{k}=[1+(i / m)] P_{k-1}\) with initial condition \(P_{0}=\) the initial amount deposited. Find an explicit formula for \(P_{n}\).

Fibonacci Variation: A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions: (1) Rabbit pairs are not fertile during their first \(t\) wo months of life, but thereafter give birth to three new male/female pairs at the end of every month. (2) No rabbits die. a. Let \(s_{n}=\) the number of pairs of rabbits alive at the end of month \(n\), for each integer \(n \geq 1\), and let \(s_{0}=1\). Find a recurrence relation for \(s_{0}, s_{1}, s_{2} \ldots . .\) b. Compute \(s_{0}, s_{1}, s_{2}, s_{3}, s_{4}\), and \(s_{5}\). c. How many rabbits will there be at the end of the year? In \(24-32, F_{0}, F_{1}, F_{2}, \ldots\) is the Fibonacci sequence.

Suppose the population of a country increases at a steady rate of \(3 \%\) per year. If the population is 50 million at a certain time, what will it be 25 years later?

A chain letter works as follows: One person sends a copy of the letter to five friends, each of whom sends a copy to five friends, each of whom sends a copy to five friends, and so forth. How many people will have received copies of the letter after the twentieth repetition of this process, assuming no person receives more than one copy?

Use the recursive definitions of union and intersection to prove the following general De Morgan's law: For all positive integers \(n\), if \(A_{1}, A_{2}, \ldots, A_{n}\) are sets, then $$ \left(\bigcap_{i=1}^{n} A_{i}\right)^{c}=\bigcup_{i=1}^{n}\left(A_{i}\right)^{c} $$

The Fibonacci sequence satisfies the recurrence relation \(F_{k}=F_{k-1}+F_{k-2}\), for all integers \(k \geq 2\). a. Explain why the following is true; $$ F_{k+1}=F_{k}+F_{k-1} \quad \text { for all integers } k \geq 1 . $$ b. Write an equation expressing \(F_{k+2}\) in terms of \(F_{k+1}\) and \(F_{k-}\) c. Write an equation expressing \(F_{k+3}\) in terms of \(F_{k+2}\) and \(F_{k+1}\)

A circular disk is cut into \(n\) distinct sectors, each shaped like a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way that no two adjacent sectors are painted the same color. Let \(S_{n}\) be the number of ways to paint the disk. a. Find a recurrence relation for \(S_{k}\) in terms of \(S_{k-1}\) and \(S_{k-2}\) for each integer \(k \geq 4\). b. Find an explicit formula for \(S_{n}\) for \(n \geq 2\).