Fibonacci Variation: Find the Recurrence Relation

[Jim01]

Homework Statement

A single pair of rabbits (male and female) is born at the beginning of a year. Assume the following conditions:

(1) Rabbit pairs are not fertile during their first two months of life, but thereafter give birth to three new male/female pairs at the end of every month.

(2) No rabbits die

(a) Let S_n = the number of pairs of rabbits alive at the end of month n, for each ionterger n>=1, and let S₀ = 1. Find a recurrence relation for S₀, S₁, S₂, ...

Homework Equations

Original Fibonacci equation = F_n = F_k-1 + F_{k - 2}, where F₀ = 1 and F₁ = 1.

The Attempt at a Solution

I have drawn a genealogy chart to the 7th generation and have come up with

S₀ = 1,
S₁ = 1,
S₂ = 1,
S₃ = 4,
S₄ = 7,
S₅ = 10,
S₆ = 22,
S₇ = 43,

The problem is that I cannot figure out a way to come up with the equation which would give me the recurrence relation.

I tried doing F_n = F_k-1 + F_{k - 2} + F_{k - 3} +1, but that doesn't work unless n >= 3 and does not work past S₄. I've tried several other combinations as well but I can't figure it out.

Is this one of those problems where you just have to "see" the answer or is there a procedure I can use to get it?

 

[vela]

Explain how you calculated S₆ and S₇. That should give you a clue as to what the recurrence relation is.

 

[Jim01]

Explain how you calculated S₆ and S₇. That should give you a clue as to what the recurrence relation is.

I didn't calculate it. I drew it out. I was hoping that if I knew what what the various numbers were it would jump out at me. I was wrong. I know there is a pattern, and I know that the previous S numbers have something to do with it, I just can't see it. I'll keep working on it.

 

[vela]

The number 3 should appear in your recurrence relation somewhere because each pair produces 3 additional pairs every month.

Hint: Look at the increase from month to month and figure out how many pairs were responsible for that increase.