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

### 5 Comments

1. #### 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

2. #### 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

3. #### 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

4. #### Andrew McIntyre:

Whoa, synchronicity!

5. #### LJS:

This seems to be more or less the argument credited to Thue at

http://www.gbbservices.com/math/primes.html