From Wikipedia, the free encyclopedia

Mathematics desk
< November 4	<< Oct | November | Dec >>	November 6 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

Contents 1 November 5 1.1 exponentials 1.2 find a recurrence relation for the number of ways to climb n stairs if you can go 1 step, 2 or 3...

[edit] November 5

[edit] exponentials

"If the population of rabbits (or anything) is initially 2000 and decays at a rate of 10% per yr, how long does it take for the population to reach 300.."

These sort of questions (I just fabricated that) are confusing. You can of course do the math and work out that it takes 18.005986 years for this to be satisfied.. in some cases it doesn't specify how you should answer so the answer would be 18. Why is this so..? Why write "After 18 years" instead of the exact value? And what does it mean when a question asks you to write your answer to the nearest six months/quarter?

Rounding is a common practice to limit the amount of digits used in a response. Assuming you used a log to find that answer, the answer is probably not an 'exact' value either, it's just rounded to many mroe decimal places. One argumant for rounding is that the 10% (or 2000) are unlikely to accurate to that many Significant figures (indeed, the rabit population would be very hard to count and may have a very large error.) Hope this helped. 48v 05:43, 5 November 2006 (UTC)

Indeed, you cannot give an exact value for two reasons. As a decimal expansion, even 18.005986142352000064378227351623801121 is a miserable approximation of the exact value of the logarithm of 300/2000 to the base 0.90. Secondly, if this is a mathematical model of something in the real world, what would the population of rabbits be after exactly 18 years? Would there be 300.18927... rabbits? Since the number of rabbits is always a whole number, the continuous aspect of exponential decay can only refer to a statistical expectation, and the 10% can only be an estimate. As is described in our article on percentages, it is common to round percentages anyway, so 10% may stand for any value from 0.095 to 0.105, giving a range from 17.1 to 19.0 years.  --Lambiam^Talk 08:45, 5 November 2006 (UTC)

[edit] find a recurrence relation for the number of ways to climb n stairs if you can go 1 step, 2 or 3...

for problems like these, why is the answer just additive without any exponential terms?

For example, the problem : "find a recurrence relation for the number of bit strings of length n with 3 consecutive 000's" has a 2^(n-3) in the solution.

when is it just additive and when is it additive with an exponential?

I guess I don't understand your question. Both for climbing stairs with one, two, or three stairs per step, and for bitstrings without (typo I assume) three consecutive zeros, the problem can be formulated using a recurrence relation that just involves addition and constants. And for both problems, the recurrence relation has a closed form solution involving exponentials. So what is the distinction between the two that you're trying to describe? —David Eppstein 19:51, 5 November 2006 (UTC)

no, I meant with three consecutive 000's.

look at ::http://72.14.203.104/search?q=cache:aARC9xTsAfsJ:www.cs.queensu.ca/home/akl/cisc203/2006/SAMPLE_TESTS/solutions_4.ps+%22find+a+recurrence+relation+for+the+number+of+ways+to+climb+n+stairs%22&hl=en&gl=us&ct=clnk&cd=6

it says that the stair problem is just additive

http://www.comp.nus.edu.sg/~cs1232/pdfs/tut2s.pdf

shows that the bit string problem is additive with the 2^(n-3) at the end.

what i need to know is, given one of these strange word problems, how can I decide if the relation has an exponetial term in it or if it's just simple additive? Does that makes sense?

I think that I can see what you mean. In the stair climbing problem let a_n be the number of ways of climbing n steps. If n is at least 3 then there are 3 cases:

1. Climb 1 step in the first leap. Then we must climb n − 1 further steps and there are a_{n − 1} ways of doing this.
2. Climb 2 steps in the first leap. Then we must climb n − 2 further steps and there are a_{n − 2} ways of doing this.
3. Climb 3 steps in the first leap. Then we must climb n − 3 further steps and there are a_{n − 3} ways of doing this.

Note that in each case we reduce the problem to a simpler problem of the same type and we get the recurrence relation a_n = a_{n − 1} + a_{n − 2} + a_{n − 3}, which is "simply additive".

In the bit string problem let S_n,3 be the number of bitstrings of length n with 3 consecutive 0s. If n is at least 3 then there are 4 cases:

1. The string has 1 as a prefix. Then the remaining string has length n − 1 and must contain 3 consecutive 0s. There are S_{n − 1,3} such strings.
2. The string has 01 as a prefix. Then the remaining string has length n − 2 and must contain 3 consecutive 0s. There are S_{n − 2,3} such strings.
3. The string has 001 as a prefix. Then the remaining string has length n − 3 and must contain 3 consecutive 0s. There are S_{n − 3,3} such strings.
4. The string has 000 as a prefix. Then the remaining string has length n − 3 and may be arbitrary. There are 2^{n − 3} such strings.

In the first 3 cases we reduce the problem to a simpler problem of the same type. However in the fourth case, we reduce to finding the number of bit strings of length n − 3 which we know to be 2^{n − 3}. Hence in this case we get the recurrence relation S_n,3 = S_{n − 1,3} + S_{n − 2,3} + S_{n − 3,3} + 2^{n − 3}, which is not "simply additive".

In general, the recurrence relation will be "simply additive" if the problem can be reduced to several simpler problems of the same type. Also, if the relation is not "simply additive" then the extra terms need not be exponential. We could have a recurrence relation such as a_n = a_{n − 1} + n.

I hope I have been of some assistance. --Matthew Auger 21:55, 5 November 2006 (UTC)

thank you for the response, it is much appreciated. this makes more sense. Thanks.