We know that any whole number can be expressed as a binary number. But what if we change this a little bit?
Any positive whole number can be expressed as a finite series of ascending powers of $2$ with alternating sign. For example, $3=-1+4=-2^0+2^2$, $6=2-4+8=2^1-2^2+2^3$.
Question: Giving a positive number $n$, in how many ways can $n$ be expressed in such a fasion given above?
I would be pleased if anyone caould show me if there's any article or books on this topic.
I am not clear if a use the wrong tags. If that happens, pls point out.
There is only one way to do this. Notice that $2^n - 2^m = \sum\limits_{i=m}^{n-1} 2^i$.
For a positive integer $N$ consider a set $S = \{i \in \mathbb{N}\cup\{0\} \colon i\text{-th bit in the binary representation of } N \text{ is }1\}$ Then $S$ can be represented as unite of maximal-inclusive integer intervals $S = \bigcup\limits_{i=1}^k \{\alpha_i, \alpha_i + 1, \ldots, \beta_i\}$ such that $\alpha_{i+1} > \beta_{i} + 1$ in the unique way. For example $S = \{0,1,3,5,6,7\} = \{0,1\} \cup \{3\} \cup \{5,6,7\}$. If $S$ is represented in a such way then $N = \sum\limits_{x\in S} 2^x = \sum\limits_{i=1}^k \sum\limits_{j=\alpha_i}^{\beta_i} 2^j=\sum\limits_{i=1}^k (2^{\beta_i + 1} - 2^{\alpha_i})$ by the first observation. $\alpha_1 < \beta_1 + 1 < \alpha_2 < \ldots < \alpha_k < \beta_k + 1$. On the other hand if $N$ is represented in that way then $S = \bigcup\limits_{i=1}^k \{\alpha_i, \ldots, \beta_i\}$. Therefore there is only one way if the signs alternating like $-1, +1, -1, \ldots$.