Erdős Problem #482

Define a sequence by \(a_1=1\) and \[a_{n+1}=\lfloor\sqrt{2}(a_n+1/2)\rfloor\] for \(n\geq 1\). The difference \(a_{2n+1}-2a_{2n-1}\) is the \(n\)th digit in the binary expansion of \(\sqrt{2}\). Find similar results for \(\theta=\sqrt{m}\), and other algebraic numbers. The result for \(\sqrt{2}\) was obtained by Graham and Pollak [GrPo70]. The problem statement is open-ended, but presumably Erdős and Graham would have been satisfied with the wide-ranging generalisations of Stoll ([St05] and [St06]). The binary expansion is \(\sqrt{2} = 1.0110101\ldots\), and the \(n\)th digit counts the leading \(1\) as digit \(1\). It is stated with Mathlib's `Real.digits`: the \(n\)th digit of \(\sqrt{2}\) is digit \(n - 1\) of \(\sqrt{2}/2 = 0.10110101\ldots\), that is \(\lfloor \sqrt{2} \cdot 2^{n-1} \rfloor \bmod 2\). The second conjunct records that these digits are the binary expansion: they reconstruct \(\sqrt{2}/2\).