Tall fraction puzzle, MSE

Publicado em 18 de Julho de 2011 por Américo Tavares

Question by Ross Millikan:

“ 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. “

My answer:

“ 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.

Advertisement

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.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Gravatar
Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com ( Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter ( Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook ( Terminar Sessão /  Alterar )

Cancelar

Connecting to %s

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