Okay so I am trying to understand modifications to the famous fibonacci rabbit problems so I can make a generalized website for it as a pet project, where people just need to input paramaters and it will generate the tree like structure and the recurrence relation if possible.
One pair of rabbits is left in an island. At the age of 3 months it produces 1 pairs of rabbit, and then every 2 months they produce 2 pairs of rabbits and no rabbits die.
I'm able to generate the tree like structure for it just fine. However, what will be the recurrence relation for it for the number of rabbits produced at nth month?
Moreover is there a nice way to generalize this? Would appreciate some help over here.
EDIT: The children follow the same pattern. They produce one pair at the age of 3 months and then two pairs every 2 months.
Best Answer
This is a bit complicated because you need to keep track of how many pairs were born in odd numbered months and how many were born in even numbered months. You can make a pair of coupled recurrences. Let $A(n)$ be the number alive in month $n$ that were born in an even numbered month and $B(n)$ the number alive in month $n$ that were born in an odd numbered month.
The first pair was born in month $0$, so $A(1)=1,A(2)=1,A(3)=1,B(0)=B(1)=B(2)=0,B(3)=1$
In an odd numbered month there are no even births, so $A(2n+1)=A(2n)$. Similarly $B(2n)=B(2n-1)$.
In month $2n$ we get one pair from every $B$ pair alive $3$ months ago and an additional pair from the $B$ pairs alive $5$ months ago, so $A(2n)=A(2n-1)+B(2n-3)+B(2n-5)$. Similarly $B(2n+1)=B(2n)+A(2n-2)+A(2n-4)$
The total number alive at month $n$ is $A(n)+B(n)$
You can substitute in to separate the two recurrences at the price of a longer tail: $$A(2n)=A(2n-1)+A(2n-6)+2A(2n-8)+A(2n-10)\\B(2n+1)=B(2n)+B(2n-5)+2B(2n-7)+B(2n-9)$$ The asymptotic growth goes about as $1.40835^n$. You can read about recurrence relations to see where this comes from.