21
$\begingroup$

How do I show that

$$\dfrac{2^{\left\lfloor\frac12 a_1\right\rfloor} + 2^{\left\lfloor\frac12 a_2\right\rfloor} + \ldots + 2^{\left\lfloor\frac12 a_n \right\rfloor}}{2^{\left\lceil\frac12 a_1\right\rceil} + 2^{\left\lceil\frac12 a_2\right\rceil} + \ldots + 2^{\left\lceil\frac12 a_n \right\rceil}}$$

represents all rationals between $\dfrac{1}{2}$ and $1$, where $a_1, a_2, \ldots, a_n \in \mathbb{N}$?

I have tried representing few rationals such as $\dfrac{7}{8}$ and $\dfrac{5}{8}$ and it seems like we can represent all of them. However I'm not completely sure why and don't have a rigorous proof.

For example

$$\dfrac{5}{8} = \dfrac{2^{\left\lfloor\frac12 3\right\rfloor} + 2^{\left\lfloor\frac12 4\right\rfloor} + 2^{\left\lfloor\frac12 5 \right\rfloor}}{2^{\left\lceil\frac12 3\right\rceil} + 2^{\left\lceil\frac12 4\right\rceil} + 2^{\left\lceil\frac12 5 \right\rceil}}$$

$$\dfrac{7}{8} = \dfrac{2^{\left\lfloor\frac12 1\right\rfloor} + 2^{\left\lfloor\frac12 2\right\rfloor} + 2^{\left\lfloor\frac12 4 \right\rfloor}}{2^{\left\lceil\frac12 1\right\rceil} + 2^{\left\lceil\frac12 2\right\rceil} + 2^{\left\lceil\frac12 4 \right\rceil}}$$

Any help would be highly appreciated. Thanks

$\endgroup$
11
  • 3
    $\begingroup$ Two questions: 1) Unfortunately, there's no concensus in Mathematics about $0$ being in $\mathbb N$ or not. Can the $a_i$'s be $0$? 2) Can $a_1, a_2,\ldots a_n$ repeat or they have to be different? $\endgroup$ – jjagmath Mar 28 at 13:45
  • 1
    $\begingroup$ It does not matter whether $0$ is considered to be in $\mathbb{N}$ or not, since you can represent the same rational by increasing all the $a_i$'s by $2$. But could OP clarify if the $a_i$'s need to be distinct? $\endgroup$ – Haran Mar 28 at 14:20
  • 1
    $\begingroup$ @Haran No there's no condition which says that the $a_i$'s should be distinct. They all can be same. Thanks. $\endgroup$ – BookWick Mar 28 at 14:48
  • 1
    $\begingroup$ Let $A=\{a_1,\cdots,a_n\}$. The expression can be written as $$\frac{\sum\limits_{m=1}^n2^{\lfloor a_i/2\rfloor}}{\sum\limits_{m=1}^n2^{\lceil a_i/2\rceil}}=\frac{\sum\limits_{i=1}^k2^{b_i-1}+\sum\limits_{j=k+1}^n2^{b_j}}{\sum\limits_{i=1}^k2^{b_i}+\sum\limits_{j=k+1}^n2^{b_j}}\in\left[\frac12,1\right]$$ where $(b_i)_{i\le k}$ correspond to all odd elements of $A$ and $(b_j)_{k+1\le j\le n}$ to all even elements. Since each of $b_1,\cdots,b_n$ is at least one, for any reduced rational $p/q$ in this domain, we can write $\sum\limits_{i=1}^k2^{b_i-1}=q-p$ and $\sum\limits_{j=k+1}^n2^{b_j}=2p-q$. $\endgroup$ – TheSimpliFire Mar 28 at 15:48
  • 1
    $\begingroup$ This completes the proof as the choice of $(b_j)_{k+1\le j\le n}$ is independent of the choice of $(b_i)_{i\le k}$, and every positive integer has a unique binary representation. Moreover, any rational number $P/Q$ can be written as $kp/kq$ (where $p/q$ is reduced), so we just need to scale $q-p$ and $2p-q$ up by a factor of $k$. $\endgroup$ – TheSimpliFire Mar 28 at 15:52
6
$\begingroup$

Some nice answers have been posted, but I'm still adding this answer since it gives a straightforward non-recursive way to get a representation.

That the expression is in $[{1 \over 2},1]$ is easy to see.

For the other way, consider ${x \over y} \in [{1 \over 2},1]$ and let $m=y-x$. Then $x-m \geq 0$.

Express $x-m=(a_k a_{k-1} \dots a_0)_2$ and $m=(b_l b_{l-1} \dots b_0)_2$ expressed in binary [$0 \notin \{a_k,b_l\}$].

Then, I claim that $\{2i : a_i = 1\} \cup \{2j+1 : b_j =1 \}$ gives our representation.

Indeed, $$ {\sum_{a_i=1}2^{\lfloor{2i \over 2}\rfloor}+\sum_{b_j=1}2^{\lfloor{2j+1 \over 2}\rfloor} \over \sum_{a_i=1}2^{\lceil{2i \over 2}\rceil}+\sum_{b_j=1}2^{\lceil{2j+1 \over 2}\rceil}} = {\sum_i a_i 2^i+\sum_j b_j 2^j \over \sum_i a_i 2^i+\sum_j b_j 2^{j+1}} = {x-m+m \over x-m+2m} = {x \over y} $$ The last line is due to the fact that in case of non-integers (i.e. ${2j+1 \over 2}$), the ceilings increase the powers of $2$ by $1$ and hence the number expressed is multiplied by $2$.

As an example, for $7 \over 10$, $x=7,y=10,m=3$.

Now, $x-m=4=(100)_2$ and $m=3=(11)_2$.

Using our algorithm, the representative numbers are $4,3,1$.

Indeed, ${2^{\lfloor{4 \over 2}\rfloor}+2^{\lfloor{3 \over 2}\rfloor}+2^{\lfloor{1 \over 2}\rfloor} \over 2^{\lceil{4 \over 2}\rceil}+2^{\lceil{3 \over 2}\rceil}+2^{\lceil{1 \over 2}\rceil}} = {2^2+2^1+2^0 \over 2^2+2^2+2^1} = {4+2+1 \over 4+4+2} = {7 \over 10}$.

I just noticed that @TheSimpliFire has done a similar thing in the comments, but I started writing it sometime ago, had some coffee, and then finished it. So I somehow missed his/her comment. Anyway, if you (@TheSimpliFire) decide to make it into an answer, please let me know and I'll remove mine.

$\endgroup$
2
  • 1
    $\begingroup$ @Haran Sorry, typo. $\endgroup$ – MathIsNice1729 Mar 28 at 17:11
  • 1
    $\begingroup$ You need not to justify an answer which is similar to a comment. $\endgroup$ – user Apr 1 at 9:34
6
$\begingroup$

There is an argument using the Farey tree. Briefly, the Farey algorithm fills in rational numbers between $x = \frac{p}{q}$ and $y = \frac{r}{s}$ by $\frac{p+r}{q+s}$ (and so on recursively) [What some have called the Bart Simpson addition of fractions). The basic fact is that if you start with $\frac12$ and $1,$ the next number you generate is $\frac{1+1}{1+2} = \frac23,$ the next two are $\frac12 + \frac23$ and $\frac23 +1$ (where + is the Bart Simpson sum), this procedure will generate all the rational numbers in the interval $[\frac12, 1].$

It is not hard to see that numbers as in the OP behave nicely with respect to the Bart Simpson addition: if $x$ and $y$ both have an $a_i,$ then their Bart Simpson sum has $a_i+2.$ It also needs to be checked that $\frac12$ and $1$ can be represented, but that is easy. So, to summarize, the bart simpson sum of two numbers having the required representation also has the required representation, which gives both a proof and an algorithm to construct the representation.

$\endgroup$
6
  • $\begingroup$ Could you please elaborate the Farey Tree and Farey Algorithm and how it relates to this problem? Thanks. $\endgroup$ – BookWick Mar 28 at 15:13
  • $\begingroup$ @BookWick OK, done. $\endgroup$ – Igor Rivin Mar 28 at 16:18
  • $\begingroup$ Why the downvotes? $\endgroup$ – Igor Rivin Mar 29 at 13:31
  • 1
    $\begingroup$ @BookWick I did not think it was you. Just disappointed that people downvote things they (apparently) don't understand. $\endgroup$ – Igor Rivin Mar 29 at 16:36
  • 1
    $\begingroup$ Yeah that's a pretty sad thing. Never mind :( $\endgroup$ – BookWick Mar 30 at 8:19
5
$\begingroup$

We can observe that $2^{\lfloor a/2 \rfloor}$ and $2^{\lceil a/2 \rceil}$ are simply powers of $2$ which are either equal or consecutive. Hence: $$2^{\lfloor a/2 \rfloor} \leqslant 2^{\lceil a/2 \rceil} \leqslant 2 \cdot 2^{\lfloor a/2 \rfloor}$$ Taking these bounds in our expression shows that any rational expressed in the given form must be between $\frac{1}{2}$ and $1$. Now, we will show that all rationals in $[\frac{1}{2},1]$ can be expressed in the given form by inducting over the size of the denominator.

The result holds good when the denominator is $1$ or $2$, by expressing $1$ and $\frac{1}{2}$ as they are. Now, assume that we are to show that $\frac{x}{y}$ can be expressed in the given form.

First, we can see that since $\frac{x}{y}<1$, it follows: $$\frac{x-1}{y-1}<\frac{x}{y}<1$$ Moreover, if we assume $\frac{x-1}{y-1}<\frac{1}{2}$, then: $$\frac{x-1}{y-1}<\frac{1}{2}<\frac{x}{y} \implies 2x-1<y<2x$$ which is clearly a contradiction. Hence, $\frac{x-1}{y-1}$ lies in $[\frac{1}{2},1]$ and can thus be expressed in the given form. Now, simply write $\frac{x}{y}$ in the given form by writing: $$\frac{x}{y} = \frac{(x-1)+1}{(y-1)+1}$$

Note: Sometimes, the fraction $\frac{x-1}{y-1}$ might not be in simplified form. Simply consider the expression of this rational number in its simplest form, and repeat the terms in the numerator and denominator till the sum in the numerator is $x-1$ and in the denominator is $y-1$.

Example: Assume we need to express $\frac{16}{25}$ in the given form. We first write: $$\frac{16}{25} = \frac{15+1}{24+1}$$ Now, we have: $$\frac{15}{24}=\frac{5}{8}=\frac{2+2+1}{4+2+2}$$ Hence: $$\frac{16}{25} = \frac{3(2+2+1)+1}{3(4+2+2)+1} = \frac{2+2+2+2+2+2+1+1+1+1}{4+4+4+2+2+2+2+2+2+1}$$

$\endgroup$
2
  • $\begingroup$ I think you didn't show that all numbers in $[\dfrac{1}{2} , 1]$ can be represented in that closed form? $\endgroup$ – BookWick Mar 29 at 11:15
  • $\begingroup$ I have, the induction establishes that all fractions in that interval with denominator $y$ can be expressed in that form. $\endgroup$ – Haran Mar 29 at 15:13
3
$\begingroup$

Let's group the parameters $a_i$ into two groups, the even and odd numbers (lets call them $e_i$ and $o_i$ resp).

Notice that $2^{\lceil e_i/2 \rceil} = 2^{\lfloor e_i/2 \rfloor} $ while $2^{\lceil o_i/2 \rceil} = 2 \times 2^{\lfloor o_i/2 \rfloor} $

Now, let $\frac12 <Z<1$ with $Z=\frac{X}{Y}$, where $ X, Y \in \mathbb{N}$

Let $D=Y-X$ and $C=2X -Y$, with $C, D>0$. Also, $X=D+C$ and $Y=C+2D$.

Then $$Z=\frac{C+D}{C+2D}$$

Further, any natural number can be expressed as sum of powers of two: $C = 2^{c_1} + 2^{c_2} + \cdots 2^{c_j}$, where $(c_1, \cdots c_j)$ correspond to the positions of the ones in the binary digits of its binary representation. Analogously, $D = 2^{d_1} + 2^{d_2} + \cdots 2^{d_k}$

Now, let $e_i = 2 c_i$ and $o_i = 2 d_i +1$, and we are done.


An example follows: Let $Z = \frac{11}{17}$, then

$$C= 2\times 11 -17=5 = 2^0 +2^2 \implies c_i=(0 , 2) \implies e_i=(0 , 4)$$

$$D=17-11=6 = 2^1 + 2^2\implies d_i=(1 , 2) \implies o_i=(3 , 5) $$

and $a_i = (0,4,3,5)$. Indeed:

$$ \dfrac{ 2^{\lfloor 0/2\rfloor} + 2^{\lfloor 4/2\rfloor} + 2^{\lfloor 3/2\rfloor} + 2^{\lfloor 5/2\rfloor} } { 2^{\lceil 0/2\rceil} + 2^{\lceil 4/2\rceil} + 2^{\lceil 3/2\rceil} + 2^{\lceil 5/2\rceil} } =\dfrac{1+4+2+4}{1+4+4+8}=\dfrac{5+6}{5+2\times 6}=\frac{11}{17} $$

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