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

In summary, the recurance relation for the Fibonacci sequence is that there are a total of 10 rabbits after 12 months.
  • #1
mr_coffee
1,629
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!
 
Physics news on Phys.org
  • #2
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:
  • #3
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
 
  • #4
Of course.
However, the number alive the previous month is S_k-1, not S_k-3.
 
  • #5
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:
[tex] S_{k} = S_{k-1} + 3*S_{k-2}[/tex]
 
  • #6
Quite so! :smile:
 
  • #7
thanks a ton!
 
  • #8
mr_coffee said:
thanks a ton!
I'm overwhelmed. Please remove the last 5 ounces.
 
  • #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 a lot 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!
 
  • #10
Use S_k-3 instead of S_k-2, then.
 
  • #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 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
 
  • #12
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!).
 
  • #13
mr_coffee said:
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 a lot 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!
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:
  • #14
Wow that was more tough than I thought, thanks for the detailed responce, very nice.
 
  • #15
But this IS equal to [tex]S_{k}=S_{k-1}+3S_{k-3}[/tex]
 
  • #16
my bad, i should have looked at your work closer, thanks a lot :)
happy thanksgiving everyone!
 

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

1. What is Fibonacci's question?

Fibonacci's question is a mathematical problem posed by Leonardo Fibonacci in the 13th century. It asks how many pairs of rabbits will be produced in one year if a pair of rabbits produces a new pair every month, and each new pair takes one month to mature before producing their own pair.

2. What is a recurrence relationship?

A recurrence relationship is a sequence of numbers or mathematical expressions that are defined recursively, meaning each term is defined in terms of the previous terms. It is often used to describe patterns or processes that repeat themselves.

3. How is Fibonacci's question related to a recurrence relationship?

Fibonacci's question can be solved using a recurrence relationship, as the number of pairs of rabbits in each month can be expressed as a function of the previous month's number of pairs. This leads to a recursive sequence, which can be solved to find the total number of pairs of rabbits after a given number of months.

4. Did I get it right? Can you give an example of a recurrence relationship?

Yes, you got the concept of a recurrence relationship right. An example of a recurrence relationship is the Fibonacci sequence itself: 1, 1, 2, 3, 5, 8, 13, ... where each term is the sum of the two previous terms.

5. Are there any real-life applications of Fibonacci's question and recurrence relationships?

Yes, Fibonacci's question and recurrence relationships have been used in a variety of fields such as finance, computer science, and biology. In finance, the Fibonacci sequence has been used to predict stock market trends, while in computer science, recurrence relationships are used in algorithms for sorting, searching, and data compression. In biology, the Fibonacci sequence has been observed in the branching patterns of trees and the arrangement of leaves on a stem.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
5K
  • General Math
Replies
4
Views
1K
  • Math Proof Training and Practice
2
Replies
64
Views
13K
  • Sci-Fi Writing and World Building
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
17K
  • Special and General Relativity
3
Replies
75
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • STEM Educators and Teaching
Replies
2
Views
12K
Back
Top