11000 - Bee
There is a rather strange species of bee that reproduce in the following manner: the female bees each give birth to one male bee and then die. The male bees each give birth to a male bee and a female bee and then die. However, there is one immortal female bee that doesn't die after it gives birth.
Starting with only the immortal female bee, find the number of male bees and the total number of bees after n generations.
Using the notation M(n) = Number of males after n generations, and F(n) = Number of females after n generations, we can deduce the following relations by definition:
From (2) in (1), we can deduce that:
Also note that M(n - 1) is needed for M(n), and for F(n). Take care not to compute this value twice.
The problem asks you to output two numbers: the number of male bees and the total number of bees.
0 1 2 3 4 5 6 7 8 -1
0 1 1 2 2 4 4 7 7 12 12 20 20 33 33 54 54 88