Be $K=\{\frac{1}{2^{2}} , \frac{1}{2^{3}}, \frac{1}{2^{4}}...\}$ and $W\subset K$.

Defining $f(W) = \frac{1}{2} + \operatorname{sum}(W) - \operatorname{sum}(K\setminus W)$.

Where sum represents the sum of all the elements of the set. Prove the truth or falsity of the following proposition

For all $a\in \mathbb{Q}\cap [0, 1]$ there is $W\subset K$ such that $f(W)=a$.

If the proposition is not true then what condition must the number have in order for it to fulfil the request?

It may be that $\frac{1}{5}$ is a counterexample but I have not been able to prove it.

  • 3
    $\begingroup$ Seems really true. It’s like playing a game of "The price is right"… if you’re above $a$, take a - sign, and if you’re not, take a + sign ;) $\endgroup$ – Jujustum Jul 21 at 20:27
  • $\begingroup$ In the title you've written $\Bbb Q \cap [0, 1]$ but in the body you've written only $\Bbb Q$. I suspect you mean the former otherwise there are the obvious counterexamples. $\endgroup$ – Aryaman Maithani Jul 21 at 20:29
  • 3
    $\begingroup$ Can you see that $f(W)=\frac12 +2sum(W)-sum(K)=2sum(W)$? Now consider binary representations of real numbers in $[0,\frac12]$ $\endgroup$ – Hagen von Eitzen Jul 21 at 20:29
  • $\begingroup$ The "price is right" game mentioned above is a nice way to approach this and can be made rigorous. Note that once you have processed the term $1/2^k$ then the sum of all the remaining terms is equal to $1/2^k$ thus if you are under/over and then over/under shoot then you never get too far away to not make it back down/up. $\endgroup$ – Winther Jul 21 at 22:02
  • $\begingroup$ If only finite sums are allowed this certainly isn't true. If infinite sums are allowed I'm almost certain it is. $\endgroup$ – K.defaoite Jul 22 at 2:34

Are we talking finite sums or are infinite sums allowed?

If infinite sums are allowed, we show that for every $a \in [0,1]$ and each integer $k$ there is a set $c_1,\ldots, c_2 \in \{-1,1\}$ such that the inequality $$\left|a - \left(\frac{1}{2} + \sum_{j=2}^k c_j2^{-j}\right)\right| \le 2^{-k}.$$ We can show this inequality holds by induction on $k$; here is a sketch of the proof. First note that this is clearly this is true for $k=2$. So let $c_2,\ldots, c_k$ be such that the above inequality holds and set $a_k \doteq \frac{1}{2} + \sum_{j=2}^k c_j2^{-j}$. Then the inequality $|a_k-a| \le 2^{-k}$ holds. If $a_k=a$ then of course we are done; if the strict inequality $a_k > a$ holds, then check for yourself that the inequality $|(a_k+2^{-(k+1)})-a| \le 2^{-(k+1)}$ holds and if the strict inequality $a_k < a$ holds, then check for yourself that the inequality $|(a_k-2^{-(k+1)})-a| \le 2^{-(k+1)}$ holds.

Thus if infinite sums are allowed, there is indeed a sequence $c_2,\ldots, c_k, \ldots$ such that $\lim_{k \rightarrow \infty} a_k = a$ for any $a \in \mathbb{Q} \cap [0,1)$, where $a_k$ is as defined above; $$a_k \doteq \frac{1}{2} + \sum_{j=2}^k c_j2^{-j}.$$

If we are talking finite sums, then no, there are rational numbers $a \in (0,1)$ whose decimal expansion is finite that cannot be expressed as a finite sum in the desired form. For example, if $a=\frac{1}{5}$ could be written as a finite sum as specified above, then for some positive integer $k$ and some integer $m$, this would gives $\frac{1}{5} = \frac{m}{2^k}$, which [using the result $\frac{a}{b}=\frac{c}{d}$ $\Rightarrow$ $bc=ad$] would give $5m =2^k$, which is clearly impossible for integral $m$ and integral $k$.

If you want to show that there is a rational number $a \in (0,1)$ that cannot be written as a finite sum as specified above and you don't care whether $a$'s decimal expansion is finite or not, then the proof is even easier. You can also note that the decimal expansion for $2^{-k}$ is finite for any finite $k$; while there are rational numbers such as $\frac{1}{3}$ for which the decimal expansion is not finite.


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