Rabbits and Recurrence Relations

The fourth Rosalind problem is a bit different than the previous ones. This time we are asked to calculate how many rabbit pairs there are after n months if every grown pair produces k new pairs each month and it takes one month for a new pair to become reproductive. The problem describes the Fibonacci sequence and how it can be applied to the simplest version of the problem, the case when k=1. It's been a while since I worked with mathematical sequences, so this was a fun way to dust of things I learned during my bachelor's maths courses.

The Fibonacci sequence works on this problem when k=1 and its recurrence relation is written as follows:

Fn = Fn-1 + Fn-2

The first thing I needed to do was to figure out the  recurrence relation for any value on k. After doodling a bit and playing around with the numbers I figured out that this must be it:

Fn = Fn-1 + Fn-2 * k

Once I knew this I wrote the following program:

n = 5                      

k = 3                      

big = 1                    

small = 1                  

for months in range(1,n-1):

      bigger = big + small*k   

      small = big              

      big = bigger             

print(big)                 

I named Fn-1 and Fn-2 big and small so that I wouldn't confuse myself which was the larger number and which was the smaller of the two. Since the problem states that F1 = 1 the program is set to only iterate n-1 times to reach the answer for Fn. The first expression in the for-loop calculates Fn. The other two terms update Fn-1 and Fn-2 in preparation of the next iteration.

I really liked this problem, mainly because it felt a bit more challenging than the previous three and because I got to practice some maths skills that I haven't used in a while. It took me a bit longer than the previous ones, about an hour, but most of that time I spent working on the recurrence relation and when I got to the coding part I managed to write the program pretty quickly and with little fuss.