Can a non-trivial integer sequence in which each element is the sum of the k previous elements be periodic?

[ Editor: the problem was posted by Stanley Rabinowitz
<stan@alliant.UUCP> in article <437@alliant.UUCP>.  Three replies
follow. ]

No, it is not possible.

All the solutions of the above recurrences are generalized Fibonacci
sequences which have solutions of the form:

        a[n] = sum( from j=1 to k, b[j] * rho[j]^n )

where rho[j] is a root of the characteristic equation:
x^k = x^(k-1)+....+x+1, and the b[j] are set according to the initial
conditions.

For a solution to be periodic, some of the rho[j]'s should be of the
form: exp(2*i*Pi/r) (where r would be the length of the period).

The characteristic polynomial can be rewritten as:  x^(k+1) - 2*x^k + 1,
(with x<>1) and the characteristic equation as:  x^(k+1)+1 = 2*x^k.
(Note that |x^(k+1)| = |x^k| = 1).  By drawing circles on the complex
plane, we see that the only solution is for x^k=1 and x^(k+1)=1 ==> x=1
and since this one was excluded, there are no solutions and hence
no periodic sequences.

[ Editor: this reply was unsigned in the collected material. ]

----

My answer is no.

Note:  I use the notation N(m) = N(m-k) + N(m-k+1) + ... + N(m-1)
for the sequence.

Proof by contradiction:

Assume we have such a sequence.

First, examine the case where m = k + 1, i.e. the first point
at which the recurrence becomes periodic. Then, we have the
following equality:

N(k+1) = N(1) + N(2) + ... + N(k)

Which, by the definition of the periodic recursive sequence, is the
same as:

N(1) = N(1) + N(2) + ... + N(k).

So, this implies:

0 = N(2) + ... + N(k).

Now, examine the k+2 step:

N(k+2) = N(2) + N(3) + ... + N(k) + N(k+1)
       =              0           + N(k+1)
       = N(k+1)
       = N(1).

For k+3:

N(k+3) = N(3) + N(4) + ... + N(k+1) + N(k+2)
       = N(k+2) + N(3) + N(4) + ... + N(k+1)        /* re-ordering */
       = N(2) + N(3) + ... + N(k) + N(k+1)
       = N(1),        from above.

Since we can map the (k + i)th integer back into the first k integers
with a mod function, we can always regenerate the same sequence,
yielding the result that N(k+i) = N(i mod k) = N(1).

This yields two results:  That all of the N(i) are the same, and
that k * N(1) = N(1).  This can only be true if (either) k = 1
or N(1) = 0, which are the two conditions stated above as being
illegal.

Thus, there is no such sequence.

-- Steve Chapin <sjc@arthur.cs.purdue.edu>

[ Editor: this argument assumes N(k+1) = N(1), i.e. that the period
is exactly k; a sequence with any other period is not covered by it. ]

----

No.

Given any such recurrence, the terms are described by

(1) a[n] = sum over i: c[i] r[i]^n

where c[i] are (complex) coefficients and r[i] are the roots of the
indicial equation:

(2) r^k = r^(k-1) + r^(k-2) + ... + r + 1

Consider the term(s) of (1) whose r[i]'s have the largest magnitude.
Ignoring combinations of terms that are identically zero (if any such
can exist), these terms will dominate the sum.  Since the series is
periodic, the terms can neither grow nor shrink over the long run, and
so the magnitude of the r[i]'s of the dominating terms must be 1.
Conversely, if we can find an r whose magnitude is 1, the problem is
solved affirmatively.  Thus, the only question is whether any root of
(2) can have magnitude 1.

We can rewrite (2) as:

r^k = (r^k-1)/(r-1)

(3) r^(k+1) + 1 = 2r^k

Since the magnitude of the terms on the left is each 1, and of the
term on the right is 2, the only way to get (3) to work is by

r^(k+1) = 1

r^k = 1

giving

r = 1

which is not a root of (2) for k>1.

-- Dale Worley <cullvax!drw@eddie.mit.edu>