7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you get $0$? If $0=\sum_{i=1}^k (-2)^{a_i}$ then we know that none of the $a_i=0$, since $0$ is even, but then you can divide by $-2$ to get a smaller representation of $0$, ad infinitum. No? $\endgroup$ – lulu Jan 28 at 23:45
  • $\begingroup$ Use induction starting from $1$ for positive integers, and induction starting from $-1$ going downwards for negative integers. $\endgroup$ – rogerl Jan 28 at 23:47
  • $\begingroup$ If you ignore the problem at $0$, I suggest doing a double induction. Establish that you can get the first few positive integers, and the first few negative integers and then show inductively that you can always get the next positive and the next negative integer (either by dividing by $-2$ or by subtracting $1$ and then dividing by $-2$). $\endgroup$ – lulu Jan 28 at 23:54
  • $\begingroup$ They have specified that the empty set is a set so I assume the empty set qualifies 0 as existing. Thanks I didn't think of just inducting both ways. $\endgroup$ – user3645925 Jan 28 at 23:59
  • $\begingroup$ Ah, if you allow the empty set then you are ok. I think the "simultaneous induction" should work without much fuss for the rest of the integers. $\endgroup$ – lulu Jan 29 at 0:00
8
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ So for the case of negative n then it would literally just trivially be the same except for -n and -n-1 as the left hand side of the equation to start? $\endgroup$ – user3645925 Jan 29 at 23:10
  • $\begingroup$ @user3645925 There is no difference with $-n$, though you should go through it yourself as a check. Well, I suppose it is worth noting that if you start with $-1$ the algorithm direct you to subtract $1$, getting $-2$, and then divide by $-2$, which brings you to $1$, which has the same absolute value has the number you started with. All other cases get you a smaller absolute value. Of course we covered $\pm 1$, and more, in the base cases. $\endgroup$ – lulu Jan 30 at 2:15
2
$\begingroup$

With just the $(-2)^0$ -bit, this can represent $\{0, 1\}$.

With $2$ -bits of values $(-2)^1$ and $(-2)^0$, this can represent $\{-2, -1\}\cup \{0, 1\}$.

With $3$ -bits of values $(-2)^2$, $(-2)^1$ and $(-2)^0$, this can represent $\{-2, -1, 0, 1\} \cup \{2, 3, 4, 5\}$.


Proposition: with $n$ -bits, if $O$ is the greatest odd number smaller than $n$, then the lower bound is the sum $$-2^1 - 2^3 - 2^5 - \cdots -2^O,$$ while if $E$ is the greatest even number smaller than $n$, then the upper bound is the sum $$2^0 + 2^2 + 2^4 + \cdots + 2^E,$$ subject to empty sum when $O$ or $E$ is negative.

Let $S_n$ be the set of integers representable by $n$ -bits.

$$\begin{align*} S_{n} &= \left[-\sum_{0\le i< n, 2\not\mid i}2^i\quad ,\quad \sum_{0\le i< n, 2\mid i}2^i\right]\cap \mathbb Z\\ &= \left[-2\cdot \frac{4^{\lfloor n/2\rfloor}-1}{4-1}\quad ,\quad \frac{4^{\lceil n/2\rceil}-1}{4-1}\right]\cap \mathbb Z\\ &= \left[-2\cdot \frac{4^{\lfloor n/2\rfloor}-1}{3}\quad ,\quad \frac{4^{\lceil n/2\rceil}-1}{3}\right]\cap \mathbb Z\\ \end{align*}$$


Assume that $k$ -bits (of values $(-2)^0, \ldots , (-2)^{k-1}$) can represent the following range of integers, inclusive:

$$\begin{align*} S_{k} &= \left[-2\cdot \frac{4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad \frac{4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ \end{align*}$$

Then the next -bit of value $(-2)^k$ can additionally represent integers in the set

$$\begin{align*} T_{k+1} &=\left\{(-2)^k + s \mid s\in S_k\right\}\\ &= \left[(-2)^k-2\cdot \frac{4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad (-2)^k + \frac{4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z \end{align*}$$

  • If $k$ is odd and $(-2)^k < 0$, then $(-2)^k = -2^k = -2\cdot 4^{\lfloor k/2\rfloor}$ and the set $T_{k+1}$ is $$\begin{align*} T_{k+1} &= \left[-2\cdot 4^{\lfloor k/2\rfloor}-2\cdot \frac{4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad -2\cdot 4^{\lfloor k/2\rfloor} + \frac{4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[-2\cdot 4^{\lfloor k/2\rfloor}-2\cdot \frac{4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad -2\cdot 4^{\lfloor k/2\rfloor} + \frac{4\cdot 4^{\lfloor k/2\rfloor}-1}{3}\right]\cap \mathbb Z\\ &= \left[-2\cdot \frac{3\cdot 4^{\lfloor k/2\rfloor} + 4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad \frac{-6\cdot 4^{\lfloor k/2\rfloor} + 4\cdot 4^{\lfloor k/2\rfloor}-1}{3}\right]\cap \mathbb Z\\ &= \left[-2\cdot \frac{4\cdot 4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad -2\cdot\frac{4^{\lfloor k/2\rfloor}-1}{3}-1\right]\cap \mathbb Z\\ &= \left[-2\cdot \frac{4^{\lfloor (k+1)/2\rfloor}-1}{3}\quad ,\quad \min S_k-1\right]\cap \mathbb Z\\ \end{align*}$$

  • If $k$ is even and $(-2)^k > 0$, then $(-2)^k = 2^k = 4^{\lceil k/2\rceil}$ and the set $T_{k+1}$ is $$\begin{align*} T_{k+1} &= \left[4^{\lceil k/2\rceil}-2\cdot \frac{4^{\lfloor k/2\rfloor}-1}{3}\quad ,\quad 4^{\lceil k/2\rceil} + \frac{4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[4^{\lceil k/2\rceil}-2\cdot \frac{4^{\lceil k/2\rceil}-1}{3}\quad ,\quad 4^{\lceil k/2\rceil} + \frac{4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[\frac{3\cdot 4^{\lceil k/2\rceil} - 2\cdot 4^{\lceil k/2\rceil}+2}{3}\quad ,\quad \frac{3\cdot 4^{\lceil k/2\rceil} + 4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[\frac{4^{\lceil k/2\rceil}-1}{3}+1\quad ,\quad \frac{4\cdot 4^{\lceil k/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[\max S_k+1\quad ,\quad \frac{4^{\lceil (k+1)/2\rceil}-1}{3}\right]\cap \mathbb Z\\ \end{align*}$$

In both cases, the set of integers representable by $k+1$ -bits is

$$\begin{align*} S_{k+1} &= S_k \cup T_{k+1}\\ &= \left[-2\cdot \frac{4^{\lfloor (k+1)/2\rfloor}-1}{3}\quad ,\quad \frac{4^{\lceil (k+1)/2\rceil}-1}{3}\right]\cap \mathbb Z\\ &= \left[-\sum_{0\le i< k+1, 2\not\mid i}2^i\quad ,\quad \sum_{0\le i< k+1, 2\mid i}2^i\right]\cap \mathbb Z\\ \end{align*}$$


By induction, with $n$ -bits all integers between $-2\cdot \dfrac{4^{\lfloor n/2\rfloor}-1}{3}$ and $\dfrac{4^{\lceil n/2\rceil}-1}{3}$ inclusive are representable.

So for any $a\in\mathbb Z$, $a$ will be representable as a base-$(-2)$ number with a sufficient number of -bits.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$).

$\endgroup$
0
$\begingroup$

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:

  1. minimise the number of terms in the sum
  2. among sums satisfying 1, maximise the number of different powers
  3. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.