“ 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:
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 terminating at for some , where it is much closer to the limit than elsewhere.
1)Find the limit, not too hard by experiment
2)In the last expression, find a simple, nonrecursive, expression to say whether is in the numerator or denominator
3)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, (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 , where is the Prouhet-Thue-Morse sequence. This product is the starting point of their proof.
1. The first few terms of this sequence are
These numerical values suggest that converges relatively fast to , and thus to :
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 can be written as the product of integers raised to . For instance,
where 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 exchange between numerators and denominators, in other words, whether the exponent is or , is the following. Let be a sequence of strings of 0’s and 1’s with length , with . For , , where is obtained from by interchanging 0’s and 1’s. Then is the infinite sequence generated by as . It has the following property: and for . Thus and since , one of , is and the other is . In terms of the exponents we have and . This means that one of the integers and 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 . Similarly, we have in general (when runs from to , varies from to .)
and we want to evaluate the limit of the sequence
In Proposition 5 of the mentioned paper, the authors show that
and, since , they get
thus proving that . The trick they use is to multiply both sides of by the auxiliary product
pretty much as in Moron’s answer. Concerning the issue of the convergence of the infinitive products, namely and the authors state that they “are convergent by Abel’s theorem”, but I must confess I have no idea which theorem is this.* “