The last Problem of the Week elicited some diverse and creative responses; many thanks to all those who submitted a solution!
Three basic approaches emerged from the solutions we received, each shedding different light on the problem, so Vishal and I thought it appropriate to give a representative example of each. (This is consonant with established practice in other fora, notably the Problems and Solutions section of the American Mathematical Monthly, which we look to as our model.) Here they are:
1. (Method based on Gamma and Beta functions; composite solution due to Philipp Lampe [U. Bonn], Jöel Duet, and Rod Carvalho) For integers , it is well-known that the Beta function
admits an integral representation
(See for instance Andrews, Askey, and Roy, Special Functions, pp. 4-5.) From the first equation we have Now let ; then we have
Interchanging summation and integration, we get
There is a slight difficulty with uniform convergence of the series (which would justify such interchange), at least in the case . There are various ways of handling this; for example, we may establish the result directly as follows: by change of variables , we have
and the partial sum telescopes to
Since for , the last integral is bounded above by
which tends to zero as . Putting all this together, it follows that
as claimed.
2. (Method of repeated integration, due to Gantumur Tsogtgerel, UC San Diego): Put , and let . We have ; thus for , the series defining converges for , and the series defining converges for < . Observe that
for .
We have for We also have
which gives for . By continuity, we get . Further, for we have and
Therefore
where we have used the Cauchy formula for repeated integration. After a short integration by parts, this last expression evaluates to . This yields for .
3. (Method of telescoping series, due to Nilay Vaish)
First, note that
.
Therefore,
.
Remarks:
Method 1 was the most popular; it has the advantage that provided one is already familiar with the Beta function, the calculation is essentially a triviality [modulo the slight technical bump in the road noted above]. For those unfamiliar with this function, I can strongly recommend the beautiful text by Andrews, Askey, and Roy, mentioned above, where the Beta function occupies a central place.
Method 2 was essentially how I accidentally discovered the calculation of the series to begin with: by considering iterated antiderivatives of . This however was some years ago, and I am grateful to Gantumur for his elegant solution, which saved me the trouble of recalling the details! Incidentally, the Wikipedia article on the Cauchy formula (linked above) sketches a proof which implicitly invokes differentiation under the integral sign (a favorite technique of Feynman), but we can also think of it this way: the -dimensional volume of the simplex is , since there are possible linear orderings of coordinates of points in the -cube [] [], and each ordering gives a simplex congruent to all the others. Then the result follows by an application of the Fubini theorem.
Method 3 is in some sense the most elementary solution [e.g., it avoids integration], if one is fortunate enough to see the trick of writing the summands as differences, so that the series telescopes. From one point of view this trick may seem awfully slick, like a magician pulling a rabbit out of a hat. But, it can be made to look utterly natural in the context of discrete calculus (dealing with sequences instead of continuous functions , and with the difference operator instead of the derivative).
Discrete calculus may be built up in analogy with continuous calculus; here are some basic terms of the analogy:
- A basic identity of discrete calculus is the polynomial identity which restates the recursive identity that generates Pascal’s triangle: This is analogous to the identity of continuous calculus,
- The preceding observation suggests that the falling power is the discrete analogue of the ordinary power of continuous calculus. It satisfies the identity The discrete analogue of the identity is the identity
- The last identity may be used to motivate the definition of when is negative: from one quickly derives The identity holds for all integers
- The analogue of continuous integration is finite summation. Formally, introduce the following symbolism for discrete integration: if and is integral, The fundamental theorem of discrete calculus is that if This simply restates the method of telescoping sums.
Using discrete calculus, the solution could be expressed compactly as follows:
Letting , our answer is:
4 comments
Comments feed for this article
June 4, 2008 at 6:18 pm
Summing reciprocals of binomial coefficients « Reasonable Deviations
[…] Trimble wrote an awesome post presenting three different […]
June 4, 2008 at 9:06 pm
Kea
Cool! I missed the deadline, but I was having so much fun playing with zeta functions. Note that the 3rd solution relates to the fact that n=2 is the reciprocals of triangular numbers, n=3 the reciprocals of tetrahedral numbers etc.
June 5, 2008 at 6:15 pm
Todd Trimble
Hi Kea,
I popped over to your blog after I read this, and saw your observation on values of zeta. What do you make of that observation, combinatorially (or otherwise)?
[Kea observed the amusing fact that
assuming I didn’t make a mistake in transcription.]
I might have a think about higher values of n.
June 5, 2008 at 9:55 pm
Kea
I don’t think higher values of n have such an obvious relation to zeta. The triangular numbers may be expressed as certain collections of Young diagrams (the non yellow ones) associated to the combinatorics of the associahedra. That’s why I don’t think the underlying reason here is easy to understand.