Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a linear recurrence sequence $\{a_n\}_{n\geq 0}$, how to decide whethere there are infinitely many zeros, or there are only finitely many ones?

share|improve this question
    
There is no way to answer such a vague question. What kind of recurrence relation do you have? –  Marc van Leeuwen Sep 11 '12 at 12:41
    
If it's a linear homogeneous constant-coefficient recurrence, the Skolem-Mahler-Lech Theorem is helpful. See, e.g., cfranc.wordpress.com/2010/03/18/the-skolem-mahler-lech-theorem –  Gerry Myerson Sep 11 '12 at 12:52
    
thanks. I mean given a linear recurrence relation, e.g., $a_{n+m}= \sum_{i=1}^{m-1} c_ia_{n+i}$, and $c_i$ are all integers, and $a_1, \dots, a_{m-1}$ are given integers. –  user29271 Sep 11 '12 at 15:39
    
If you want to be sure I see your comment, you have to put @Gerry in there somewhere. Anyway, yes, that's a linear homogeneous constant-coefficient recurrence. I trust that by now you've had a look at Skolem-Mahler-Lech. Has it been helpful? –  Gerry Myerson Sep 12 '12 at 5:58

1 Answer 1

The characteristic polynomial of your recurrence is $$x^{m-1}-c_{m-1}x^{m-2}-\cdots-c_1$$

Here's something that follows from the Skolem-Mahler-Lech Theorem: if the recurrence has infinitely many zeros, then the characteristic polynomial has two distinct roots whose ratio is a root of unity.

Careful: this is not an "if and only if".

Another good source is Chapter 2 of the book Recurrence Sequences by Graham Everest, Alf Van Der Poorten, Igor Shparlinski and Thomas Ward.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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