Powers of two with coefficients $\{1, -1\}$ 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^0n_0 + 2^1n_1 + \dots + 2^{l - 1}n_{l - 1} + 2^ln_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.
 A: Just consider the power of $z$ in the rantional function $$f(z)=\prod_{i=0}^{l}(1+z^{n_i\ 2^i})=\frac{\prod_{i=0}^{l}(1+z^{2^i})}{\prod_{n_i<0}z^{2^i}}=\frac{1+z+z^2+...+z^{2^{l+1}-1}}{\prod_{n_i<0}z^{2^i}}$$
The conclusion follows since $$\sum_{i=0}^{l}n_i2^i<2^{l+1}-1-\sum_{n_i<0}2^i$$.
A: Express $a$ in binary and subtract it bitwise from the upper limit given by the $n_i$. In a given digit $i$, if there is no carry, either nothing is subtracted and $n_i$ remains unchanged, or a $1$ is subtracted, turning a $+1$ into a $0$ and a $-1$ into a $0$ with carry. If there is a carry, either nothing is subtracted, which is equivalent to $1$ being subtracted without carry, or $1$ is subtracted, which is combined with the carry into a carry to the next digit. In all cases, the resulting digit is either $n_i$ or $0$. There can't be a carry beyond $n_l$, since that would imply that $a$ exceeds the upper limit.
A: Put $J=\{k_0,\ldots,k_r\}$, a subset of $I$ to be determined, and for which one should have $a=\sum_{j\in J}n_j2^j$. One can (and should) allow $a=0$, which will correspond to $J=\emptyset$ (with $r=-1$).
Proof by induction on $l$. For $l=0$ take $J=\emptyset$ for $a=0$, and $J=\{0\}$ for $a=1$.
Now suppose $l>0$. Take $0\in J$ if and only if $a$ is odd. Moreover in that case define $a'=a-n_02^0$, while leaving $a'=a$ if $a$ is even. In both cases $a'$ is even, and $0\leq a'\leq \sum_{i=1}^ln_i2^i$
Now one needs to find $J'=J\setminus\{0\}$ such that
$$ a'=\sum_{j\in J'}n_j2^j, $$
but that means $\frac{a'}2$ satisfies the conditions for the shorter sequence $(n_1, \dots, n_l)$ in place of $(n_0, n_1, \dots, n_l)$, and our indiction hypothesis provides the required set $J'$.
