next up previous
Next: About this document ...

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.





Jeffrey Shallit 2005-05-24