Proof that base -2 with binary digits can form every integer Basically the question is proving that you can create all integers with binary but instead using $-2$ as the base to be able to create negative integers.
Exact question: 

Prove that every integer (positive, negative, or zero) can be written as the sum of distinct powers of $−2$.

I somewhat get how you can induct upon increasing powers for $2^0+2^1+2^2$ etc and prove that it will always hold for the next number but I'm not sure how this will work with negative integers since If I induct upwards I can't go down and I can't start at $-\infty$.
 A: $0$ is obtained via the empty set.
We'll proceed by "simultaneous induction" on the positive and negative integers.
To build up positive base cases we note that $$1=(-2)^0\quad \quad 2=(-2)^2+(-2)^1\quad \quad 3= (-2)^2+(-2)^1+(-2)^0$$
To build up negative base cases we note that $$-1=(-2)^1+(-2)^0\quad \quad -2=(-2)^1\quad \quad -3=(-2)^3+(-2)^2+(-2)^0$$
Now the induction statement we want is "Given that the claim is true for all integers $k$ with $|k|≤n-1$ prove that it is also true for $k=\pm n$."  
That plus the base cases will certainly suffice.
To prove the statement, we first note that (using the base cases) we can assume that $n≥4$.  Now we distinguish between the cases $n$ even or $n$ odd.
If $n$ is even then $\frac n{-2}$ is an integer with absolute value $<n$ so we can write $$\frac n{-2}=\sum_{i=1}^m(-2)^{a_i}\implies n=\sum_{i=1}^m(-2)^{a_i+1}$$
(here, of course, we are using a proper representation of the smaller number.  Thus the $\{a_i\}$ are distinct.  If that is the case, then of course the numbers $\{a_i+1\}$ are also all distinct.)
If $n$ is odd then $n-1$ is even and, as before we can write $$\frac {n-1}{-2}=\sum_{i=1}^m(-2)^{a_i}\implies n=\sum_{i=1}^m(-2)^{a_i+1}+(-2)^0$$  and we are done.
The case of $-n$ is more or less identical.
Note that this method is "constructive" in the sense that you can use it to construct the representation of some number, given that you have already got the representations of smaller numbers.
A: Let $ n $ be the integer that you wish to write as the sum of distinct powers of $ -2 $. We'll start off with some base cases:


*

*$ 1 = ( -2 ) ^ 0 $

*$ 0 = 0 $ (sum of zero powers of $ -2 $)

*$ -1 = ( -2 ) ^ 1 + ( -2 ) ^ 0 $

*$ -2 = ( -2 ) ^ 1 $
For other values of $ n $ we can find the sum of distinct powers of $ -2 $ for $ \frac n { -2 } $ (if n is even) or $ \frac { n - 1 } { -2 } $ (if n is odd), whose absolute value is always less than $ n $. We can take this sum, multiply each term by $ -2 $ (which leaves the terms distinct), and for odd $ n $ add $ ( -2 ) ^ 0 $ (which no longer appears after the multiplication), to produce a sum of distinct powers of $ -2 $ that equals $ n $. Since at each step we reduce the absolute value, we will eventually end up at one of the base cases.
A: The statement follows from the following proposition (which can be discovered by considering small cases):
For every $n\ge0$, define $D = \sum_{1\le d\le n/2} 2^{2d-1}$.
Every integer between $-D$ and $2^n-D-1$ (inclusive) can be written as the sum of distinct elements of $\big\{ (-2)^0, (-2)^1, \dots, (-2)^{n-1} \big\}$.
Proof: choose an integer $t$ with $-D \le t \le 2^n-D-1$. Write $t+D$ in binary as an $n$-bit integer (padding on the left with $0$s if necessary): $t+D=(b_{n-1}b_{n-2}\cdots b_1b_0)_2$, so that $t+D = \sum_{0\le j\le n-1} b_j 2^j$. Then
\begin{align*}
t = t+D-D &= \sum_{0\le j\le n-1} b_j 2^j - \sum_{1\le d\le n/2} 2^{2d-1} \\
&= \sum_{0\le j\le n-1} \begin{cases}
b_j, &\text{if $j$ is even}, \\
1-b_j, &\text{if $j$ is odd}
\end{cases} \bigg\} (-2)^j
\end{align*}
is a representation of $t$ as the sum of distinct powers of $-2$ (since each $b_j$ and each $1-b_j$ is either $0$ or $1$).
A: I know you're looking for an inductive proof, but here is a non-inductive alternative.
First, we claim that any integer $n$ can be written as a (finite) sum of powers of $-2$ which are not necessarily all different. This can be done by taking the normal binary representation and regarding this as a sum where each term is $\pm(-2)^k$ for some $k$, then replacing each $-(-2)^k$ with $(-2)^{k+1}+(-2)^k$.
Next, we choose the "best" representation of $n$ as a sum of (not necessarily distinct) powers of $-2$. We have three criteria for doing this, in order of priority:


*

*minimise the number of terms in the sum  

*among sums satisfying 1, maximise the number of different powers

*among sums satisfying 1 and 2, minimise the number of powers which are larger than the largest repeated power


Suppose we have a "best" representation (which always exists). We claim all powers must be different. Suppose not, and consider the largest repeated power, $k$ (so we have at least two terms of $(-2)^k$, but at most one of each higher power). We have three cases:


*

*If there is a term $(-2)^{k+1}$, delete $(-2)^k+(-2)^k+(-2)^{k+1}$ from the sum. This gives a representation with fewer terms, contradicting 1.

*If there is no term $(-2)^{k+1}$ or $(-2)^{k+2}$, replace $(-2)^k+(-2)^k$ with $(-2)^{k+1}+(-2)^{k+2}$. This gives a representation with the same number of terms, but more different powers, contradicting 2.

*If there is a term $(-2)^{k+2}$ but no $(-2)^{k+1}$, make the same replacement. Now this representation has the same number of terms, at least as many different powers (we have possibly lost $k$ but have gained $k+1$), and fewer terms with higher powers than the new largest repeated power, contradicting 3.


Thus in all cases we get a contradiction, and our "best" representation is valid.
