Infinitely Many Primes by Combinatorics
Here’s a proof of the infinitude of primes that occurred to me when for some reason Delta upgraded me to First Class on a flight April 2. Can anyone provide a reference?
Suppose that the set P of primes and 1 has just n+1 elements. Now every number at most 2k can be obtained by choosing k elements of P with replacement, which can be done in (k+n choose n) ways. Therefore
2k ≤ (k+n choose n) ≤ (k+n)n ,
which fails for k large.
Welcome to my blog. I also have a blog at the
MB:
Clearly you prove this by assuming a finite number of primes, and showing this leads to a contradiction like is usual, but can you explain to a novice in combinatorics how the inequalities follow? Specifically, how does your argument imply 2^k ≤ (k+n choose n) ≤ (k+n)^n ?
A number ≤ 2^k has at most k prime factors and hence is a product of exactly k numbers from our set P. It is a standard combinatorial formula (see any Discrete Math text) that the number of ways to choose k numbers from a set with n elements (allowing repetition) is (k+n choose n) = (k+n)(k+n-1)… ≤ (k+n)^n. —FM
4 April 2010, 7:14 amAndrew McIntyre:
Hi,
You mentioned this proof to me at the HRUMC the other day, and I said that I had just heard it somewhere else recently.
What I was thinking of was this post on Alexandre Borovik’s blog – not the same as yours, but similar. He credits it to Dmitri Fon-Der-Flaass.
andrew
18 April 2010, 9:35 pmFrank Morgan:
Thanks Andrew, interesting, same proof, based on Russian post by Dmitri Fon-Der-Flaass of same date as my post. I posted a comment on Borovik’s blog.
Frank
19 April 2010, 8:19 amAndrew McIntyre:
Whoa, synchronicity!
19 April 2010, 8:45 amLJS:
This seems to be more or less the argument credited to Thue at
http://www.gbbservices.com/math/primes.html
23 May 2010, 10:23 pm