On the discriminator of Lucas sequences

Abstract

We consider the family of Lucas sequences uniquely determined by $U_{n+2}(k)=(4k+2)U_{n+1}(k)-U_n(k),$ with initial values $U_0(k)=0$ and $U_1(k)=1$ and $k\ge 1$ an arbitrary integer. For any integer $n\ge 1$ the discriminator function ${\mathcal{D}}_k(n)$ of $U_n(k)$ is defined as the smallest integer $m$ such that $U_0(k),U_1(k),\dots ,U_{n-1}(k)$ are pairwise incongruent modulo $m$. Numerical work of Shallit on ${\mathcal{D}}_k(n)$ suggests that it has a relatively simple characterization. In this paper we will prove that this is indeed the case by showing that for every $k\ge 1$ there is a constant $n_k$ such that ${\mathcal{D}}_k(n)$ has a simple characterization for every $n\ge n_k$. The case $k=1$ turns out to be fundamentally different from the case $k>1$.

21 pages