A young pair of rabbits (one of each sex) is placed on an island.
A pair of rabbits does not breed until they are 2 months old.
After they are 2 months old, each pair of rabbits produces another pair each month.
And the pairs leave the island after reproducing twice.
Find a recurrence relation for the number of pairs of rabbits on the island after n months.
Let $a_n$ be the number of pairs of rabbits on the island after $n$ months.
Answer in the book: $a_n=a_{n-2}+a_{n-3}$
I counted the population for the first nine months $a_0=1, a_1=1, a_2=2, a_3=2, a_4=3, a_5=4, a_6=5, a_7=7, a_8=9, a_9=12$ and see that the recurrence relation in the book satisfies these values.
But I can't understand the solution. Can someone please explain the logic?
Best Answer
I think you have to keep track of number of rabbits by age:
Let $x_i, y_i, z_i$ be the number of pairs of newborn, pairs of one-month old, and pairs of two-month old rabbits respectively after $i$ months. Pairs in category $y_i$ and $z_i$ produce new pairs (counted in $x_{i+1}$). After being counted in $z_i$, a pair leaves the island and is not counted in the next iteration.
Let $\vec{v_i}=\begin{pmatrix} x_i \\y_i\\z_i \end{pmatrix}$
Initial conditions are
$\vec{v_0}=\begin{pmatrix} 1 \\0\\0 \end{pmatrix}$.
For $n\ge 1$, we have
$x_n=y_{n-1}+z_{n-1}$;
$y_n=x_{n-1}$, and
$z_n=y_{n-1}$
Note that this gives $\vec{v_1}=\begin{pmatrix} 0 \\1\\0 \end{pmatrix}$ and $\vec{v_2}=\begin{pmatrix} 1 \\0\\1 \end{pmatrix}$.
Then the total number of rabbits after $n$ months, for $n\ge 3$ is given by: $$\begin{array}{ccccccc}a_n&=&x_n&+&y_n&+&z_n\\&=&(y_{n-1}+z_{n-1})&+&x_{n-1}&+&y_{n-1}\\ &=&(x_{n-2}+y_{n-2})&+&(y_{n-2}+z_{n-2})&+&x_{n-2}\\ &=&(x_{n-2}+y_{n-2})&+&(x_{n-3}+z_{n-2})&+&(y_{n-3}+z_{n-3})\\&=& a_{n-2}+a_{n-3} \end{array}$$