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
Austria
and
Institute of Discrete Mathematics and Geometry
Wiedner Hauptstraße 8-10
1040 Vienna
Austria

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