Martian hares are hermaphrodite. Each mature Martian hare produces one leveret during each breeding cycle. Each leveret takes one breeding cycle to mature into a fully-grown hare, and then lives for ever. Starting with a single Martian leveret, how many hares (including leverets) are there after 47 breeding cycles?
This is the question I am posed with and I recognize that the breeding cycle follows the pattern of the Fibonacci sequence so I'm able to figure out the number after 47 breeding cycles but how do I go about proving that $M_n = M_{n-1}+M_{n-2}$?
Let there be $m(n)$ mature hares after cycle $n$ and $L(n)$ leverets. Then $m(n)=(n-1)+L(n-1)$ because the exising leverets become mature and the existing mature ones remain. $L(n)=m(n-1)$ because the new leverets come from existing mature hares. By definition $M_n=m(n)+L(n)$ $$\begin {align}M_n &=m(n)+L(n)\\ &=m(n-1)+L(n-1)+m(n-1)\\ &=m(n-1)+L(n-1)+m(n-2)+L(n-2)\\ &=M_{n-1}+M_{n-2} \end {align}$$