Kempner Sums

I remember reading, some time ago, an article questioning the worth of a mathematical proof in comparison to simply a convincing argument. I have absolutely no recollection what the author’s point was.

But, in the realm of proof and proving things, there are a number of ways of going about proving something to be true. You might, for example, derive a proposition from first principles – simpler statements you take to be true. You might show that if what you’re trying to prove isn’t true, it must follow that something ridiculous, and therefore wrong, must occur. You might reduce a problem to something previously solved or something else previously proved. To prove something exists, you might construct such a thing, or show how to find it – the constructive approach. In my opinion, the best kinds of proofs are constructive proofs, and very very clever proofs.

I prefer constructive proofs because, for the most part, they directly demonstrate properties of the desired object or proposition and it gives you a more intuitive feel for how or why something works. I saw a proof once of the Hoffman-Singleton Theorem, that was really quite slick. The details are irrelevant, but it basically proved that several types of graphs could exist, by turning the problem into a problem in matrix theory. But it didn’t construct a graph-theoretic reason as to why these graphs could exist. Even though it proved they could exist, the proof itself contributed nothing to actually finding the graphs or understanding their properties beyond that their potential existence. The proof was incredibly clever – one of my favorites, but you come out of it with little more understanding than what you went in with.

Of course, all this is irrelevant for this post – I don’t actually have a proof to offer, but the idea of a proof that explains the how and why of something is very important.

Consider the harmonic series, the sum of the reciprocals of the natural numbers.

As you take the limit of the sum, as n goes to infinity, the sum diverges, increasing at basically ln(n).

But here is an interesting exercise. Take the sum, and remove all terms that include a 1 in the denominator.

That sum actually converges as you take the limit. I’ve always found this very surprising, but it can be proved that the sum converges.

Consider this. Take all the terms with n-many digits in the denominator. Of these terms, the values in the denominator must all be greater than . This means that each of those terms must be strictly less than . The next question is, how many such terms are there? Each denominator is an n-digit number. For the highest place, we have 8 choices for that digit – it cannot be 1, since we exclude 1, and it cannot be 0, since we’re dealing with n-digit numbers. For all other places, we have 9 of the 10 possible digits to choose from. This gives, in total, such numbers. This means that the sum of all the terms with n digits in the denominator is strictly less than . If we break the total sum into groups of n-digit denominator terms, we can calculate the entire sum by summing over all the groups. In a short, we construct the bound,

But the bound on the right is easily calculable. It’s a standard geometric series.

Thus we get the bound, , and an increasing sequence bound from above must converge. Therefore this curious summation must converge, and it must converge to something less than 80!

I find this fascinating. I think it’s because the condition, dropping all numbers with the digit 1, seems almost ‘unmathematical’.

So, it’s an interesting proof of an interesting property – but it troubles me. Even though it proves conclusively that the summation converges, it doesn’t really explain ‘why’ it converges. Why does dropping those terms sufficiently reduce the summation to allow it to converge? What was it about those terms, the ones that contain the digit 1, that made H diverge that K lacks? Is it the size of the terms? The distribution? The proof sheds no immediate light on this.

And I don’t really have a proof that does. But I find the following very interesting. Consider the question, how many natural numbers contain the digit 1? Of course it’s nonsense phrased like that, there are infinitely many, but consider all numbers from 1 to n many digits. We can represent each number as a string of n-characters. 00003, representing 3 in the set of 5 digit numbers. How many such numbers at there? Clearly, , 10 choices for each of n places. But, of those numbers, how many do not contain the digit 1? Same calculation, except now with 9 choices for each place – .

This means that, considering all numbers less than , do not contain the digit 1. Thus, as n goes to infinity, the fraction of numbers below that do not contain 1 goes to zero. And in turn, the fraction that do contain the digit 1 goes to 100%. In effect, by throwing away all the denominators that contain the digit 1, you are leaving a vanishingly small fraction of the original number of terms. You’re throwing away, in the limit, effectively all of the terms. Given that, it begins to make sense to me why the summation K converges the way it does.

It isn’t a proof, certainly, but I think it does point suggestively and waggle its eyebrows.

Another interesting problem to consider is how best to calculate the sum. The proof I give bounds K by 80, but in fact it is much closer to 16. And given the roughly harmonic nature of the summation, it converges very slowly. So how best to calculate K to a high degree of accuracy? I don’t know … but someone does.