Fibonacci's question, recurance relationship, did i get it?

[mr_coffee]

Hello everyone, I'm having troubles finding hte recurance relationshiop of this modified Fibonacci's question.

The question is the following:
A single pair of rabbits (male and female) is born at the beginning of a year. Assume the folowing conditions:
1. Rabbit pairs are not fertile during their first 2 months of life, but therearfter give birth to 3 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 integer n>=1, and let s_0 = 1. Find a reuccrence relation for s_0, s_1, s_2...

c. How many rabbits will there be at the end of the year?
answer: 904 rabbit pairs or 1,808 rabits after 12 months.

Well I looked at the orginal Fibonacci's question for a basis:
The orginal question was under the following conditions:
1. Rabbit pairs are not fertile during their 1st month of life, but therearfter give birth to 1 new male/female pairs at the end of every month.
2. No rabbits die.

How many rabits will there be at the end of the year?
Solution:
The crucial observation is that the number of rabbit pairs born at the end of month k is the same as the number of pairs alive at the end of month k-2. Why? Because it is exactly the rabbit pairs that were alive at the end of month k-2 that were fertile during month k. The rabbits born at the end of month k-1 were not.
so at month k-2, each pair alive
at month k-1 nothing
at month k-2 gives birth to a pair here
F_0 = the intial number of rabbit paris = 1
and F_1 = 1 also, becuase the first apir of rabbits is not fertile until the 2nd month. Hence the complete specification of the Fibbonacci sequence for all integers k >= 2,
(1) F_k = F_k-1 + F_k-2
(2) F_0 = 1, F_1 = 1

Okay now back to my problem,

The number of rabbits alive at the end of the first month is still 1, so S_0 = 1;
Now it won't be another 2 months after the first month until they are fertile, so at the end of month 1 they still will only have 1 pair, so S_1 = 1, and also at month 2, they still havn't mated, so S_2 = 1, but now they can mate at month 2, so at month 3 (S_3) this is where the babies start popping out. So if its 3 new male/females, I would just take
3*S_1 right?

S_3 = S_0 + 3*S_1
S_4 = S_1 + 3*S_2
S_5 = S_2 + 3*S_3
...
...
S_k = S_k-3 + 3*S_k-2

Does that look right for the recurance relationship?

Thanks

Thanks!

 

[arildno]

No, it doesn't!

Think as follows:
At end of month k, then the number of pairs of rabbits must equal the number of pairs of rabbits in the previous month (since none of these rabbits have died), plus how many were born within month k (these are new rabbit. pairs, not included in the previous month's tally).

 

[Office_Shredder]

arildno, that's what he did. the number of new rabbit pairs is 3 times the number of new rabbit pairs that have been alive for 2 months

 

[arildno]

Of course.
However, the number alive the previous month is S_k-1, not S_k-3.

 

[mr_coffee]

ahh i c what your saying now, I was thinking it was skipping 3 months evrytime, but that's not the case, they just arnt' fertile during the first 2 months, so would it now be:
S_{k} = S_{k-1} + 3*S_{k-2}

 

[arildno]

Quite so!

 

[mr_coffee]

thanks a ton!

 

[arildno]

thanks a ton!

I'm overwhelmed. Please remove the last 5 ounces.

 

[mr_coffee]

I was double checking my work and I might have misunderstood or somthing isn't right.

i'm using:
S_{k} = S_{k-1} + 3*S_{k-2}
with S_{0} = 1 and S_{1} = 1

The back of the book said:
The number of pairs after 12 months is 904 or 1,808 rabits

But after doing the calculations for 12 months I'm getting a a lot bigger number, i stopped at S_{10} because i was getting 2683 pairs.

S_2 = S_1 + 3*S_0 = 1 + 3 = 4
S_3 = S_2 + 3*S_1= 4 + 3(1) = 7
S_4 = S_3 + 3*S_2= 7 + 3(4) = 19
...
...
...
S_{10} = S_9 + 3*S_8= 1159 + 3*508 = 2683

Any ideas? Thanks!

 

[arildno]

Use S_k-3 instead of S_k-2, then.

 

[mr_coffee]

I also thought that but then say your trying to find
S_2, would u end up with
S_2 = S_1 + 3*S_{-1}
but what's S_{-1} defined as? because there is no month, {-1}

or do i need 3 base cases?
S_0 = 1, S_1 = 1, and S_2 = 1?
then for all integers k >= 3

 

[arildno]

Then you would have:
1=S_2=S_1+3S_-1, by which follows that S_-1=0
Also,
S_1=S_0++3S_-2, by which follows that S_-2=0

Furthermore, we must set S_-3=1, and so on, if we are to extend the recursion relation backwards in time (little physical interpretation!).

 

[OlderDan]

I was double checking my work and I might have misunderstood or somthing isn't right.

i'm using:
S_{k} = S_{k-1} + 3*S_{k-2}
with S_{0} = 1 and S_{1} = 1

The back of the book said:
The number of pairs after 12 months is 904 or 1,808 rabits

But after doing the calculations for 12 months I'm getting a a lot bigger number, i stopped at S_{10} because i was getting 2683 pairs.

S_2 = S_1 + 3*S_0 = 1 + 3 = 4
S_3 = S_2 + 3*S_1= 4 + 3(1) = 7
S_4 = S_3 + 3*S_2= 7 + 3(4) = 19
...
...
...
S_{10} = S_9 + 3*S_8= 1159 + 3*508 = 2683

Any ideas? Thanks!

I thought at first that your sums were the correct sequence, but now I don't think so. I think it goes like this

n S(n)
0 1
1 1
2 1
3 4
4 7
5 10
6 22
7 43
8 73
9 139
10 268
11 487
12 904
13 1708
14 3169
15 5881
16 11005
17 20512

For n = 0,1,2 each term is defined to be 1. Starting with n = 3, if you define the term to be zero for all n < 0 this is given by

<br /> S_n = 4S_{n - 3} + 3\left( {S_{n - 4} + S_{n - 5} } \right)<br />

For example:

<br /> S_{12} = 4S_9 + 3\left( {S_8 + S_7 } \right) = 4 \times 139 + 3\left( {73 + 43} \right) = 904<br />

Perhaps this could be tightened up a bit if one looked at a couple of adjacent terms.

The reasoning is to track the numbers in the following categories (at the end of the month): Born; 1 month old; 2 months old; Mature. For the first several months starting with n = 0 these go

1 + 0 + 0 + 0 = 1
0 + 1 + 0 + 0 = 1
0 + 0 + 1 + 0 = 1
3 + 0 + 0 + 1 = 4
3 + 3 + 0 + 1 = 7
3 + 3 + 3 + 1 = 10
12 + 3 + 3 + 4 = 22
21 + 12 + 3 + 7 = 43

The number born at the end of every month is 3 times the number of matures. The first three numbers move one postion to the right every month, accumulating at Mature. The first three columns track the delayed sequence times three, and the last column combined with the first gives the multiple of 4 in the first term of the recurance relationship

 

[mr_coffee]

Wow that was more tough than I thought, thanks for the detailed responce, very nice.

 

[arildno]

But this IS equal to S_{k}=S_{k-1}+3S_{k-3}

 

[mr_coffee]

my bad, i should have looked at your work closer, thanks a lot :)
happy thanksgiving everyone!