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$ – Gerry Myerson Nov 7 '13 at 23:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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