## Tall fraction puzzle, MSE

I was given this problem 30 years ago by a coworker, posted it 15 years ago to rec.puzzles, and got a solution from Barry Wolk, but have never seen it again.  Consider the series:

$1, \dfrac{1}{2},\dfrac{\dfrac{\ 1\ }{2 }}{\dfrac{3}{ 4}},\dfrac{\ \dfrac{\ \dfrac{\ 1\ }{2}\ }{ \dfrac{\ 3\ }{4}}\ }{\ \dfrac{\ \dfrac{\ 5\ }{6}\ }{\dfrac{\ 7\ }{8}}\ },\ldots$

I don’t know how to format it to show the larger fraction bars, but you can guess, particularly with what follows.  Each fraction keeps its large bars while being put atop a similar structure. [Improved formatting AT]

This can also be represented as $\dfrac{1\cdot 4 \cdot 6 \cdot 7 \dots}{2 \cdot 3 \cdot 5 \cdot 8 \dots}$ terminating at $2^n$ for some $n$, where it is much closer to the limit than elsewhere.

The challenge:

1)Find the limit, not too hard by experiment

2)In the last expression, find a simple, nonrecursive, expression to say whether $n$ is in the numerator or denominator

3)Prove the limit is correct-this is the hard one.

This problem (E 2692) was proposed by D. Woods in Americ. Math. Monthly 85, No.1, p.48, (link needs a subscription) and a solution by E. Robbins was published in Americ. Math. Monthly 86, No. 5, p.394f, (link needs a subscription) in 1979. A solution from 1987 by Jean-Paul Allouche is given in Proposition 5 of Jean-Paul Allouche and Jeffrey Shallit’s paper The ubiquitous Prouhet-Thue-Morse sequence (or here slides 24-28).

In 3. apart from a sketch of Allouche and Shallit’s proof of Proposition 5, I give my interpretation why the limit can be expressed as the infinite product $\displaystyle\prod_{m=0}^{\infty }\left( \dfrac{2m+1}{2m+2}\right)^{(-1)^{t_{m}}}$, where $\left( t_{m}\right) _{m\geq 0}$ is the Prouhet-Thue-Morse sequence. This product is the starting point of their proof.

1. The first few terms of this sequence are

\begin{aligned}\left( f_{n}\right) _{n\geq 0}=\left( 1,\dfrac{1}{2},\dfrac{2}{3},\dfrac{7}{10},\dfrac{286}{405},\dfrac{144\,305}{204\,102},\dfrac{276\,620\,298\,878}{391\,202\,754\,597},\ldots \right)\end{aligned}

These numerical values suggest that $\left( f_{n}^{2}\right) _{n\geq 0}$ converges relatively fast to $\dfrac{1}{2}$, and thus $f_{n}$ to $\dfrac{\sqrt{2}}{2}$:

\begin{aligned} \left( f_{n}^{2}\right) _{n\geq 0}=\left(1, 0.25,0.444\,44,0.49,0.498\,68,0.499\,88,0.499\,99,\ldots \right) \end{aligned}

2. The Prouhet-Thue-Morse sequence (A010060) OEIS page gives the closed form formula (already  in Eelvex’s answer) by Benoit Cloitre (benoit7848c(AT)orange.fr), May 09 2004.

3. The term $f_{n}$ can be written as the product of integers $1\leq k\leq 2^{n}$ raised to $e_{k}\in \left\{ -1,+1\right\}$. For instance,

\begin{aligned}f_{3} &=\dfrac{\ \dfrac{1}{2}/\dfrac{3}{4}\ }{\dfrac{5}{6}/\dfrac{7}{8}}=\dfrac{1}{2}\left( \dfrac{3}{4}\right) ^{-1}\left( \dfrac{5}{6}\left( \dfrac{7}{8}\right)^{-1}\right) ^{-1}=1\cdot 2^{-1}\cdot 3^{-1}4\cdot 5^{-1}\cdot 6\cdot 7\cdot 8^{-1}\\&=\prod_{k=1}^{2^{3}}k^{e_{k}}=\prod_{k=1}^{2^{3}}k^{(-1)^{t_{k-1}}}\end{aligned},

where $\left( t_{k}\right) _{k\geq 0}=\left( 0,1,1,0,1,0,0,1,\ldots \right)$ is the binary sequence known as the Prouhet-Thue-Morse sequence (A010060), which has several equivalent definitions. One that is related directly to the way the numbers $k$ exchange between numerators and denominators, in other words, whether the exponent $e_{k}=(-1)^{t_{k-1}}$ is $+1$ or $-1$, is the following. Let $A_{k}$ be a sequence of strings of 0’s and 1’s with length $2^{k}$, with $A_{0}=0$. For $k\geq 0$, $A_{k+1}=A_{k}\overline{A}_{k}$, where $\overline{A}_{k}$ is obtained from $A_{k}$ by interchanging 0’s and 1’s. Then $\left( t_{k}\right) _{k\geq 0}$ is the infinite sequence generated by $A_{k}$ as $k\rightarrow \infty$. It has the following property: $t_{2m}=t_{m}$ and $t_{2m+1}=1-t_{m}$ for $m\geq 0$. Thus $t_{2m}+t_{2m+1}=1$ and since $t_{k}\in \left\{ 0,1\right\}$, one of $t_{2m+2}$, $t_{2m+1}$ is $0$ and the other is $1$. In terms of the exponents we have $e_{2m+1}=(-1)^{t_{2m}}=(-1)^{t_{m}}$ and $e_{2m+2}\ e_{2m+1}=(-1)^{t_{2m}+t_{2m+1}}=-1$. This means that one of the integers $2m+1$ and $2m+2$ is in the numerator and the other in the denominator, which is in accordance with the way how the tall fraction is constructed from fractions $\frac{1}{2},\frac{2}{3},\frac{4}{5},\ldots$. Similarly, we have in general (when $k$ runs from $1$ to $2^{n}$, $m$ varies from $0$ to $2^{n-1}-1$.)

\begin{aligned}f_{n} &=\prod_{k=1}^{2^{n}}k^{e_{k}}=\prod_{k=1}^{2^{n}}k^{(-1)^{t_{k-1}}}\\&=\prod_{m=0}^{2^{n-1}-1}\left( 2m+1\right)^{(-1)^{t_{2m}}}\left( 2m+2\right)^{(-1)^{t_{2m+1}}}=\prod_{m=0}^{2^{n-1}-1}\left( \frac{2m+1}{2m+2}\right)^{(-1)^{t_{m}}} \end{aligned}

and we want to evaluate the limit of the sequence $f_{n}$

\begin{aligned}\underset{n\rightarrow \infty }{\lim }f_{n}=\prod_{m=0}^{\infty }\left(\dfrac{2m+1}{2m+2}\right) ^{(-1)^{t_{m}}}.\qquad(\ast )\end{aligned}

In Proposition 5 of the mentioned paper, the authors show that

\begin{aligned}\underset{n\rightarrow \infty }{\lim }f_{n}=\prod_{m=0}^{\infty }\left(\dfrac{2m+1}{2m+2}\right) ^{(-1)^{t_{m}}}=\dfrac{1}{2}\prod_{m=0}^{\infty }\left(\dfrac{2m+1}{2m+2}\right) ^{(-1)^{t_{2m+1}}} \end{aligned}

and, since $(-1)^{t_{2m+1}}=-(-1)^{t_{2m}}=-(-1)^{t_{m}}$, they get

\begin{aligned} \underset{n\rightarrow \infty }{\lim }f_{n}=\dfrac{1}{2\ \underset{n\rightarrow\infty }{\lim }f_{n}},\end{aligned}

thus proving that $\underset{n\rightarrow \infty }{\lim }f_{n}^{2}=\dfrac{1}{2}$. The trick they use is to multiply both sides of $\left( \ast \right)$ by the auxiliary product

\begin{aligned}\prod_{m=1}^{\infty }\left( \frac{2m}{2m+1}\right) ^{(-1)^{t_{m}}}\qquad(\ast \ast ) \end{aligned}

pretty much as in Moron’s answer. Concerning the issue of the convergence of the infinitive products,  namely $\left( \ast \right)$ and $(\ast\ast )$ the authors state that they “are convergent by Abel’s theorem”, but I must confess I have no idea which theorem is this.*

* See this answer by Plop to this question of mine.

## Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Matemática, Math, Mathematics Stack Exchange com as etiquetas , , , . ligação permanente.

This site uses Akismet to reduce spam. Learn how your comment data is processed.