The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Sequence of Integers

Date: 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 

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


  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


  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 
Associated Topics:
High School Functions
High School Logic
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.