Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 4 more comments

3 Answers 3

up vote 19 down vote accepted

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.

share|improve this answer
1  
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
show 3 more comments

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.

share|improve this answer
add comment

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$$
share|improve this answer
    
These are right. –  Ross Millikan Mar 27 '11 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.