|
|
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.
|
|
|
answered
Mar 29 '11 at 21:26
|
|
