1. Limited time only! Sign up for a free 30min personal 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!

Functions in Discrete math

  1. Aug 13, 2008 #1
    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
  2. jcsd
  3. Aug 13, 2008 #2
    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.
  4. Aug 13, 2008 #3
    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.
  5. Aug 13, 2008 #4
    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.
  6. Aug 13, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Aug 13, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    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.
  8. Aug 13, 2008 #7
    Just curious, what made you think of doing that?
  9. Aug 13, 2008 #8


    User Avatar
    Science Advisor
    Homework Helper

    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?
    Last edited: Aug 13, 2008
  10. Aug 14, 2008 #9
    Haven't solved it yet. Still thinking about it.
  11. Aug 14, 2008 #10


    User Avatar
    Science Advisor
    Homework Helper

    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?
    Last edited: Aug 14, 2008
  12. Aug 15, 2008 #11
    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


    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.
  13. Aug 15, 2008 #12


    User Avatar
    Science Advisor
    Homework Helper

    There are actually two solutions. 20,2,20,2,20,.. works as well.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Functions in Discrete math
  1. Discrete Maths (Replies: 3)

  2. Discrete Math (Replies: 2)