Series acceleration and zeta(2)

-

(This is Yan Sheng.)

Today's post started with this question:

IMC 2015 Q6: Prove that $\displaystyle\sum_{n=1}^\infty\frac1{\sqrt n(n+1)}<2$.

The interested reader can pause here to try it out, while I helpfully fill the next few sentences with flavour text to delay spoilers.

One of my favourite hobbies is to cosplay as Euler. No, not literally (though I'm sure some of you freaks who read this blog would love to see it), but by trying to manipulate infinite series in all sorts of fun ways. I've already written here before about hand computation and zeta(2), and this post will be more of the same mucking around.

Theodorus's constant

For today's problem, seeing that the terms are of order $n^{-3/2}$, the first instinct should be to compare with a telescoping series whose tail sums are of order $n^{-1/2}$. Indeed, it's completely routine to check that$$2\left(\frac1{\sqrt n}-\frac1{\sqrt{n+1}}\right)-\frac1{\sqrt n(n+1)}=\frac{(\sqrt{n+1}-\sqrt n)^2}{\sqrt n(n+1)},$$and then summing over $n$ instantly finishes.

Apparently the constant defined by this infinite sum has a name: it's sometimes called Theodorus's constant. I'm a sucker for constants with names, so the natural follow-up question is how closely we can approximate it, preferably by hand and without actually summing up a bajillion terms (especially since there are square roots in there). We could try to set for instance$$\frac1{\sqrt n(n+1)}\approx A\left(\frac1{\sqrt{n+c}}-\frac1{\sqrt{n+c+1}}\right),$$and find the constants $A,c$ such that the power series expansion on both sides agree to as many terms as possible. After some algebra (omitted; the interested reader can see this AoPS post), we find that$$\frac1{\sqrt n(n+1)}>2\left(\frac1{\sqrt{n+\frac16}}-\frac1{\sqrt{n+\frac76}}\right),$$where the error is a tiny $\sim\dfrac1{96}n^{-7/2}$. Hence$$T\coloneqq\sum_{n=1}^\infty\frac1{\sqrt n(n+1)}>\sum_{n=1}^{N-1}\frac1{\sqrt n(n+1)}+\frac2{\sqrt{N+\frac16}},$$with error $\sim\dfrac1{240}N^{-5/2}$. For instance, $N=1$ gives$$T>2\sqrt{\frac67}=1.85164\ldots,$$and $N=2$ gives$$T>\frac12+2\sqrt{\frac6{13}}=1.85873\ldots$$Of course, higher values of $N$ give even better bounds. (Compare with the actual value $T=1.86002\ldots$)

Series acceleration

The next thing I wanted to do was to improve the approximation even further, by adding higher-order terms, but things quickly started to get disgusting because of the square roots. To scratch that itch, I decided to shift focus to a series with nicer terms, turning back to the all-time classic$$\zeta(2)\coloneqq\sum_{n=1}^\infty\frac1{n^2}.$$We know that this has value $\dfrac{\pi^2}6=1.64493\ldots$, but the challenge here is to compute the value by estimating the sum directly.

Okay, what other series do we know how to compute the value of, ideally where the terms are also of order $n^{-2}$? Here's an obvious one:$$\sum_{n=1}^\infty\frac1{n(n+1)}=1,$$proven as we know by writing the summand as $\displaystyle\frac1n-\frac1{n+1}$ and telescoping.

Now we can do the simplest possible thing, namely to subtract one series from the other:$$\begin{align*} \zeta(2)&=1+\sum_{n=1}^\infty\left(\frac1{n^2}-\frac1{n(n+1)}\right)\\ &=1+\sum_{n=1}^\infty\frac1{n^2(n+1)}. \end{align*}$$Now we've ended up with terms which are asymptotically $n^{-3}$ instead of $n^{-2}$; what we've done here is to accelerate the convergence of the series. (This trick is called the Kummer transform.)

I know what you're thinking: why not do it again? Now we need to come up with a new series whose terms are of order $n^{-3}$. This is harder if you haven't seen it before, but a good choice here is$$\sum_{n=1}^\infty\frac1{n(n+1)(n+2)}=\frac14,$$which comes from writing the summand as $\displaystyle\frac12\left(\frac1{n(n+1)}-\frac1{(n+1)(n+2)}\right)$. Now we can subtract again to get$$\begin{align*} \zeta(2)&=1+\frac14+\sum_{n=1}^\infty\left(\frac1{n^2(n+1)}-\frac1{n(n+1)(n+2)}\right)\\ &=1+\frac14+2\sum_{n=1}^\infty\frac1{n^2(n+1)(n+2)}. \end{align*}$$ And again?$$\begin{align*} &\sum_{n=1}^\infty\frac1{n(n+1)(n+2)(n+3)}\\&=\frac13\sum_{n=1}^\infty\left(\frac1{n(n+1)(n+2)}-\frac1{(n+1)(n+2)(n+3)}\right)\\&=\frac1{3\cdot3!},\end{align*}$$so$$\begin{align*} \zeta(2)&=1+\frac14+\frac2{3\cdot3!}+2\sum_{n=1}^\infty\left(\frac1{n^2(n+1)(n+2)}-\frac1{n(n+1)(n+2)(n+3)}\right)\\ &=1+\frac14+\frac19+3!\sum_{n=1}^\infty\frac1{n^2(n+1)(n+2)(n+3)}. \end{align*}$$Now it's pretty clear how the pattern continues, and we get infinitely many identities:$$\begin{align*} \zeta(2)&=1+\sum_{n=1}^\infty\frac1{n^2(n+1)}\\ &=1+\frac1{2^2}+\sum_{n=1}^\infty\frac1{n^2\binom{n+2}2}\\ &=1+\frac1{2^2}+\frac1{3^2}+\sum_{n=1}^\infty\frac1{n^2\binom{n+3}3}\\ &=1+\frac1{2^2}+\frac1{3^2}+\frac1{4^2}+\sum_{n=1}^\infty\frac1{n^2\binom{n+4}4}\\ &=\cdots\\ &=\sum_{j=1}^k\frac1{j^2}+\sum_{n=1}^\infty\frac1{n^2\binom{n+k}k}. \end{align*}$$The end result here is that we can accelerate $k$ times to get a series with terms of order $n^{-(k+2)}$, at the cost of having $k$ terms drop out of the Kummer transformation. (It seems like an interesting coincidence that these $k$ terms are precisely the reciprocal squares; hold that thought!)

The above expansion was already known to James Stirling (of Stirling's approximation for the factorial, and Stirling numbers); in his Methodus Differentialis (1730), he takes $k=12$ to compute $\zeta(2)$ to 8 correct decimal places.

Diagonalisation

Recall that we actually want to calculate the sum; which of those infinitely many series should we use? We can access faster and faster converging series, but at the cost of more and more initial terms, so it looks like there's a trade-off to be made here.

Suppose we want to use 6 terms in total. Here's what we get with different values of $k$ (scroll right on mobile):$$\begin{array} {lll}k\hspace{1em}&\text{Sum}&\text{Value}\\\hline 0&1+\dfrac1{2^2}+\dfrac1{3^2}+\dfrac1{4^2}+\dfrac1{5^2}+\dfrac1{6^2}&1.49138\ldots\\ 1&1+\dfrac1{1^2\cdot2}+\dfrac1{2^2\cdot3}+\dfrac1{3^2\cdot4}+\dfrac1{4^2\cdot5}+\dfrac1{5^2\cdot6}&1.63027\ldots\\ 2&1+\dfrac1{2^2}+\dfrac1{1^2\binom32}+\dfrac1{2^2\binom42}+\dfrac1{3^2\binom52}+\dfrac1{4^2\binom62}&1.64027\ldots\\ 3&1+\dfrac1{2^2}+\dfrac1{3^2}+\dfrac1{1^2\binom43}+\dfrac1{2^2\binom53}+\dfrac1{3^2\binom63}&1.64166\ldots\\ 4&1+\dfrac1{2^2}+\dfrac1{3^2}+\dfrac1{4^2}+\dfrac1{1^2\binom54}+\dfrac1{2^2\binom64}&1.64027\ldots\\ 5&1+\dfrac1{2^2}+\dfrac1{3^2}+\dfrac1{4^2}+\dfrac1{5^2}+\dfrac1{1^2\binom65}&1.63027\ldots\\ 6&1+\dfrac1{2^2}+\dfrac1{3^2}+\dfrac1{4^2}+\dfrac1{5^2}+\dfrac1{6^2}&1.49138\ldots \end{array}$$We know that all of these sums are lower bounds for $\zeta(2)$, so the best approximation is just the largest value, which occurs at $k=3$. So a good rule of thumb seems to be setting $k$ to half the number of terms we're planning to use. (It's also a bit strange how the results are exactly symmetric under $k\leftrightarrow6-k$.)

Can we do this automatically while doing the series acceleration? Looks like we want $k$ terms to drop out of the $k$-times accelerated series, so we can do this by taking out one term of the series each time we accelerate:$$\begin{align*} \zeta(2)&=\sum_{n=1}^\infty\left(\frac1{n(n+1)}+\frac1{n^2(n+1)}\right)\\ &=\left(1+\frac1{1^2\cdot2}\right)+\sum_{n=2}^\infty\frac1{n^2(n+1)}\\ &=\left(1+\frac1{1^2\cdot2}\right)+\sum_{n=2}^\infty\left(\frac1{n(n+1)(n+2)}+\frac1{n^2\binom{n+2}2}\right)\\ &=\left(1+\frac1{1^2\cdot2}\right)+\left(\frac1{2^2\cdot3}+\frac1{2^2\binom42}\right)+\sum_{n=3}^\infty\frac1{n^2\binom{n+2}2}\\ &=\left(1+\frac1{1^2\cdot2}\right)+\left(\frac1{2^2\cdot3}+\frac1{2^2\binom42}\right)+\sum_{n=3}^\infty\left(\frac{2!}{n(n+1)(n+2)(n+3)}+\frac1{n^2\binom{n+3}3}\right)\\ &=\left(1+\frac1{1^2\cdot2}\right)+\left(\frac1{2^2\cdot3}+\frac1{2^2\binom42}\right)+\left(\frac{2!}{3^2\cdot4\cdot5}+\frac1{3^3\binom63}\right)+\sum_{n=4}^\infty\frac1{n^2\binom{n+3}3}\\ &=\cdots\\ &=\sum_{j=1}^k\left(\frac{(j-1)!}{j^2(j+1)(j+2)\cdots(2j-1)}+\frac1{j^2\binom{2j}j}\right)+\sum_{n=k+1}^\infty\frac1{n^2\binom{n+k}k}. \end{align*}$$It turns out that the terms in the first sum can be combined: multiply the first term by $\dfrac{2k}{2k}$ to see that it's exactly twice the second term, so we have proven that$$\zeta(2)=\sum_{j=1}^k\frac3{j^2\binom{2j}j}+\sum_{n=k+1}^\infty\frac1{n^2\binom{n+k}k}. $$Taking $k\to\infty$, we obtain the elegant series$$\boxed{\zeta(2)=\sum_{j=1}^\infty\frac3{j^2\binom{2j}j}.}$$This series converges fast! Note that just 3 terms of this series would give the same result as $k=3$ in the previous table. We know by construction that it's going to converge faster than the $k$-times accelerated series for any $k$. Here's what the partial sums of this series look like (compare with the true value $1.644934\ldots$):$$\begin{array}{ll} k\hspace{1em}&\text{Value}\\\hline 1&1.5\\ 2&1.625\\ 3&1.641666\ldots\\ 4&1.644345\ldots\\ 5&1.644821\ldots\\ 6&1.644911\ldots \end{array}$$By Stirling's approximation, the terms in this series are of order $j^{-3/2}4^{-j}$; in particular, this converges exponentially fast, which none of our $k$-times accelerated series could manage.

The magic array

I've used the term "diagonalisation" to describe the above process (accelerating $k$ times, then taking out the first $k$ terms), so then I wondered if there's a 2D array which corresponds to this process. In fact, all we have to do here is to keep track of what happens to each term as we accelerate:$$\begin{align*} \frac1{n^2}&=\frac1{n(n+1)}+\frac1{n^2(n+1)}\\ &=\frac1{n(n+1)}+\frac1{n(n+1)(n+2)}+\frac{2!}{n^2(n+1)(n+2)}\\ &=\frac1{n(n+1)}+\frac1{n(n+1)(n+2)}+\frac{2!}{n(n+1)(n+2)(n+3)}+\frac{3!}{n^2(n+1)(n+2)(n+3)}\\ &=\cdots \end{align*}$$In fact notice that these are special cases of the general formula$$\frac1x=\sum_{j=1}^k\frac{a_1a_2\cdots a_{j-1}}{(x+a_1)(x+a_2)\cdots(x+a_j)}+\frac{a_1a_2\cdots a_k}{x(x+a_1)(x+a_2)\cdots(x+a_k)},\qquad(*)$$with $x=n$ and $a_j=j$. Hence$$\begin{array}{rcccccccccc} \zeta(2)={}&\dfrac1{1\cdot2}&+&\dfrac1{1\cdot2\cdot3}&+&\dfrac{2!}{1\cdot2\cdot3\cdot4}&+&\dfrac{3!}{1\cdot2\cdots5}&+&\cdots&\small(n=1)\\[1em] {}+{}&\dfrac1{2\cdot3}&+&\dfrac1{2\cdot3\cdot4}&+&\dfrac{2!}{2\cdot3\cdot4\cdot5}&+&\dfrac{3!}{2\cdot3\cdots6}&+&\cdots&\small(n=2)\\[1em] {}+{}&\dfrac1{3\cdot4}&+&\dfrac1{3\cdot4\cdot5}&+&\dfrac{2!}{3\cdot4\cdot5\cdot6}&+&\dfrac{3!}{3\cdot4\cdots7}&+&\cdots&\small(n=3)\\[1em] {}+{}&\dfrac1{4\cdot5}&+&\dfrac1{4\cdot5\cdot6}&+&\dfrac{2!}{4\cdot5\cdot6\cdot7}&+&\dfrac{3!}{4\cdot5\cdots8}&+&\cdots&\small(n=4)\\[1em] {}+{}&\vdots&&\vdots&&\vdots&&\vdots&&\ddots \end{array}$$Each value of $n$ yields one row of this array, and each acceleration yields one column; hence each row and column telescopes by construction.

We've made the observation before that the row sums and column sums of this array are unexpectedly both equal to the reciprocal squares. Calculating a few entries explicitly shows us why: it's symmetric!$$\begin{matrix} \dfrac12&\dfrac16&\dfrac1{12}&\cdots\\[1em] \dfrac16&\dfrac1{12}&\dfrac1{60}&\cdots\\[1em] \dfrac1{12}&\dfrac1{60}&\dfrac1{180}&\cdots\\[1em] \vdots&\vdots&\vdots&\ddots \end{matrix}$$This is easy to show: the term in the $n$-th row and $k$-th column is $\dfrac{(n-1)!(k-1)!}{(n+k)!}$, which is clearly symmetric in $n$ and $k$.

Now we can almost read off the boxed identity from staring at this array: the $n$-th diagonal entry is $\dfrac1{n^2\binom{2n}n}$, and it's easy to verify that the entries below it telescope to the same value (and by symmetry, so do the entries to the right of it), so the whole array sums to $\displaystyle3\sum_{n\ge1}\frac1{n^2\binom{2n}n}$.

Exercises

Other series to accelerate/diagonalise

Try to diagonalise some other series (or the same series in different ways) yourself! Here are some ideas.

  1. Prove that$$\sum_{n=1}^\infty\frac1{2^n-1}=\sum_{k=1}^\infty\frac{2^k+1}{2^{k^2}(2^k-1)}.$$(Bonus points for doing this in your head!) The value of this series is known as the Erdős–Borwein constant. Note that the original sum already converges exponentially, but the diagonalised sum converges even faster.
  2. Using $(*)$ with $x=n^2$ and $a_j=j^2$, prove that$$\zeta(2)=\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k^2\binom{2k}k}\left(\frac52+\frac1{2k-1}\right),$$and$$\boxed{\zeta(3)\coloneqq\sum_{n=1}^\infty\frac1{n^3}=\frac52\sum_{k=1}^\infty\frac{(-1)^{k-1}}{k^3\binom{2k}k}.}$$
  3. Using $(*)$ with $x=n-\frac12$ and $a_j=j+\frac12$, prove that$$\begin{align*} \log2&=\frac14\sum_{n=1}^\infty\frac1{(n-\frac12)n}\\ &=\frac12+\frac12\sum_{k=1}^\infty\left(\frac1k+\frac1{2k+1}\right)\frac1{4^k}. \end{align*}$$Similarly, using $(*)$ with $x=n+\frac12$ and $a_j=j-\frac12$, prove that$$\begin{align*} \log2&=1-\frac14\sum_{n=1}^\infty\frac1{n(n+\frac12)}\\ &=1-\frac12\sum_{k=1}^\infty\left(\frac2{k(2k-1)}+\frac1{k(2k+1)}\right)\frac1{4^k}. \end{align*}$$Also derive the above identities using the power series for $\log(1\pm x)$. (Note that there are more efficient ways to compute $\log2$ with that power series, such as $\frac12\left(\log(1+\frac13)-\log(1-\frac13)\right)$ with convergence rate $\frac19$.)
  4. Using $(*)$ with $x=n^2-\frac1{16}$ and $a_j=-(j-\frac14)(j-\frac34)$, prove that$$\begin{align*} \pi&=4-\frac12\sum_{n=1}^\infty\frac1{n^2-\frac1{16}}\\ &=4-\frac12\sum_{k=0}^\infty\frac{(-1)^k}{4^{k-1}(4k+1)(4k+3)}\left(\frac1{4k+2}+\frac4{4k+5}\right). \end{align*}$$Also derive the above identity using the power series expansion for $\operatorname{Im}\log\left(1-\frac{1+i}2\right)$. (Note that there are more efficient ways to compute $\pi$ with such power series, such as $16\tan^{-1}\frac15-4\tan^{-1}\frac1{239}$.)
  5. Using $(*)$ with $x=n^2$ and $a_j=-\left(j-\frac12\right)^2$, prove that$$\zeta(2)=2-\sum_{k=1}^\infty(-1)^{k-1}\frac{\binom{2k}k}{\binom{4k}{2k}}\left(\frac1{k^2}+\frac2{(2k+1)(4k+1)}\right).$$

Euler and the Basel problem

Euler's first major achievement was the solution of the Basel problem (finding a closed form for $\zeta(2)$) in 1734. However, in 1731 he had already computed the value of $\zeta(2)$ to 6 decimal places (unaware of Stirling's 1730 calculation), using the following method.

  1. By expanding the integrand as a power series, show that$$\zeta(2)=\int_0^1\frac{-\log(1-x)}x\,dx.$$
  2. By using integration by parts, show that for any $0<c<1$, we have$$\zeta(2)=\log c\log(1-c)+\sum_{n=1}^\infty\frac{c^n}{n^2}+\sum_{n=1}^\infty\frac{(1-c)^n}{n^2}.$$(This is the reflection formula for the dilogarithm.) Hence deduce that$$\zeta(2)=\log^22+\sum_{n=1}^\infty\frac1{2^{n-1}n^2}.$$

It is plausible that this computation would have led him to notice (!) that the value of $\zeta(2)$ is close to $\dfrac{\pi^2}6$.

Another proof of the boxed identity

This exercise will explore the series $$S_k\coloneqq\sum_{n=1}^\infty\frac1{n^2(n+1)^2\cdots(n+k)^2}.$$For instance, $S_0=\zeta(2)$.

  1. (Optional) Show that$$\frac1{n(n+1)\cdots(n+k)}=\frac1{k!}\left(\frac1n-\frac{\binom k1}{n+1}+\frac{\binom k2}{n+2}-\cdots+(-1)^k\frac1{n+k}\right).$$Hence show that $S_k$ is of the form $S_k=a_k\zeta(2)-b_k$, where $a_k,b_k\in\mathbb Q$. In fact, show that$$a_k=\frac1{k!^2}\left(\binom k0^2+\binom k1^2+\binom k2^2+\cdots+\binom kk^2\right)=\frac1{k!^2}\binom{2k}k.$$This approach also gives us a formula for $b_k$, but it's pretty nasty; we'll have to go with a different method.
  2. By using the identity$$\frac1{n^2(n+1)^2\cdots(n+k)^2}=\frac1{k^2}\left(\frac1{n(n+1)\cdots(n+k-1)}-\frac1{(n+1)(n+2)\cdots(n+k)}\right)^2,$$prove the recurrence$$S_k=\frac{2(2k-1)}{k^3}S_{k-1}-\frac3{(k\cdot k!)^2}.$$
  3. Hence show that $a_k,b_k$ (as defined in part 1) satisfy the recurrences$$\left\{\begin{aligned}a_k&=\frac{2(2k-1)}{k^3}a_{k-1},\\b_k&=\frac{2(2k-1)}{k^3}b_{k-1}+\frac3{(k\cdot k!)^2}.\end{aligned}\right.$$This allows us to write $b_k$ as a sum. (Also, verify the recurrence for the explicit expression of $a_k$ derived in part 1.)
  4. Deduce that$$\zeta(2)=3\sum_{j=1}^k\frac1{j^2\binom{2j}j}+\frac{S_k}{a_k},$$and thus finish the proof of the boxed identity.

Further reading

After calculating $\zeta(2)$ to 6 decimal places in 1731, Euler would then discover the Euler–Maclaurin summation formula in 1732, applying it to compute $\zeta(2)$ and $\zeta(3)$ to 20 decimal places in 1735, then proving $\zeta(2)=\dfrac{\pi^2}6$ the same year. See this StackExchange question for an overview of the history of the Basel problem, and the following articles for details:

The boxed identities for $\zeta(2)$ and $\zeta(3)$ and the identity $(*)$ are key ingredients in Apéry's proof of the irrationality of those constants; see for instance van der Poorten (1979), A Proof that Euler Missed.

Most of the series we considered in this post are hypergeometric series, i.e., the ratio between consecutive terms is a rational function in $n$. It is now possible to prove many such identities automatically with the method of WZ pairs, due to Wilf and Zeilberger (yes, the very sane and reasonable ultrafinitist with lots of Opinions); see the book A=B.

Comments

Post a Comment

Popular posts from this blog

SMO Open 2024 ??% Speedrun

-
Image
 Hi! It's Glen again. So I was supposed to write a post for next weekend, but I woke up this morning to pictures of this year's SMO Open Round 2 in my messages, and I figured I might as well give them a go. And then I figured that I should just release my solutions to beat everyone else to the chase. Hence, this blog post is a week early.
Read more

SMO Senior 2025 ??% Speedrun

-
Image
 (Glen here.) The blog has been somewhat inactive because everyone has been busy, so sorry if we kept you waiting! I got sent this year's SMO Senior Round 2 paper this morning, so I thought I'd give it a shot. I don't have paper with me, so that's an extra challenge, I guess. Problem 1 Let $ABCD$ be a convex quadrilateral and $M$ be the intersection of its diagonals. Through $M$ draw a line meetin [sic] the side $AB$ at $P$ sand [sic] the side $CD$ at $Q$. Find all the quadrilaterals so that there exists the segment $PQ$ that divides the triangles $ABM$ and $CDM$ into $4$ similar triangles. ??? What on earth is this??? Here's a picture:  Ok, we probably need $\angle APM = \angle MPB = 90^\circ$? Yeah, if not, then each triangle has two distinct angles that add up to $180^\circ$, which is bad. This also tells us that $AB||DC$, as $PQ$ is perpendicular to both. If $\angle APM = 90^\circ$, then the only two possibilities for $APM$ and $BPM$ to be similar are if $MA=MB$...
Read more