0

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?

Sakthi
  • 100

2 Answers2

2

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}$$

paw88789
  • 40,402
  • If someone has confusion as me, here $a_n$ calculates the number after three-month old ones leave when they have reproduced by $x_n=y_{n-1}+z_{n-1}$. So there are no three-month old ones. – An5Drama Dec 31 '23 at 09:52
0

Let $b_n$ be the number of actively breeding rabbit pairs on the island at month $n$. It's easy to see that this sequence satisfies $$ \tag{*} b_n = b_{n-2}+b_{n-3} $$

However, what was asked is the total number of rabbit pairs, whether they're currently breeding or not. Since every rabbit stay on the island for exactly three months, the current population equals the number of births in the previous three months, summed. So $$ a_n = b_{n-1} + b_{n-2} + b_{n-3} $$ .. or something like that, depending on whether we count newborn litters and/or rabbits that are just about to depart.

But this slight uncertainty doesn't really matter because in any case $(a_n)_n$ is a linear combination of shifted versions if the $(b_n)_n$ sequence. And because the recurrence $\text{(*)}$ is linear, this means that the $a_n$s will satisfy the same recurrence.

Thus to find the solution according to your favorite criteria for counting rabbits, you can simulate the first handful of months precisely, keeping track of how many rabbits of each age there are, and summing the ones you decide count. From that point onwards, you can just run the total population through the recurrence.

(In order to be sure to be clear of effect of the "artificial" placement of rabbits on the island on month 0, I would simulate by hand for 6 months -- 3 because that's the length of the recurrence of $b_n$ and 3 more to account for the maximum shift of $b$s that contribute to $a$. Careful thinking will probably be able to show that doing fewer cycles by hand is enough, but I would find it quicker just to do a few more cycles by hand than convincing myself that a shortcut analysis is actually correct).

hmakholm left over Monica
  • 286,031