I came across a fun problem recently that gave me a good opportunity to exercise my approximation muscles.
Problem: Compute , if it exists.
The basic approach to such sums is that the first few terms contribute to the sum because they are large and the rest of the terms contribute to the sum because there are a lot of them, so it makes sense to approximate the two parts of the sum separately. This is an important idea, for example, in certain estimates in functional analysis.
Since it follows that the limit, if it exists, is at least . In fact, this is the precise value of the limit. We’ll show this by giving progressively sharper estimates of the quantity
In the discussion that follows I’m going to ignore a lot of error terms to simplify the computations.
Suppose we split the sum after terms, where is a parameter to be optimized later. Then the sum of the first terms is bounded above by , and the sum of the rest of the terms is bounded above by . It’s clear that in order for this latter term to even stay bounded, needs to be on the order of . However, the former term will go to zero as long as grows slower than . And as one term gets larger, the other gets smaller. So ideally, we want them to have the same growth rate for large , and this should occur when has growth rate somewhere between and .
Well, if we suppose that grows fast enough so that goes to zero, the latter term is asymptotic to , so setting gives as our optimum. (We don’t need to worry about rounding since disregarding finitely many terms of the sum doesn’t affect the limit.) This in turn gives
How sharp is this estimate? Well, we know that (at least approximately), so there’s certainly room for improvement.
Now suppose we split the sum twice, first after and then after terms. Then the sum of the first terms is bounded above by , the sum of the next terms is bounded above by , and the sum of the rest of the terms is bounded above by , again under the assumption that grows faster than . Now we should compare the three growth rates
It’s somewhat less obvious what to do here. Under the assumption that is a fixed constant and that grows, equating the latter two growth rates gives
hence . By choosing larger and larger (but fixed) values of , it follows that
for every . But this isn’t optimal, since the term is smaller than it could be. If we allow to depend on then we have to be a little careful, since the effect of adding a constant to is to modify the middle growth rate considerably. With that in mind, thinking of the middle growth rate as suggests that we try since we’ll get a constant in the numerator. This gives
hence , giving us a final growth rate of
for any choice of . This suggests that we can do better. At this point the calculations get a little tedious, so I’m just going to tell you that an even better choice is
and that, after the appropriate calculations, it gives
A tight bound?
Of course, if we suspect that is very close to , then we shouldn’t be using the term to do our estimates at all. In other words, we should really be estimating , i.e. starting from the term. This gives, essentially,
The fact that the first term is now much smaller opens up the possibility that can grow like a power of . Trying out gives , hence and
and it’s not hard to see that this is essentially the best we can do.
Given that adding additional parameters isn’t likely to help much because the behavior of the sum smooths out considerably after the first batch of terms, I’m inclined to think this bound is reasonably tight, but I’m curious if a more sophisticated method can do better. Any takers?