Finding Solutions to a Discrete Math Function Problem

[axon23]

Hi
I need some help with the following problem:

1. Find all functions f: Z₊ -> Z₊ such that for each n Є Z₊ we have f(n) > 1 and
f(n + 3)f(n + 2) = f(n + 1) + f(n) + 18
2. I've been reading everywhere and I can't seem to find anything like this. I was wondering if anybody knew where to start
3. I was thinking of trying one to one, but it doesn't make sense. Then induction but I don't think I can conclude anything from that either.

Thanks for your help

 

[Alex6200]

Hmmm, what I tried to do is say f(0) = a, f(1) = b, f(2) = c, and then see if a pattern emerges that would let you determine what values of a, b, and c work. Maybe write a program so that you can get more values, maybe use TI-89 basic?

That's a tough problem.

 

[axon23]

i already wrote a program to try many different functions with different values and i get that there are no solutions.. but i just don't know how to get to that point.

 

[Alex6200]

Ah, I see what you're saying. Ummmm... If you keep a, b, and c general can you show that the limit of f(n, even) as n approaches infinity is 1? I'll try that.

 

[Dick]

If you fish around you can find f_n={2,20,2,20,2,20,...} works, so I wouldn't try to prove there are no solutions. But I don't see how to tackle it in general. It does look hard. Unless there is a trick.

 

[Dick]

Ah, ha! Here's a BIG hint. You have f(n+3)f(n+2)=f(n+1)+f(n)+18. Get another equation by substituting n+1 for all of the n's in that equation and subtract the two equations. Can you use that to show f(n+3)*(f(n+4)-f(n+2))=f(n+2)-f(n)?? That's your BIG hint. Here's a LITTLE hint. Remember f(n+3)>1. This tells you a lot about the behavior of the differences of alternating terms. Use it to draw an important conclusion about alternating terms.

 

[Alex6200]

Ah, ha! Here's a BIG hint. You have f(n+3)f(n+2)=f(n+1)+f(n)+18. Get another equation by substituting n+1 for all of the n's in that equation and subtract the two equations. Can you use that to show f(n+3)*(f(n+4)-f(n+2))=f(n+2)-f(n)?? That's your BIG hint.

Just curious, what made you think of doing that?

 

[Dick]

Just curious, what made you think of doing that?

First, I did the same thing you and axon23 did. I wrote a computer program to generate examples of such sequences starting with arbitrary initial data. Observed that in the general case, ignoring the restriction to integers greater than 1 that the sequence still converged to one with alternating terms nearly equal. Wondered, why? Guessed that the '18' didn't have much to do with it. Did the obvious thing to eliminate the '18', subtracting two shifted versions of the recursion relation. Found gold. In brief, I just 'messed around with it' for a while. I don't think there is any system to solve problems like this. Now, I'm just curious. Did you solve the problem?

 

[Alex6200]

Haven't solved it yet. Still thinking about it.

 

[Dick]

More hints follow. f(n+4)-f(n+2)=0 iff f(n+2)-f(n)=0. So differences are either all nonzero or all zero. Which is it? If nonzero then, |f(n+4)-f(n+2)|<|f(n+2)-f(n)| that's an infinitely decreasing series of positive integers. Is there such a thing? How many more hints do you need?

 

[Alex6200]

Ohhh... I think I got it. If f(5) is not the same as f(3), and so on, then it's not going to be a valid function f(n) because it will eventually go to 1 or below one. So for a valid f(n):

f(n+2) = f(n), so our equation

f(n+3)f(n+2) = f(n+1) + f(n) + 18

becomes

f(n+1)f(n) = f(n+1) + f(n) + 18,

f(n+1) = (f(n) + 18) / (f(n) - 1)

So my solution is, with C = f(1) being the initial condition:

f(n, even) = (C + 18) / (C - 1)
f(n, odd) = C

so if C = 2:

f(n) = 2,20,2,20,2,20...

That was an interesting problem. Thanks for the help Dick.

 

[Dick]

There are actually two solutions. 20,2,20,2,20,.. works as well.