Just one file here. The original question was an old chestnut: to show that if n is prime, n divides u_n, where the sequence u_n begins 0, 2, 3, ... and has u_{n+1} = u_{n-1} + u_{n-2}. We prove it, investigate the converse, and generalize. Turns out all to have been known. I don't intend to do anything with this.

From the paper:

In this paper we would like to show that in a sequence subject to a linear recurrence relation, whenever n is prime, n divides the n-th term. Unfortunately, that result is not always true, so we will show that n divides something else. As an application we will use these sequences to test quickly the primality of integers.

Click here for the TeX source file and for the output DVI file.

I received a comment which should be taken into consideration:

(3) It would be helpful to list (and examine) the desired properties of
basic recurrent sequences.  It would also be nice to develop a definition
that associates with each $f$ a *unique* basic recurrent sequence [I don't
have one!].  Here are some desirable properties:
   a.  Sequence is nontrivial, i.e., not identically zero.
   b.  Sequence is composed of integers.
   c.  Sequence satisfies the recurrence.
   d.  w_n is congruent to w_1 mod n if n is prime.
This isn't quite enough, as w_n = 1 would work for f(x) = (x-1)^k for any
positive k.  Somehow, w shouldn't satify any "lesser" recurrences, i.e.
corresponding to only some of the factors of f.  But then again see (4)a.
immediately below. 

(4) The formula for the w_{n}'s doesn't seem to work if the theta's are
repeated.  Here are some examples. 
   a. The basic recurrent sequence for f(x) = (x-1)^2 is w_n = 1.  w_n = an
+ b doesn't work because w_n - w_1 = a(n-1), which is never divisible by n>a
unless a=0.
   b. For your example of u_n = n(n-1)/2, we have f(x) = (x-1)^3.  The basic
recurrent sequence is w_n = n(n-1), not 1+n+n^2.
   c. For f(x)=(x-1)^4, the basic recurrent sequence is n(n-1)(n-2)/2.
   d. For f(x)=(x-1)^5, the basic recurrent sequence is n(n-1)(n-2)(n-3)/24.