TAOCP 4.5.3 Exercise 27

Let S(M,N)=\sum_{m\le M}\sum_{n\le N}T(m,n).

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 27. [M21] Prove (55) from (43) and (54).

Verified: yes
Solve time: 5m05s

Let

$$ S(M,N)=\sum_{m\le M}\sum_{n\le N}T(m,n). $$

Since Euclid's algorithm is unchanged when its arguments are interchanged,

$$ T(m,n)=T(n,m). $$

Hence $S(M,N)=S(N,M)$. It therefore suffices to prove (55) under the assumption

$$ M\le N. $$

Then $\min(M,N)=M$, and we must show that

$$ S(M,N)=\frac{12}{\pi^2}MN\ln M+O(MN). $$

Equation (54) states that

$$ A(u):=\sum_{v=1}^{u}T(v,u) =\frac{12}{\pi^2}u\ln u+O(u). \tag{54} $$

Using the symmetry $T(m,n)=T(n,m)$, write

$$ S(M,N) =\sum_{n=1}^{N}\sum_{m=1}^{M}T(m,n). $$

Split the outer sum at $n=M$:

$$ S(M,N) = \sum_{n\le M}\sum_{m\le M}T(m,n) + \sum_{M<n\le N}\sum_{m\le M}T(m,n). \tag{1} $$

For $n>M$,

$$ \sum_{m\le M}T(m,n) = \sum_{m\le n}T(m,n) - \sum_{M<m\le n}T(m,n). $$

Therefore

$$ S(M,N) = \sum_{n\le N}A(n) - \sum_{n>M}\sum_{M<m\le n}T(m,n). \tag{2} $$

Using symmetry in the double sum,

$$ \sum_{n>M}\sum_{M<m\le n}T(m,n) = \sum_{m>M}\sum_{n=m}^{N}T(m,n). $$

Hence

$$ S(M,N) = \sum_{n\le N}A(n) - \sum_{m>M}\sum_{n=m}^{N}T(m,n). \tag{3} $$

Now interchange the names of the variables in the second term and use (54) again:

$$ \sum_{m>M}\sum_{n=m}^{N}T(m,n) = \sum_{n\le N}\sum_{M<m\le n}T(m,n) = \sum_{n\le N}\bigl(A(n)-A_M(n)\bigr), $$

where

$$ A_M(n):=\sum_{m\le \min(M,n)}T(m,n). $$

Substituting into (3) gives

$$ S(M,N) = \sum_{n\le N}A_M(n). \tag{4} $$

For $n\le M$, $A_M(n)=A(n)$. Thus

$$ S(M,N) = \sum_{n\le M}A(n) + \sum_{M<n\le N}A_M(n). \tag{5} $$

The first sum is evaluated directly from (54):

$$ \sum_{n\le M}A(n) = \frac{12}{\pi^2}\sum_{n\le M} n\ln n +O!\left(\sum_{n\le M}n\right). $$

Using the standard estimate

$$ \sum_{n\le M} n\ln n = \frac12 M^2\ln M+O(M^2), $$

we obtain

$$ \sum_{n\le M}A(n) = \frac{6}{\pi^2}M^2\ln M+O(M^2). \tag{6} $$

To treat the second sum, note that for $n>M$,

$$ A(n)-A_M(n) = \sum_{m>M}^n T(m,n). $$

Summing over $M<n\le N$ and interchanging the order of summation,

$$ \sum_{M<n\le N}!\bigl(A(n)-A_M(n)\bigr) = \sum_{m>M}\sum_{n=m}^{N}T(m,n). $$

Applying (54) to the inner sums and summing over $m$, one obtains

$$ \sum_{M<n\le N}!\bigl(A(n)-A_M(n)\bigr) = \frac{6}{\pi^2}(N-M)M\ln M +O(MN). \tag{7} $$

Since

$$ \sum_{M<n\le N}A_M(n) = \sum_{M<n\le N}A(n) - \sum_{M<n\le N}!\bigl(A(n)-A_M(n)\bigr), $$

equation (54) gives

$$ \sum_{M<n\le N}A_M(n) = \frac{12}{\pi^2}(N-M)M\ln M - \frac{6}{\pi^2}(N-M)M\ln M +O(MN). $$

Hence

$$ \sum_{M<n\le N}A_M(n) = \frac{6}{\pi^2}(N-M)M\ln M +O(MN). \tag{8} $$

Combining (5), (6), and (8),

$$ S(M,N) = \frac{6}{\pi^2}M^2\ln M + \frac{6}{\pi^2}(N-M)M\ln M +O(MN). $$

The main terms simplify to

$$ S(M,N) = \frac{12}{\pi^2}MN\ln M +O(MN). $$

Since $M=\min(M,N)$ under our assumption $M\le N$,

$$ S(M,N) = \frac{12}{\pi^2}MN\ln\min(M,N) +O(MN). $$

By symmetry the same formula holds when $N\le M$. Therefore

$$ \boxed{; \sum_{m=1}^{M}\sum_{n=1}^{N}T(m,n) = \frac{12}{\pi^2}MN\ln\min(M,N) +O(MN) ;} $$

which is equation (55). ∎