Tall fraction puzzle
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, \frac{1}{2},\frac{\displaystyle\frac{1}{2}}{\displaystyle\frac{3}{4}},\frac{\displaystyle\frac{\displaystyle\frac{1}{2}}{\displaystyle\frac{3}{4}}}{\displaystyle\frac{\displaystyle\frac{5}{6}}{\displaystyle\frac{7}{8}}},\cdots$$
Each fraction keeps its large bars while being put atop a similar structure.
This can also be represented as $$\frac{1\cdot 4 \cdot 6 \cdot 7 \cdot\cdots}{2 \cdot 3 \cdot 5 \cdot 8 \cdot\cdots}$$ terminating at $2^n$ for some $n$, where it is much closer to the limit than elsewhere.
The challenge:
Find the limit, not too hard by experiment
In the last expression, find a simple, nonrecursive, expression to say whether $n$ is in the numerator or denominator
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, in 1978, and a solution by E. Robbins was published in Americ. Math. Monthly 86, No. 5, p.394f, 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 $\prod_{m=0}^{\infty }\left( \frac{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.
- The first few terms of this sequence are $$\begin{equation*} \left( f_{n}\right) _{n\geq 0}=\left( 1,\frac{1}{2},\frac{2}{3},\frac{7}{10},% \frac{286}{405},\frac{144\,305}{204\,102},\frac{276\,620\,298\,878}{% 391\,202\,754\,597},\ldots \right) \end{equation*}$$ These numerical values suggest that $\left( f_{n}^{2}\right) _{n\geq 0}$ converges relatively fast to $\frac{1}{2}$, and thus $f_{n}$ to$\frac{\sqrt{2% }}{2}$: $$\begin{equation*} \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{equation*}$$
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.
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{eqnarray*} f_{3} &=&\frac{\ \frac{1}{2}/\frac{3}{4}\ }{\frac{5}{6}/\frac{7}{8}}=\frac{1}{2}% \left( \frac{3}{4}\right) ^{-1}\left( \frac{5}{6}\left( \frac{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}}}\text{,} \end{eqnarray*}$$ 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 [edit: when $k$ runs from $1$ to $2^{n}$, $m$ varies from $0$ to $2^{n-1}-1$.] $$\begin{eqnarray*} 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{eqnarray*}$$ and we want to evaluate the limit of the sequence $f_{n}$ $$\begin{equation*} \underset{n\rightarrow \infty }{\lim }f_{n}=\prod_{m=0}^{\infty }\left( \frac{2m+1}{2m+2}\right) ^{(-1)^{t_{m}}}.\qquad(\ast ) \end{equation*}$$ In Proposition 5 of the mentioned paper, the authors show that $$\begin{equation*} \underset{n\rightarrow \infty }{\lim }f_{n}=\prod_{m=0}^{\infty }\left( \frac{2m+1}{2m+2}\right) ^{(-1)^{t_{m}}}=\frac{1}{2}\prod_{m=0}^{\infty }\left( \frac{2m+1}{2m+2}\right) ^{(-1)^{t_{2m+1}}} \end{equation*}$$ and, since $(-1)^{t_{2m+1}}=-(-1)^{t_{2m}}=-(-1)^{t_{m}}$, they get $$\begin{equation*} \underset{n\rightarrow \infty }{\lim }f_{n}=\frac{1}{2\ \underset{n\rightarrow \infty }{\lim }f_{n}},\end{equation*}$$ thus proving that $\underset{n\rightarrow \infty }{\lim }f_{n}^{2}=\frac{1}{2}$. The trick they use is to multiply both sides of $\left( \ast \right) $ by the auxiliary product $$\begin{equation*} \prod_{m=1}^{\infty }\left( \frac{2m}{2m+1}\right) ^{(-1)^{t_{m}}}\qquad(\ast \ast ) \end{equation*}$$ 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.
I believe the following approach might work for 3)
We can write the product as
$$\prod_{n=0}^{\infty} \left(\frac{2n+1}{2n+2}\right)^{x_n}$$
where $\displaystyle x_n$ is defined as
$\displaystyle x_0 = 1$
$\displaystyle x_1 = -1$
$\displaystyle x_{2n} = x_n$
$\displaystyle x_{2n+1} = -x_n$
Now notice that if we multiply each individual term (except for $\displaystyle n=0$) with $\displaystyle \left(\frac{2n}{2n+1}\right)^{x_n}$ we get $\displaystyle \left(\frac{n}{n+1}\right)^{x_n}$
Now if $\displaystyle n = 2k$ is even, then we have $\displaystyle x_{2k} = x_k$ and thus we get $\displaystyle \left(\frac{2k}{2k+1}\right)^{x_k}$
If $\displaystyle n = 2k+1$ is odd, then we have $\displaystyle x_{2k+1} = -x_k$ and thus we get $\displaystyle \left(\frac{2k+1}{2k+2}\right)^{-x_k}$
Thus the term which we multiplied $\displaystyle \frac{2n}{2n+1}$ will get canceled out, and the original terms are inverted.
Thus the square of our product must be $\displaystyle \frac{1}{2}$ (as we only multiply for $\displaystyle n \gt 0$).
Of course, this needs to be justified, dealing with cancellations etc in infinite products, but I suppose it can be done.