next up previous
Next: Problems Up: Linear recursive sequences Previous: Inhomogeneous recurrence relations

The Mahler-Lech theorem

Here is a deep theorem about linear recursive sequences:

Theorem 4 (Mahler-Lech theorem)   Let $ \{a_n\}$ be a linear recursive sequence of complex numbers, and let $ c$ be a complex number. Then there exists a finite (possibly empty) list of arithmetic progressions $ T_1$, $ T_2$, ...$ T_m$ and a finite (possibly empty) set $ S$ of integers such that

$\displaystyle \{  n \mid a_n=c  \} = S \cup T_1 \cup T_2 \cup \cdots \cup T_m.$

Warning: don't try to prove this at home! This is very hard to prove. The proof uses ``$ p$-adic numbers.''

Zvezdelina Stankova-Frenkel 2000-09-20