From: Alex Selby <a.p.selby@REMOVE.pobox.com>
Subject: Re: algorithm about pi
Date: Tue, 04 Sep 2001 13:52:08 +0100
Newsgroups: sci.math
Summary: Limit of recursive sequence using the arithmetic-geometric mean.

Boris LTSI wrote:

> Hello,
> there had a post on fr.sci.maths (france) about a problem that has not
> been solved. If someone has an idea, I would be very happy to know it
> here it is
> let Y(0)=3+2^(3/2)
> and
> Y(n+1)=(Y(n)+(Y(n)^2-1)^(1/2))^2
> then the limit of Y(n)^(1/2^n) is exp(Pi) and no proof has been
> proposed. There may exist a proof with modular forms and elliptic
> functions, but we were looking on the french forum for a simpler proof.
> (however, I'm not against a proof with elliptic K function ! and perhaps
> arithmetic-geometric mean too, I don't know why... I feel that it could
> be useful)
> Some easy observations :
> Y(n+1)-2*Y(n)*sqrt(Y(n+1))+1=0
> cosh(1/2*ln(Y(n+1)))=Y(n)
> Regards
> --
> Boris
> http://www.pi314.net

Hi Boris,

I think you have to use arithmetic-geometric mean / elliptic K
function. The question is how to transform your problem into AMGM
form.

Let AGM(a,b) denote the arithmetic-geometric mean of a and b
(Replace (a,b) by (AM(a,b),GM(a,b))=((a+b)/2,sqrt(ab)) until
it converges.)

Let A(a)=AGM(a,1).

Define T(n) by T(n)^(-2)+Y(n)^(-2)=1, T(n)>0

Then...

Limit of Y(n)^(1/2^n) is exp(Q*pi/2), where Q=A(T(0))/T(0)/(A(Y(0))/Y(0))

It is slightly easier to see that this comes to exp(pi) in the case in
question if you notice that Y(-1)=T(-1)=sqrt(2). So replacing Y(n) by
Y(n-1) means that Q=1 and the limit is exp(pi/2)^2 = exp(pi).


Proof of above formula:

If a(n),b(n) are defined by AMGM, i.e., a(n+1)=AM(a(n),b(n)),
b(n+1)=GM(a(n),b(n)), and c(n)=a(n)/b(n), then
c(n+1)=AM(c(n),1)/GM(c(n),1) and inductively b(n)=Prod(r<n,
c(r))^(1/2)*b(0). So,

if c(n+1)=AM(c(n),1)/GM(c(n),1), then
 A(c(0))=AGM(c(0),1)=Prod(r=0...infty, c(r))^(1/2),
 and
 A(c(0))/A(c(n))=Prod(r<n, c(r))^(1/2)
(Formula (*))


Some fiddling about with the definitions of Y(n+1) and T(n) gives us
the formulae:

Y(n)=AM(Y(n+1),1)/GM(Y(n+1),1)
T(n+1)=AM(T(n),1)/GM(T(n),1)

(so T(n) and Y(-n) are sequences of the form c(n)),

and

sqrt(Y(n+1))/Y(n)=2T(n+1)/sqrt(T(n)).

Taking the product of this with n replaced by 0,1,...,n-1 gives

Y(n).(Y(n)Y(n-1)...Y(1))^(-1/2).Y(0)^(-1)=2^n.T(n)(T(0)T(1)...T(n-1))^(1/2).T(0)^(-1)

Using formula (*) with c(r)=Y(n-r) and c(r)=T(r),

Y(n).(A(Y(n))/A(Y(0)))^(-1).Y(0)^(-1)=2^n.T(n).A(T(0))/A(T(n)).T(0)^(-1)

T(n) --> 1 as n --> infty, so

Y(n) ~ 2^n.A(T(0)).A(Y(n)).Y(0)/(A(Y(0))T(0))
     = 2^n.Q.A(Y(n))

where ~ means asymptotic to (ratio tends to 1).

Now we use the fact that A(x) ~ pi.x/(2.log(x)) as x --> infty

This can be proved using an integral representation for AGM(x,1) and
some easy estimates.

Given this, we have

Y(n) ~ 2^n.Q.pi.Y(n)/(2.log(Y(n))),

giving 2^(-n).log(Y(n)) ~ Q.pi/2, which is the answer above.


Alex