On families of nonlinear recurrences related to digits

Stoll, Th.

Journal of integer sequences, Tome 8 (2005) no. 3.

Résumé

Summary: Consider the sequence of positive integers $(u_n)_{n\geq 1}$ defined by $u_1=1$ and $u_{n+1}=\lfloor\sqrt{2}\left(u_n+\frac{1}{2}\right) \rfloor$. Graham and Pollak discovered the unexpected fact that $u_{2n+1}-2u_{2n-1}$ is just the $n$-th digit in the binary expansion of $\sqrt{2}$. Fix $w\in {\mathbb{R}}_{>0}$. In this note, we first give two infinite families of similar nonlinear recurrences such that $u_{2n+1}-2u_{2n-1}$ indicates the $n$-th binary digit of $w$. Moreover, for all integral $g\geq 2$, we establish a recurrence such that $u_{2n+1}-gu_{2n-1}$ denotes the $n$-th digit of $w$ in the $g$-ary digital expansion.

Détail

Classification : 11B37, 11A67
Keywords: graham-pollak sequence, nonlinear recurrence, digits