Let $a_n$ be a linear recurrence with integer constant coefficients and initial values.

Is it possible $a_n$ to satisfy all of these:

  1. $a_n = 0$ infinitely often.

  2. if $a_n \ne 0$, $ | a_n |$ is of exponential growth (to avoid cases like $\dots 0 , n , 0 ,n+1, \dots$).

  3. $ | a_n |$ is conjectured to be prime infinitely often. Since it is not known if there are infinitely many Fibonacci primes, proving primality is hard, but there shouldn't be obvious obstructions like divisibility by a single prime or some polynomial factorization when treating a coefficient as a variable.

If this is possible, what is minimal order of $a_n$ (it can't be $2$)?


Yes. $a_n=a_{n-1}+a_{n-2}-a_{n-3}+a_{n-4}-a_{n-5}$ has a solution containing zeros and Fibonacci numbers: $0,1,0,1,0,2,0,3,0,5,0,8\ldots$.

  • $\begingroup$ Thank you! According to OEIS this can be simplified to order 4: A079977. a(n) = a(n-2)+a(n-4). Do you think order 3 is possible? $\endgroup$
    – joro
    Nov 7 '13 at 15:08
  • $\begingroup$ I thought that was cheating. No, I don't think order 3 is possible. It doesn't work if every second or third term is 0, but we would need to rule out more occasional zeros. $\endgroup$
    – user25199
    Nov 7 '13 at 17:04
  • 1
    $\begingroup$ Skolem-Lech-Mahler says you can't have (infinitely many) "occasional" zeros; they come in arithmetic progressions. $\endgroup$ Nov 7 '13 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.