Perrin-type sequence?

[Max]

On 3/12/06, Dean Hickerson <dean at math.ucdavis.edu> wrote:

> Your sequence is the absolute value of the sequence a(n) defined by
> a(1)=0, a(2)=3, a(3)=5, and a(n)=3a(n-1)-6a(n-2)+8a(n-3).  More
> explicitly,
>
>     a(n) = (2^(n-1) - ((1+sqrt(-15))/2)^n - ((1-sqrt(-15))/2)^n)/3
>
> It does appear to be true that if n>3 is prime then n divides a(n); at
> least it's true for all n up to 200000.

This easily follows from the explicit formula above.
For prime p>3, we have (using Fermat's Little Theorem and the fact
that binomial coefficients C(p,k) are divisible by p for 0<k<p)

a(p) = (2^(p-1) - ((1+sqrt(-15))/2)^p - ((1-sqrt(-15))/2)^p)/3
= (1 - 1/2^p - 1/2^p)/3 = (1 - 1/2 - 1/2)/3 = 0 (mod p).

Max