# Simple recursion or closed form for $\lfloor 2^n \sqrt{2}\rfloor$

Is it possible to find an expression of the form $$\lfloor 2^n \sqrt{2}\rfloor = \sum_{k=1}^r (\alpha_k + \beta_ki)\cdot\Big(a_k+b_k i\Big)^n,$$ where $$i^2 = -1$$ and $$\alpha_k, \beta_k, a_k, b_k$$ real numbers? Maybe with $$r< 5$$ if possible. I am trying to compute the mean value (average) of $$\{ 2^n \sqrt{2}\}= 2^n \sqrt{2} - \lfloor 2^n \sqrt{2}\rfloor$$ over $$n=0, 1,2, \cdots$$. Let us denote as $$p$$ this mean value: $$p$$ is the proportion of binary digits of $$\sqrt{2}$$ equal to one, and $$p$$ is widely believed to be equal to $$\frac{1}{2}$$.

Note that $$p=\lim_{n\rightarrow\infty} p_n, \mbox{ with } p_n = \frac{1}{n}\sum_{k=1}^n \Big( 2^k \sqrt{2} - \lfloor 2^k \sqrt{2}\rfloor\Big).$$ Assuming we have a simple closed form for $$\lfloor 2^k \sqrt{2}\rfloor$$ as suggested in the first formula, then we can have a closed form for $$p_n$$, involving a finite number of terms. I don't expect this to be true if you replace $$\sqrt{2}$$ by (say) $$\pi$$ or $$\log 2$$, but I would expect this to work with any quadratic irrational.

Of course you can always use the Fourrier series to represent the fractional part function, but I don't think it would be easy to handle: it involves an infinite number of terms ($$r=\infty$$.)

• Does it help at all that $2^n\sqrt2=2^{n+\frac12}$? – Andrew Chin Sep 18 '19 at 15:43
• This is equivalent to find a simply way to find the binary digits of $\sqrt 2$. You can try mimicking the classic square root algorithm for decimal notation. – ajotatxe Sep 18 '19 at 15:50
• @AndrewChin: Maybe or maybe not. The general idea is that formulas do exist for sequences such as $\lfloor \phi^n\rfloor$ where $\phi$ is the golden ratio, and the recursion attached to it linked to Fibonacci numbers. – Vincent Granville Sep 18 '19 at 15:51
• But $\sqrt 2$ has not so nice properties... – ajotatxe Sep 18 '19 at 15:52
• I have found this. Not exactly simple, but... – ajotatxe Sep 18 '19 at 15:54

No it's not possible.

A sequence of complex numbers $$A_n$$ having a closed form of the type $$A_n = \sum_{i=1}^k a_i b_i^n$$ with the $$a_i$$'s and $$b_i$$'s complex numbers implies it satisfies a recursion $$A_n = c_1A_{n-1}+\dots +c_kA_{n-k}$$ for some fixed complex numbers $$c_1, c_2, \dots, c_k$$.

Moreover, if that sequence $$A_n$$ is actually a sequence of integers then the constants $$c_1, c_2, \dots, c_k$$ in the recursion are actually rational numbers. Clearing the denominators gives a recursion $$c_0'A_n = c_1'A_{n-1}+\dots +c_k'A_{n-k}$$ where now the $$c_i'$$s are integers.

Now note that the parity of $$A_n$$ only depends on the parity of $$A_{n-1}, A_{n-2},\dots$$ and $$A_{n-k}$$. In particular, this sequence must become periodic mod 2 as once the same length $$k$$ string of parities occurs everything after it repeats as well, and there are finitely many $$(2^k)$$ length $$k$$ strings.

This is a problem though, as the parity of $$\lfloor 2^n \sqrt{2} \rfloor$$ determines the $$n$$th binary digit of $$\sqrt{2}$$. This sequence being periodic implies that $$\sqrt{2}$$ is rational, which we know is false.

This same argument shows that $$\lfloor a^n b \rfloor$$ with $$a \in \mathbb{N}$$ can be written in this form iff $$b$$ is rational.

• Thanks Nate. Let me think about this. The $A_n$'s have to be irrational. And using my notation, the largest modulus of $a_k + b_k i$ (that is, the largest $\sqrt{a_k^2 + b_k^2}$) must necessarily be exactly equal to 2. – Vincent Granville Sep 18 '19 at 16:13
• In think you misunderstand, $A_n$ in this argument is $\lfloor 2^n \sqrt{2} \rfloor$, which is definitely an integer. – Nate Sep 18 '19 at 18:11
• I assume the sequence $A_n = \lfloor 2^n \sqrt{2} \rfloor$ has this closed form and arrive at $\sqrt{2}$ being rational, a contradiction. – Nate Sep 18 '19 at 18:12
• I may have misunderstood, I'll spend a bit more time on this. I assume you are right and I have thus accepted your answer. In the meanwhile, I added some elements from this discussion to my recent article "Two New Deep Conjectures in Probabilistic Number Theory", see exercise 14 at the very bottom when you read my article (link: datasciencecentral.com/profiles/blogs/…) – Vincent Granville Sep 18 '19 at 18:40