# Every real number can be represented as a sum of plus-minus of the terms of infinite geometric sequence $2^{-n}$.

Every $$C\in \mathbb R$$ can be represented as $$C = \sum_{n=k}^\infty \pm 2^{-n}$$ for some $$k\in \mathbb Z$$.

Trivially, every real number can be represented as $$\sum_{n=1}^\infty \pm 2^{-a_n}$$ for some strictly increasing sequence $$\{a_n\}$$. However, there might be missing terms in the geometric sequence, i.e. $$a_{n+1}$$ might be greater than $$a_n$$ for some $$n$$.

Is there a shorted / easier to follow proof than I provide among answers?

This question was inspired by the post: Conjecture about the representation of a constant $C=0.6516...$

Strategy: Notice that $$2^{-2} = 2^{-1} - 2^{-2},$$ using this fact you can always "fill the gaps" in the sequence $$\{a_n\}$$. It allows me to prove a much stronger result in fact.

Proof.

If $$C = 0$$, then $$C = 2^0 - \sum_{n=1}^\infty 2^{-n}$$. It is enough to show that $$C>0$$ can be represented in the desired way, as in order to represent $$-C$$ it is enough to switch the signs.

In the rest of the proof we consider $$C>0$$. Since every positive real number can be represented in basis 2, there exist a (possibly finite) strictly increasing sequence $$\{b_n\}$$ such that $$C = \sum_{n=1}^\infty 2^{-b_n}$$. If the sequence was finite and $$b_M$$ was the last term, we could replace $$2^{-a_M}$$ by $$\sum_{m=1}^\infty 2^{-(a_M+m)} = 2^{-a_M}.$$

We conclude that there is at least one way to represent $$C$$ as $$\sum_{n=1}^\infty \pm 2^{-c_n}$$, where $$\{c_n\}$$ is a strictly increasing sequence (with terms possibly apart by more than $$10$$). Let $$\mathcal{S}$$ be the set of all such sequences $$\{c_n\}$$. If $$\mathcal{S}$$ contains an arithmetic sequence of the form $$c_1,c_1+1,\ldots$$, we are done. Suppose that not. For a sequence $$\{c_n\} \in \mathcal{S}$$ define $$f(\{c_n\}) = \min\big\{n\in \mathbb N:c_{n+1}-c_n>1\big\}.$$ and let $$N = \max\big\{ f(\{c_n\}) : \{c_n\} \in \mathcal{S}\big\}.$$ Define the subset of $$\mathcal{S}$$ containing the sequence of "earliest occurance of a gap", $$\mathcal{T} = \big\{ \{c_n\} \in \mathcal{F} : f(\{c_n\}) = N \big\}.$$ Finally, pick any sequence $$\{c_n\}$$ from $$\mathcal{T}$$ for which $$c_{N+1}-c_N$$ is minimal. By the definition of $$N$$ and $$\mathcal{T}$$, $$c_{N+1}-c_N > 1$$. By replacing $$\pm 2^{-c_{N+1}}$$ with $$\pm 2^{-(c_{N+1}-1)} \mp 2^{-c_{N+1}},$$ we obtain new sequence $$\{c'_n\}$$ that can be written as $$c_1,\ldots,c_n,c_{N+1}-1,c_{N+1},\ldots$$ and it belong to $$\mathcal S$$. If $$c_{N+1}-c_{N}=2$$, then the beginning of the new sequence contains more than $$N$$ consecutive integers ($$f(\{c'_n)>N$$), which is a contradiction with the maximality of $$N$$. Last, if $$c_{N+1}-c_{N}>2$$, then the new sequence $$\{c'_n\}$$ belongs to $$\mathcal T$$ and $$c'_{N+1}-c'_{N} , which is a contradiction with the way $$\{c_n\}$$ was chosen out of all the sequences in $$\mathcal T$$. That concludes the proof.

Somewhat shorter proof:

Using the same argument as in the other proof, we can assume $$C>0$$. Let $$\sum_{n=k}^\infty b_n 2^{-n}$$, where $$k\in \mathbb Z$$ and $$\{b_n\}\in \{0,1\}^\infty$$, be the binary representation of $$C$$. Then $$C = \sum_{n=k}^\infty b_n 2^{-n} = \sum_{n=k}^\infty 2b_n 2^{-(n+1)} = 2^{-k} + \sum_{n=k}^\infty (2b_n-1) 2^{-(n+1)},$$ where $$2b_n-1 = \pm 1$$ for all $$n=k,k+1,\ldots$$. This is the desired representation.