1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 18, 2006 #1
    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!
     
  2. jcsd
  3. Nov 18, 2006 #2

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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).
     
    Last edited: Nov 18, 2006
  4. Nov 18, 2006 #3

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  5. Nov 18, 2006 #4

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Of course.
    However, the number alive the previous month is S_k-1, not S_k-3.
     
  6. Nov 19, 2006 #5
    ahh i c what your saying now, I was thinking it was skipping 3 months evrytime, but thats not the case, they just arnt' fertile during the first 2 months, so would it now be:
    [tex] S_{k} = S_{k-1} + 3*S_{k-2}[/tex]
     
  7. Nov 19, 2006 #6

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Quite so! :smile:
     
  8. Nov 19, 2006 #7
    thanks a ton!
     
  9. Nov 19, 2006 #8

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    I'm overwhelmed. Please remove the last 5 ounces.
     
  10. Nov 21, 2006 #9
    I was double checking my work and I might have misunderstood or somthing isn't right.

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

    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 alot bigger number, i stopped at [tex]S_{10}[/tex] because i was getting 2683 pairs.

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

    Any ideas? Thanks!
     
  11. Nov 22, 2006 #10

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Use S_k-3 instead of S_k-2, then.
     
  12. Nov 22, 2006 #11
    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 whats 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
     
  13. Nov 22, 2006 #12

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    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!).
     
  14. Nov 22, 2006 #13

    OlderDan

    User Avatar
    Science Advisor
    Homework Helper

    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

    [tex]
    S_n = 4S_{n - 3} + 3\left( {S_{n - 4} + S_{n - 5} } \right)
    [/tex]

    For example:

    [tex]
    S_{12} = 4S_9 + 3\left( {S_8 + S_7 } \right) = 4 \times 139 + 3\left( {73 + 43} \right) = 904
    [/tex]

    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
     
    Last edited: Nov 22, 2006
  15. Nov 23, 2006 #14
    Wow that was more tough than I thought, thanks for the detailed responce, very nice.
     
  16. Nov 23, 2006 #15

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    But this IS equal to [tex]S_{k}=S_{k-1}+3S_{k-3}[/tex]
     
  17. Nov 23, 2006 #16
    my bad, i should have looked at your work closer, thanks alot :)
    happy thanksgiving everyone!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?