
\problemdata     
{S01-PS6-7}           
{Recurrences}              
{S01-PS6} 		
{S01 Karger}


\begin{problem}


On a certain far away island, all men are either blond or
brown-haired. Studies show that each man has four sons. Every blond
father has exactly three blond sons, while every brown-haired man
has exactly two brown-haired sons.

\begin{problemparts}
\problempart

Let $a_n$ and $b_n$ denote the number of blond and
brown-haired men, respectively, in the $n$th generation. Write a
system of recurrences for $a_n$ and $b_n$.

\solution{
\begin{equation*}
\begin{split}
a_n &= 3 a_{n-1} + 2 b_{n-1},\\
b_n &= a_{n-1} + 2 b_{n-1}.
\end{split}
\end{equation*}
}

\problempart

For which values of $c\ne 0$ and $d$ will we have a
solution of the form $a_n = c^n$, $b_n = d c^n$?

\solution{ Assume $a_n = c^n$ and $b_n = d c^n$ for some $c\ne 0$
and $d$. Let's substitute this into the system of recurrences.
We will obtain the equations
\begin{align*}
c^n &= 3 c^{n-1} + 2 d c^{n-1},\\
d c^n &= c^{n-1} + 2 d c^{n-1}.
\end{align*}
Dividing out $c^{n-1}$ (which is allowed, since $c\ne 0$), we
obtain
\begin{equation}
\label{eq:de}
\begin{split}
c &= 3 + 2 d,\\
d c &= 1 + 2 d.
\end{split}
\end{equation}
Multiplying both sides of the first equation by $d$ and
subtracting the second equation, we obtain
\begin{equation*}
0 = 3 d + 2 d^2 - 1 - 2d = 2 d^2 + d - 1.
\end{equation*}
Solving the quadratic equation, we obtain $d \in \{-1,
\frac{1}{2}\}$. Substituting into~\eqref{eq:de}, we obtain the
solutions
\begin{alignat*}{2}
c &= 1, \quad &d &= -1;\\
c &= 4, \quad &d &= \frac{1}{2}.
\end{alignat*}
}


\problempart
 Show that there exist values for $c_1$, $c_2$, $d_1$,
and $d_2$ such that
\begin{equation*}
\begin{split}
a_n &= x c_1^n + y c_2^n,\\
b_n &= x d_1 c_1^n + y d_2 c_2^n,
\end{split}
\end{equation*}
is a solution for all $x$ and $y$.

\solution{ Let $c_1 = 1$, $d_1 = -1$, $c_2 = 4$, $d_2 =
\frac{1}{2}$ (i.e., the two pairs of $c$ and $d$ that were
obtained in part~(a)).  From part~(a) we know that $a_n =
c_i^n$, $b_n = d_i c_i^n$ is a solution to the recurrences, for
each $i\in \{1, 2\}$. It is easy to verify that a constant
multiple of a solution is a solution, and that a sum of two
solutions is a solution.  }

\problempart

Suppose in the first generation there were ten blond
and twenty brown-haired men on the island. How many of each
group will there be in the $n$th generation?

\solution{We have $a_1 = 10$, $b_1 = 20$. Let's find $x$ and $y$
such that a solution in the form of part~(d) would satisfy these
initial conditions. We have
\begin{align*}
10 &= x \cdot 1^1 + y \cdot 4^1,\\
20 &= x \cdot (-1) \cdot 1^1 + y \cdot \frac{1}{2} \cdot 4^1,
\end{align*}
which can be rewritten as
\begin{align*}
10 &= x + 4 y,\\
20 &= -x + 2 y.
\end{align*}
This gives $x = -10$ and $y = 5$.

Thus the solution is
\begin{align*}
a_n &= -10 + 5 \cdot 4^n,\\
b_n &= 10 + \frac{5}{2} \cdot 4^n.
\end{align*}
}
\end{problemparts}

\end{problem}