Sequence of IntegersDate: 08/12/2008 at 09:45:16 From: Jessica Subject: f(n + 3)f(n + 2) = f(n + 1) + f(n) + 18. Find all functions f : Z+ --> Z+ such that for each n in Z+ we have f(n) > 1 and f(n + 3)f(n + 2) = f(n + 1) + f(n) + 18. I attempted to use the idea of one-to-one function and onto function, but don't think I'm quite doing it right. I remember something similar completed in class, but when I tried to work it out with the same concept, most of the stuff didn't get eliminated as it should have.... Date: 08/17/2008 at 17:49:09 From: Doctor Vogler Subject: Re: f(n + 3)f(n + 2) = f(n + 1) + f(n) + 18. Hi Jessica, Thanks for writing to Dr. Math. That's a very good question, and very interesting. If you didn't require the values of your sequence to be integers, then you would just have a simple recurrence relation: f(n + 3) = [ f(n) + f(n + 1) + 18 ] / f(n + 2). So the first three integers you pick (for f(1), f(2), and f(3)) determine the entire sequence. But you have to pick them carefully if you want all of the terms to be integers. Furthermore, you can easily have arbitrarily many of the terms be integers. For example, if you want at least the first 10000 terms to be integers, then you just pick moderately large (like bigger than 5 is good enough) integer values for f(10000), f(9999) and f(9998), and then you can back-solve f(n) = f(n + 3)f(n + 2) - f(n + 1) - 18 all the way back to f(1). This gives (at least) 10000 consecutive integer values, but it does not guarantee that the remaining terms are integers. Consequently, you can't answer the question by only checking that f(4) and f(5) are integers. All of the above makes your problem challenging. But here is one little idea to help you break into the problem: First prove that if f(n + 2) < f(n) then this implies that f(n + 4) < f(n + 2). Similarly, if f(n + 2) = f(n) then this implies that f(n + 4) = f(n + 2) and if f(n + 2) > f(n) then this implies that f(n + 4) > f(n + 2). Conclude that the even terms of your sequence (that is, the ones with n even) are either constant (all the same), or they form a strictly monotonic sequence (always increasing or always decreasing). Similarly for the odd terms of your sequence. Explain why a sequence of positive integers cannot be strictly monotonic decreasing. If the odd (respectively, even) terms of your sequence are a constant x (other than 1), then prove that the even (respectively, odd) terms of your sequence are an arithmetico-geometric sequence whose limiting value is (x + 18)/(x - 1) = 1 + 19/(x - 1), which means that all even (resp. odd) terms are given by the formula x + 18 1 (n/2) f(n) = ------ + ( --- ) * constant x - 1 x or f(n) = (x + 18)/(x - 1) + (1/x)^(n/2) * (constant) for some constant (which depends on x and on the initial term, but not on n). Since x has to be an integer (why?) bigger than 1, f(n) gets closer and closer to the limit (x + 18)/(x - 1) as n grows to infinity, which means that either the limit is a non-integer and eventually f(n) will get too close to the limit and will also fail to be an integer, or the limit is an integer, and eventually f(n) will get too close to be any *other* integer, which means that the only way for f(n) to be an integer for every n is if the constant is zero, so that f(n) = (x + 18)/(x - 1) = 1 + 19/(x - 1) for every even (resp. odd) n, and this number is an integer. For which integer values of x is the above number an integer (hint: the number 19 is prime)? If x = 1, then what happens? The alternative is that the even terms form a monotonic increasing sequence, and the odd terms form a monotonic increasing sequence. Since the terms are all integers, they must increase by at least 1 every step, which means that, eventually, f(n) is always bigger than, say, 5. (We could have put 100 there instead, but 5 is already enough.) In particular, it means that for all sufficiently large n (and we only need this for one n), we have f(n + 3) > f(n + 1) > 5 and f(n + 2) > f(n) > 5. But then f(n) + f(n + 1) + 18 = f(n + 2)f(n + 3) >= (f(n) + 1)(f(n + 1) + 1) >= f(n)f(n + 1) + f(n) + f(n + 1) + 1 > 5 * 5 + f(n) + f(n + 1) + 1 = f(n) + f(n + 1) + 26, which is obviously impossible. Conclude that the only sequences of positive integers that satisfy your equation for all n are the alternating sequence of 2 and 20: 2 if n is even f(n) = { 20 if n is odd and the reverse 2 if n is odd f(n) = { 20 if n is even and a sequence which alternates between 1 and a linear sequence with common difference 19 1 if n is even f(n) = { m + 19(n+1)/2 if n is odd and the reverse 1 if n is odd f(n) = { m + 19(n/2) if n is even If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/