The Gauss-Legendre algorithm


Lemma 3.1.   Let a0=a and b0=b as in definition 3.1. Set

S=a2n=02n1(an2bn2).

Then ES(a,b)=SFS(a,b).

Proof. Consider the integral

(2)L(a,b)=a2FS(a,b)ES(a,b)

Explicitly, this expands to

L(a,b)=(a2b2)0π/2sin2θa2cos2θ+b2sin2θdθ.

  Substituting x2=a2cos2θ+b2sin2θ,

L(a,b)=baa2x2x2b2dx.

Now substituting y=(x+ab/x)/2 and considering the associated AM-GM sequence,

L(a,b)=12b1a1(a2b2)+4(a12y2)(a12y2)(y2b12)dy=12(a2b2)FS(a,b)+2L(a1,b1),

and thus

L(a,b)FS(a,b)=12(a02b02)+2L(a1,b1)FS(a,b).

  Since 2n(an2bn2)0, we get 2nL(an,bn)0, and hence repeatedly applying this identity we get

L(a,b)=n=02n1(an2bn2)FS(a,b),

or equivalently

L(a,b)=SFS(a,b)+a2FS(a,b).

Combining this equation with (2) gives us the result.