Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.2

On Families of Nonlinear Recurrences Related to Digits

Th. Stoll
Faculty of Mathematics
University of Vienna
Nordbergstraße 15
1090 Vienna
Institute of Discrete Mathematics and Geometry
Wiedner Hauptstraße 8-10
1040 Vienna

Abstract: 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.

(Concerned with sequences A001521 A091522 and A091523 .)

Full version:  pdf,    dvi,    ps,    latex    

Received April 1 2005; revised version received May 12 2005. Published in Journal of Integer Sequences May 24 2005.

Return to Journal of Integer Sequences home page