Powers of two with coefficients {1,−1}

Question

Given a vector $(n_0, n_1, \dots, n_l)$ where $n_i \in \{-1, 1\}$, $i = \overline{0, l-1}, n_l = 1$ and $l \in \mathbb{N}$.
Prove that for all $a$ such that $$0 < a \leq 2^0\cdot n_0 + 2^1 \cdot n_1 + \dots + 2^{l - 1} \cdot n_{l - 1} + 2^l \cdot n_l$$

there are distinct $k_0, k_1, \dots, k_r \in I = \{0, 1, \dots, l\}$ where $r \leq l$ such that

$$a = n_{k_0} \cdot 2^{k_0} + n_{k_1} \cdot 2^{k_1} + \dots + n_{k_r} \cdot 2^{k_r}\;.$$

Any help is appreciated.

Answer 1

Any $N\ge0$ has a unique binary expansion $$ N=\sum_{k=0}^n a_k 2^k, \quad a_k\in\{0,1\},\ a_n=1. $$ (Here $n=\lfloor \log_2 N\rfloor$.) Now consider the map $N\mapsto 2N-(2^{n+1}-1)$ from $\mathbb Z_+$ to $\mathbb Z$. We have $$ N'=2N-(2^{n+1}-1)=\sum_{k=0}^n a'_k 2^k, \quad a'_k\in\{-1,1\}, $$ where $a_k'=2a_k-1$. This map is 1-1, hence the result. (So, in fact, we can expand negative integers in such a series as well as positive ones.)