42
$\begingroup$

What does this number equal if it goes on forever? $$\frac{\frac{\frac{\frac{\frac{1}{2}}{\frac{3}{4}}}{\frac{\frac56}{\frac78}}}{\frac{\frac{\frac{9}{10}}{\frac{11}{12}}}{\frac{\frac{13}{14}}{\frac{15}{16}}}}}{\frac{\frac{\frac{\frac{17}{18}}{\frac{19}{20}}}{\frac{\frac{21}{22}}{\frac{23}{24}}}}{\frac{\frac{\frac{25}{26}}{\frac{27}{28}}}{\frac{\frac{29}{30}}{\frac{31}{32}}}}}$$ $$.$$$$.$$$$.$$

Treat the fraction in blocks, one divides what is under it, then that pair is divided by the next pair, those four are divided by the next four. ETC

Edit. I'm reformatting as I can't read the original... aged eyes I guess ;-( but in deference to almagest's comment I am leaving the original too. $$\frac{\frac{\frac{1}{2}\Big/\frac{3}{4}}{\frac{5}{6}\Big/\frac{7}{8}}\Bigg/ \frac{\frac{9}{10}\Big/\frac{11}{12}}{\frac{13}{14}\Big/\frac{15}{16}}} {\frac{\frac{17}{18}\Big/\frac{19}{20}}{\frac{21}{22}\Big/\frac{23}{24}}\Bigg/ \frac{\frac{25}{26}\Big/\frac{27}{28}}{\frac{29}{30}\Big/\frac{31}{32}}} \cdots$$

$\endgroup$
14
  • $\begingroup$ You should write where is the main fraction... ($x=\frac{1}{\frac{2}{3}}$ or $x=\frac{\frac{1}{2}}{3})$? $\endgroup$ – Bman72 Sep 9 '14 at 6:36
  • 1
    $\begingroup$ Observation: whether a number ends up on the top or the bottom of the reduced fraction depends on its binary representation. $\endgroup$ – Dan Brumleve Sep 9 '14 at 6:39
  • $\begingroup$ @Dan I think that kind of comment is wasted here. I wonder if someone will insist on re-formatting the question. That would be a pity. It is quite fun! $\endgroup$ – almagest Sep 9 '14 at 6:41
  • 1
    $\begingroup$ If $k-1$ has an even number of bits, $k$ ends up in the numerator, else $k$ ends up in the denominator. My guess is that the limit is $1$ since both should be equally probable? $\endgroup$ – Dan Brumleve Sep 9 '14 at 7:03
  • 2
    $\begingroup$ @MarcvanLeeuwen That sequence is indeed divergent if you take the limit of partial products up to $n$ terms, because the terms don't even tend to 1. But if you interpret the question as the limit of the sequence terminating the process after some number of recursive divisions, the limit is over partial products of the first $2^n$ terms. This does converge. $\endgroup$ – Holographer Sep 9 '14 at 16:10
15
$\begingroup$

The product converges. Here's a proof:

Take 4 consecutive terms, beginning with $4k+1$ for some integer $k$. The binary expansion of these 4 terms will be some sequence of bits, followed by 00,01,10,11. The terms will contribute $\left(\frac{(4k+1)(4k+4)}{(4k+2)(4k+3)}\right)^{\pm1}$ to the product, the exponent depending on the number of bits that are 1 in the preceding sequence. This is asymptotically $(1\mp\frac{1}{8k^2})$, so the product converges by comparison.

In fact, we can do slightly better, by evaluating $$ \prod_{k=0}^\infty \frac{(4k+1)(4k+4)}{(4k+2)(4k+3)}=\frac{\sqrt{\pi } \Gamma \left(\frac{3}{4}\right)}{\Gamma \left(\frac{1}{4}\right)}\approx 0.599 $$ to give us a bound on the value, which is between this number and its reciprocal, around 1.669.

This method could be improved to include 8 consecutive terms, or 16, and so on, to improve the bound. For example, doing the product for the first five layers and then estimating the remainder by a method of grouping terms in 8s gives a bound of between 0.703676 and 0.708679.

Perhaps this can even be done systematically to get a proof of the whole thing.


To add to the evidence in @David's claim that the series converges to $\frac1{\sqrt2}$, here's a log plot of the error against the number of layers, up to 20 layers. I plot the difference between the proposed limit and the partial products. Partial product error

Looks like exponential convergence to me!

As a physicist, this constitutes a proof. $\quad\square$

$\endgroup$
2
  • 28
    $\begingroup$ I was tempted to question your rigour, but then I read that you are a physicist. $\endgroup$ – Gahawar Sep 9 '14 at 12:11
  • 5
    $\begingroup$ Such an easy way out! $\endgroup$ – Isomorphism Sep 9 '14 at 16:44
19
$\begingroup$

SPOILER. Computation of the expression out to $20$ levels suggests strongly that the answer is...

... don't rollover unless you really want to see it...


$\displaystyle\frac{1}{\sqrt2}$

$\endgroup$
0
12
$\begingroup$

To formulate the question a bit differently:

given $a_{0}(n)=n, a_{k+1}(n)=\frac{a_{k}(2n-1)}{a_{k}(2n)}$

find: $\lim_{k\rightarrow \infty}a_{k}(1)$

EDIT:

Since it was established the sequence converges to a limit, maybe we can do something fishy...

define: $L(n)=\lim_{k\rightarrow \infty}a_{k}(n)$

then as expected $L(0)=0$ but $L(1)=\frac{L(1)}{L(2)}=\frac{\frac{L(1)}{L(2)}}{\frac{L(3)}{L(4)}}=...$

$\endgroup$
2
  • $\begingroup$ Can you little bit explain your formula. I didn't understand it. $\endgroup$ – Bumblebee Sep 10 '14 at 3:08
  • 1
    $\begingroup$ The formula works by always looking at the upper left rectangle of the expression as edited by Jonas Meyer. For example: $a_{0}(1)=1,a_{1}(1)=\frac{1}{2},a_{2}(1)=\frac{\frac{1}{2}}{\frac{3}{4}}...$ $\endgroup$ – user174513 Sep 10 '14 at 5:59
7
$\begingroup$

It seems the exponents follow the Thue-Morse pattern. Wikipedia shall give more information. There is also a nice article of Allouche/Shallit titled "the ubiquituous Thue-Morse constant (.ps-file)". Also a recent answer in MSE or MO deals with that sequence.

Taking the log gives then the infinite sum of logarithms $@1-@2-@3+@4-@5+@6+@7-@8... $ where the $@$ means the logarithm (I'm typing on my phone) and the signs alter with the pattern of the Thue-Morse sequence.

The series does not obviously diverge to neg-infinity but possibly a limit exists.

Here is a screenshot of the Shalit/Allouche paper on the "ubiquituous thue morse-sequence" :


bild
One version for the limit is given as ${\sqrt2\over2}$ but I observe that this is undestood as evaluated at each second partial product - maybe the limit for the partial product if evaluated at each single number is different, don't know.

$\endgroup$
2
  • $\begingroup$ I enjoyed the @ symbol explanation. I will look into it, thank you. $\endgroup$ – user142198 Sep 10 '14 at 7:58
  • 2
    $\begingroup$ It's worth noting that $$\frac{\sqrt 2}2=\frac1{\sqrt 2}$$ $\endgroup$ – Alice Ryhl Sep 12 '14 at 22:07
4
$\begingroup$

Here is the material for a proof. My little knowledge in mathematics does not allow me to fill the gaps, but surely someone else can.

Let $S$ be the infinite fraction.
The first thing to do is to flatten the fraction. By that I mean to express $S$ as a product of fractions $p/q$, with $p, q \in \mathbb{N}$. In other words, find and expression $P$, such that $P := \prod \frac pq = S$.

@karvens' comment got me started:

I think the question is about the closed form for: $\frac{1}{2}\frac{4}{3}\frac{6}{5}\frac{7}{8}\cdots$

Obviously all naturals occur inside $P$, the only real problem is to find out whether or not a fraction is proper (i.e. when to swap numerator and denominator). It turns out¹ that there is a profound link between this problem and the Thue-Morse sequence (I now see that others had already pointed this out). In fact, we can write: $$P := \prod_{n = 0}^\infty \left ( \frac{2n + 1}{2n + 2} \right )^{\left [ (-1)^{t_n} \right ]}$$

where $t_n$ denotes the $n$-th digit (either $0$ or $1$) in the infinite Thue-Morse sequence. $t$ starts as follows (first $32$ digits): $$01101001100101101001011001101001\dots$$

With the expression $\displaystyle\frac{2n + 1}{2n + 2}$ we are able to scan all natural numbers in pairs and when $t_n$ is $1$, we swap. Expansion of $P$ to the first fractions yields: $$\frac{1}{2}\cdot\frac{4}{3}\cdot\frac{6}{5}\cdot\frac{7}{8}\cdot\frac{10}{9}\cdot\frac{11}{12}\cdot\frac{13}{14}\cdot\frac{16}{15}\cdot\frac{18}{17}\cdot\frac{19}{20}\cdot\frac{21}{22}\cdot\frac{24}{23}\cdot\frac{25}{26}\cdot\frac{28}{27}\cdot\frac{30}{29}\cdot\frac{31}{32}$$

Now, it can be demonstrated that: $$P = \frac {\sqrt{2}} 2 = \frac 1 {\sqrt{2}}$$

See Allouche and Shallit 2003, pp. 153 and 204. On page 204 there are typos, you can find the corrections here (pdf).

I tried to find those pages online, but Google Books has only 4 unrelated example pages. Also, I couldn't find this result mentioned anywhere online but on MathWorld (Wikipedia does not reference this result explicitly). MathWorld mentions two other interesting products as well.

Note: as @Gottfried Helms stated in the comments below, this result is already in a paper of 1998/1999 of Shallit/Allouche, The ubiquitous Prouhet-Thue-Morse sequence.


[1]: I did some experimenting with a small Python program. Here it is: https://gist.github.com/rubik/bbb903734c6221f81ed0

EDIT: I've added a Haskell translation of the algorithm. After compilation it takes a little less time than the Python one.

$\endgroup$
5
  • $\begingroup$ @Dan Brumleve: What do you think? $\endgroup$ – rubik Sep 10 '14 at 12:35
  • 1
    $\begingroup$ Excellent. You've essentially given out the answer/where to find it It is also said the answer to this specific question can be found in:D.R Woods Elementary problem proposal E 2692 $\endgroup$ – user174513 Sep 10 '14 at 13:19
  • $\begingroup$ The result is already in a paper of 1998 of Shallit/Allouche ("the ubiquituous thue-morse-constant") and was recently available online as pdf-file. See my screenshot of a copy which I've downloaded about 2004. $\endgroup$ – Gottfried Helms Sep 10 '14 at 16:34
  • $\begingroup$ @GottfriedHelms: Oh thank you for posting the screenshot! I found the PDF here: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.144 $\endgroup$ – rubik Sep 10 '14 at 16:40
  • $\begingroup$ @ rubik: you're welcome! $\endgroup$ – Gottfried Helms Sep 10 '14 at 16:48
0
$\begingroup$

HINT:
let $u_n=\dfrac{n}{n+1}$ and $v_n=\dfrac{u_n}{u_{n+1}}$ where $n=1,2,3,..$
I think here you are asking about the$ \lim_{ n \to \infty} v_n.$

$\endgroup$
3
  • 1
    $\begingroup$ I think the question is about the closed form for $$\frac{1}{2}\frac{4}{3}\frac{6}{5}\frac{7}{8}\cdots$$ I don't get what you mean by the limit of $v_n$. Isn't that just 1? $\endgroup$ – karvens Sep 9 '14 at 6:43
  • 1
    $\begingroup$ You have $v_8 = \frac{\frac{8}{9}}{\frac{9}{10}} = \frac{80}{81}$, but I think OP means $\frac{\frac{\frac{1}{2}}{\frac{3}{4}}}{\frac{\frac{5}{6}}{\frac{7}{8}}} = \frac{7}{10}$ $\endgroup$ – Dan Brumleve Sep 9 '14 at 6:54
  • $\begingroup$ Thanks. I was wrong. But I think this may be helps to get some approach to this question $\endgroup$ – Bumblebee Sep 9 '14 at 10:00