## 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 2^{k} can be obtained by choosing *k* elements of *P* with replacement, which can be done in (*k+n* choose *n*) ways. Therefore

2^{k} ≤ (*k*+*n* choose *n*) ≤ (*k*+*n*)^{n} ,

which fails for *k* large.

## 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 ?

4 April 2010, 7:14 amA 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## Andrew 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 pm## Frank 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 am## Andrew McIntyre:

Whoa, synchronicity!

19 April 2010, 8:45 am## LJS:

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