# 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{\frac{1}{2}}{\frac{3}{4}},\frac{\frac{\frac{1}{2}}{\frac{3}{4}}}{\frac{\frac{5}{6}}{\frac{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.
This can also be represented as $\frac{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.

-
I haven't solved 3) yet, but I notice that for $n \ge 1$, if you multiply $a_n \times a_{n+1}$ you can cancel each integer $k$ in $a_n$ with $2k$ in $a_{n+1}$ leaving just the odd integers. –  Douglas Zare Mar 27 '11 at 4:09
@Carl Brannen: That should be $a_2 \times a_3 = \frac{1 \cdot 7}{3\cdot 5}$. –  Douglas Zare Mar 27 '11 at 6:27
@Doug; Thanks for the correction. In odd form, it's easier to predict whether a number ends up in the numerator or denominator. I think your observation may work. It makes me think of the infinite series for sine: en.wikipedia.org/wiki/… –  Carl Brannen Mar 27 '11 at 6:46
@Ross: Do you allow me to transcribe your question as it is (with full link to it, and to you) together with my answer and post them in my blog? –  Américo Tavares Jul 17 '11 at 21:01
@Américo Tavares: Certainly. I hope people like it. Two of the equations in your answer are not rendering properly for me-you might check. –  Ross Millikan Jul 18 '11 at 3:12

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.

1. 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*}$$
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{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.

-
A non-rigorous demonstration of convergence is to consider breaking the product into terms of the form $\frac{n(n+3)}{(n+1)(n+2)}=1-\frac{2}{n^2+3n+2}$ Then taking the log gives a sum with terms that go as $\frac{2}{n^2}$, so is absolutely convergent. The auxiliary product is has the same reasoning, so you can add the logs in any order you want as long as you group by 4's. –  Ross Millikan Mar 29 '11 at 22:22
@Ross Millikan: Thanks! These groups of 4 terms appear in the way you indicate or in inverted position $\frac{(n+1)(n+2)}{n(n+3)}$. –  Américo Tavares Mar 29 '11 at 23:00
that is true. I just thought getting the terms down to order 1/n^2 made the multiplication and rearrangement convincing. –  Ross Millikan Mar 29 '11 at 23:12
The sequence of exponents $\left( e_{k}\right) _{k\geq 0}$ is A106400 oeis.org/A106400 –  Américo Tavares Mar 30 '11 at 13:27
I took the liberty of adding links to problem and solution in the Amer. Math. Monthly (needs a subscription, though). –  t.b. Jul 15 '11 at 11:47

Some thoughts up to now:

1. Seems like $\frac{1}{\sqrt{2}}$
2. n is numerator if number of 1s on binary representation of (n-1) is even. For example $n = 8, n - 1= 111_2$ is a denominator, $n = 30, n-1= 11101_2$ is a numerator. (Sequence A010060) $$a(n) = \left(\sum_{k=0}^{n-1}\binom{n-1}{k}\mod 2\right)\mod 3 - 1$$
-
These are right. –  Ross Millikan Mar 27 '11 at 21:20

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.

-