I have no pressing reason for asking the question I’m about to ask, but it is related to an old post about when two proofs are essentially the same, and it suddenly occurred to me while I was bathing my two-year-old son.
Consider the problem of showing that the product of any consecutive positive integers (or indeed any integers, not that that is a significant extension) is divisible by I think the proof that most experienced mathematicians would give is the slick one that divided by is and so is the number of ways of choosing objects from objects. Since the latter must be an integer, so must the former.
One might argue that this is not a complete proof because one must show that really is the number of ways of choosing objects from but that is not hard to do.
It is not hard to imagine a less experienced mathematician — somebody just starting out at university, say — failing to think of this argument. If so, then they might attack the problem with brute force. To show that divides any product of consecutive positive integers, it is (necessary and) sufficient to show that every prime goes at least as many times into as it does into And that is actually not all that hard to prove. Let me show it for 3, but the argument is completely general.
A first guess at how many times 3 goes into is the number of multiples of that are at most or However, this is wrong since it forgets the fact that some of those multiples of 3 are also multiples of 9.
Since for each multiple of 9 we “forgot” a factor of 3, we could add on the number of multiples of 9. But then we’re forgetting multiples of 27, and so on. So in fact the number of times that 3 goes into is the number of multiples of 3 that are in the set plus the number of multiples of 9 plus the number of multiples of 27 plus the number of multiples of 81, and so on.
How many times does go into ? Exactly the same argument works: it is the number of multiples of 3 that belong to the set plus the number of multiples of 9, etc. etc.
The final step of the argument is to observe that for any positive integer the number of multiples of that belong to the set is less than or equal to the number of multiples of that belong to the set Why? Well, suppose you want to choose to minimize the number of multiples of you get. The obvious thing to do is make one more than a multiple of so that it takes as long as possible to hit the first multiple, then as long as possible to hit the second, etc. Since 0 is a multiple of every we are done.
The question I’m now asking is whether these are two completely different arguments, or whether there is some sophisticated perspective from which it is possible to regard them as sort of the same. The fact that the second one makes heavy use of the fundamental theorem of arithmetic suggests that they really are different, but it could be that what is really happening is that the second argument is taking the first argument and somehow splitting it up into pieces in an unnecessary way.