I don't undestand. For all natural k we have $k=\sum_{i=1}^{n}2^{b_{i}}$, were $b_{i}$ are distinct nonnegative integers. $0=1-1$.

Example for n=2 1=2-1 2=4-2 3=2+1 4=2+2 5=4+1 6=4+2 7=8-1 8=4+4 9=8+1 10=8+2 11=??????? d2=11

N.T.TUAN wrote: Let $n$ be a positive integer. Find, with proof, the least positive integer $d_{n}$ which cannot be expressed in the form \[\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}}, \] where $a_{i}$ and $b_{i}$ are nonnegative integers for each $i.$ Very nice problem. The answer is $d_{n}=2\frac{4^{n}-1}{3}+1$ Notations : a) $\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}}=(a_{i},0,\cdot,a_{i-1},\cdot,0,\cdot,a_{1},0,0,\cdot)$, each $a_{i}$ being at the $b_{i}^{th}$ position from the right. b) If k may be written with such exactly n nonzero positions, I'll write that k has a n_representation Lemma L1 : Obviously, any number equal to 3 modulus 4 ends with either $(1,1)$, either $(0,-1)$. Lemma L2 : If a number has a p_representation, it also has a q_representation for any $q>p$ : Leftmost position is always $1$. $(1,$ anything with $p-1$ nonzero values$)=(1,$ $q-p$ values $-1,$ the same anything as LHS $)$ Lemma L3 : If k has a p_representation ($p\geq 1$), $k+1$ has a $(p+1)$_reprentation. Easy with induction on k: If 1 has a p_representation($p\geq 1$), 2 has a $(p+1)$_reprentation (since $2=(1,0)$ + Lemma L2) If k=$2u$ has a p_representation ending with 0, $k+1$ has obviously a $p+1$_representation, (by adding a $1$ at righmost position) If k=$2u+1$ has a p_representation ending with +1, $u$ has obviously a $(p-1)$_representation, so $u+1$ has a $p$_representation (induction), and $k+1=2u+2$ has a p_representation, and so a $(p+1)$_reprentation (Lemma L2) edited : If k=$2u-1$ (we must consider that the number we are studying may end with 0, 1 or also -1) has a p_representation ending with -1, $k+1=2u$ has a $(p-1)$_representation (suppress the rightmost -1), and so also a $(p+1)$_reprentation (Lemma L2) Easiest proof now is with induction. 1) $n=1$ $1=(1)$ $2=(1,0)$ $3$ can't be written with just one nonzero value (see lemma L1 above). And $d_{1}=3=2\frac{4^{1}-1}{3}+1$ 2) assume the propery is verified up to rank $n\geq 1$. Let $m=d_{m}-1$ 2.1) $1, 2$ and $3$ has a $(n+1)$_representation : $1=(1)$ + Lemma L2 $2=(1,0)$ + Lemma L2 $3=(1,1)$ + Lemma L2 if necessary ($n>2$) 2.2) For any $q\in[4,4m+2]$ q has a $(n+1)$_representation : If $q=4k$ with $k\leq m$, $k$ has a $n$_representation (induction), so a $(n+1)$_representation (Lemma L2), so has q (adding $(0,0)$ at the right. If $q=4k+1$ with $k\leq m$, $k$ has a $n$_representation (induction), so q has a $(n+1)$_representation (adding $(0,1)$ at the right. If $q=4k+2$ with $k\leq m$, $k$ has a $n$_representation (induction), so q has a $(n+1)$_representation (adding $(1,0)$ at the right. If $q=4k+3=4(k+1)-1$ with $k+1\leq m$, $k+1$ has a $n$_representation (induction), so q has a $(n+1)$_representation (adding $(0,-1)$ at the right of the reprentation of $k+1$. 2.3) $4m+3$ don't have a $(n+1)$_representation If $4m+3$ has a $(n+1)$_representation, it ends with $(1,1)$ or $(0,-1)$ (Lemma L1). If it ends with $(0,-1)$, by deleting these 2 rightmost numbers, we have a n_representation of $m+1$, in contradiction with induction $m=d_{n}-1$ If it ends with $(1,1)$, by deleting these 2 rightmost numbers, we have a $(n-1)$_reprentation of $m$, so it exist a n_representation of $m+1$ (Lemma L3), in contradiction with induction $m=d_{n}-1$. So $d_{n+1}=4m+3=4d_{n}-1=4(2\frac{4^{n}-1}{3}+1)-1=2\frac{4^{n+1}-1}{3}+1$ Q.E.D. -- Patrick

Rust wrote: I don't undestand. For all natural k we have $k=\sum_{i=1}^{n}2^{b_{i}}$, were $b_{i}$ are distinct nonnegative integers. $0=1-1$. Are you sure? Remember that $n$ is FIXED. @pco: Thank you very much! I will check your solution later, i am busing.

Yes. I don't read, that n fixed. For these case obviosly minimal number $d_{n}=1010...1011=1+2*(1+...+4^{n-1})=1+2*\frac{4^{n}-1}{3}.$

Here is an inductive argument (which I hope works). Solution Let a positive integer that can be expressed in the stated form be defined as $n$-good. We claim that the minimal number that is not $n$-good is $d_n = 2 \left( \frac{4^n - 1}{3} \right) +1$. We will prove this in two steps. Step 1: All $m \in \mathbb{N}$ such that $1 \le m \le 2 \left( \frac{4^n - 1}{3} \right)$ are $n$-good. Proof: Assume that the hypothesis holds for $n=k$. Therefore all $1 \le m \le 2 \left( \frac{4^k - 1}{3} \right)$ can be expressed in the described way. Since $1=2^{k}-2^{k-1}-2^{k-2} - \dots - 2^0$, $1$ is $k+1$-good. For any $m$ such that $1 \le m \le 2 \left( \frac{4^k - 1}{3} \right)$ consider the expressions $2^l \pm m$ where $l=0,1,\dots , 2k+1$. Since $2^{2k-1}<2 \left( \frac{4^k - 1}{3} \right)<2^{2k}$, by this method we achieve an expression with $k+1$ terms for each positive integer less than or equal to $2^{2k+1} + 2 \left( \frac{4^n - 1}{3} \right)= 2 \left( \frac{4^{k+1} - 1}{3} \right)$. Therefore all $m \in \mathbb{N}$ such that $1 \le m \le 2 \left( \frac{4^{k+1} - 1}{3} \right)$ are $k+1$-good. This completes the induction. $\blacksquare$ Step 2: $2 \left( \frac{4^n - 1}{3} \right) +1$ and $\frac{4^{n+1} - 1}{3}$ are not $n$-good. Proof: Assume that both hypotheses hold for $n=k$. Note that any $n$-good number is $m$-good for all natural numbers $m \ge n$. This is because we may exchange a $\pm (2^l)$ in the expression with a $\pm (2^{l+1} - 2^{l})$ to increase the number of terms in the expression without changing the value. Therefore we may assume that there is only one $\pm 1$ since otherwise we can exchange any excess $\pm 1$ for $\pm 2$’s. Note that if a number is not $n$-good, then the minimum number of summands in the expression exceeds $n$. Now assume for contradiction that $2 \left( \frac{4^{k+1} - 1}{3} \right) +1$ is $k+1$-good. Then there must be a $\pm 1$ in the expression since it is an odd number. If it is a $+1$, then subtracting $1$ and dividing by $2$ yields that $\frac{4^{k+1} - 1}{3}$ requires $k$ summands minimum. This contradicts the fact that $\frac{4^{k+1} - 1}{3}$ is not $k$-good. Similarly if it is a $-1$, then adding $1$ and dividing by $2$ contradicts the fact that $2 \left( \frac{4^{k+1} - 1}{3} \right) +1$ is not $k$-good. We arrive at the same contradictions for $\frac{4^{k+1} - 1}{3}$. This completes the induction. $\blacksquare$ Therefore the minimum value is $d_n = 2 \left( \frac{4^n - 1}{3} \right) +1$.

How do you prove that $2\left(\frac{4^{n}-1}{3}\right)+1$ is not $n$-good? I don't quite follow the explanation in the post above...

supercomputer wrote: How do you prove that $2\left(\frac{4^{n}-1}{3}\right)+1$ is not $n$-good? I don't quite follow the explanation in the post above... Here is my own solution, hopefully it will help. I will deal with everything in base $2$. The answer for $n$ is $1010...1011$ where there are $2n$ digits. The goal of the problem can be rethought of as taking a binary number and first adding powers of $2$ onto it (we'll call this part building), then plucking off all the remaining $1$s so that you end up with $0$ (we will call this part the plucking part), (we will call this whole process destroying). Lemma: You can re-destroy $0$. Proof: Let the number of moves required be $r$. If $2 | r$, then all you have to do is add $1$, then pluck it off. Easy. If $r$ is odd and $r > 1$, add a $1$, then add $1$ again to get $10$, then destroy it to get $0$ and now just alternate like before. If $r = 1$, then we have to retrace. The reason why we even include this lemma is if our destroy process hits $0$ before the $n$-th move. Thus, consider what the $n-1$-th move was. It had to be from the plucking stage, which means we were left with $2^a$ for some integer $a$. We have two moves left, so add $2^a$ and then subtract $2^{a+1}$. $\Box$ Part I: Anything less than $1010...1011$ ($2n$ digits) can be destroyed. Assume that for all integers $k < n$, anything less than $1010...1011$ ($2k$ digits) can be destroyed in $k$ moves. The base case of $n = 1$ is quite obvious (there can be at most one $1$, so you just pluck that $1$ off. Now we employ the inductive hypothesis. If the number of $1$s is already at most $n$, then we can just skip the building part and pluck off all the $1$s. Otherwise, suppose we have $\ge n+1$ number of $1$s. If the number has $2n-1$ digits, then just change all the $0$s to $1$s in the building part, which takes at most $n-2$ moves, so we get $11111....1$, then add $1$ to turn it into $10000...0$ and we can pluck that $1$ off. Otherwise, we have $10[\text{some number less than 10...1011 (2n-2 digits)]}$. That text portion, by the inductive hypothesis, can be destroyed in $n-1$ moves. Then just pluck off that last $1$ at the beginning. Part II: $1010...1011$ ($2n$ digits) can not be destroyed. We will strengthen the induction a bit. I claim that, for all $k < n$, both $1010...1011$ ($2k$ digits) and $1010...101$ ($2k-1$ digits) cannot be be destroyed in $k$ moves and $k-1$ moves, respectively. Base case is easy to deal with. Suppose we have $1010...1011$ ($2n$ digits). At some point, we have to either pluck the last two $1$s or build a $1$ on top. If we pluck the last two $1$s, then we are left with $1010...1000$ ($2n$ digits), and now we need to destroy $1010...1$ ($2n-3$ digits) in $n-2$ moves, which is not possible. If we build a $1$, then we get $1010...101100$ ($2n$ digits), which of course, cannot be done due to the inductive hypothesis. So we know that $1010...1011$ ($2n$ digits) cannot be destroyed. Now we need to show that $1010..101$ ($2n-1$ digits) cannot be destroyed in $n-1$ moves. The last step is either a pluck $1$ or build $1$ onto the last digit. You'll arrive at contradictions.

Call a number $x$ $n$-good if we can write $x$ as \[\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}}.\]If a number $x$ is $n$-good then $2x$ is $n$-good because we can add $2$ to each $b_i$ and $x-1,x+1,x+2$ are $n+1$-good. By extension, $4x-1,4x,4x+1,4x+2$ are all $n+1$-good. Thus, if all $i\le x$ were $n$-good then all $i\le 4x+2$ are $n+1$-good. $~$ Note that $1,2$ are $1$-good so all $x\le 10$ are $2$-good. Inductively we see that all $x\le 2(1+4^1+\dots+4^{n-1})$ are $n$-good. We claim that $1+2(1+4^1+\dots+4^{n-1})$ is not $n$-good and thus is our least positive integer $d_n.$ For each $i$ if $\pm 2^i$ appears more than once, we can merge two of them and create a shorter representation. Thus, we assume that each $\pm 2^i$ appears at most once. In particular, we can create a sequence $f(x)=(c_0,c_1,c_2,\dots)$ where $x=c_02^0+c_12^1+c_22^2+\dots$ and $c_i\in \{-1,0,1\}$ for all $i.$ When $x\equiv 3\pmod 4$ we must have $(c_0,c_1)=(0,-1),(1,1),$ or $(-1,1).$ Actually, we may replace $(-1,1)$ with $(0,-1)$, and the representation with $(-1,1)$ will be longer, so $(c_0,c_1)=(0,-1)$ or $(1,1).$ If it is $(0,-1)$ then we require $x+1 = 4(1 + 2(1+4^1+\dots+4^{n-2}))$ to be $n-1$-good, but this requires $\frac{x+1}{4}$ to be $n-1$-good, and so inductively this does not work. If $(c_0,c_1)=(1,1)$ then we require $y=\frac{x-3}{4}=1+4^1+\dots+4^{n-2}$ to be $n-2$-good. This means $2y+1$ is $n-1$-good which is false, so inductively we reach a contradiction. Therefore, $1+2(1+4^1+\dots+4^{n-1})$ is not $n$-good. Thus, our answer is \[d_n=1+2\left(\frac{4^n-1}{3}\right)=\frac{2^{2n+1}+1}{3}\]

Easy induction