A year or two ago, a couple of us were bored and somehow got to thinking about the series
It’s pretty easy to compute the series for For , one simply has to reorder the sum:
In the original sum, one adds vertically and then horizontally. Adding horizontally and then vertically — and tacitly making use of Fubini’s Theorem — one obtains
In general, one can iterate this idea to determine the sum in terms of the previous sums. For ,
The first row sums to one. The next three rows each sum to . The next five rows sum to . So in general, one obtains
Performing this same idea for general , one ends up with a sequence of rows. The first row always sums to 1. Then a number of rows follows each of which sums to . Then some rows summing to , and so on. To determine the number of rows summing to , one sees that there are . Hence we can write that
Note that the numerator of the right side of the equality is a polynomial of degree , and so by breaking the sum apart into each constituent power of , we have an iterative method of computing the sum for general . In particular,
As a relevant aside, while teaching calculus I went through an example in class of how to use power series to compute sums; At the board I realized I had just computed a power series which could be used to compute the sum for any denominator. If
then one can easily see that
All these series have radius of convergence 1, so in particular makes sense when .
Anyway, the original series seems to grow extremely quickly in , much faster than . The approximate growth rate with respect to is pretty obvious by considering the integral,
Since must be smaller than 1, we changed to so that it’s more clear the integral actually converges.Making the change of variables , one gets to something close to the function:
For large enough , depending on , one can replace the lower-limit by 0 without making too great an error. This is because the maximum of the integrand gets larger and moves further and further to the right as gets bigger. In fact the approximation is very good as long as isn’t too small, in particular if isn’t bigger than . Anyway, the whole point of this is that the final integral is almost exactly equal to . For , the integral is 119.99 rather than 5!=120.
For , this formula is good to 2 decimal places.
We worked for a while to figure out if there was a way to get a closed-form formula (i.e. a formula for finding the th sum without having to know all the sums smaller than ), but didn’t get too far. If anyone happens to know it, feel obliged to provide a reference!