Big List of Erdős’ elementary proofs

Paul Erdős was one of the greatest mathematicians of all time and he was famous for his elegant proofs from The Book. I posted a question about one of his theorem and got a reference, and I have other questions I want to know the answer to too. But, instead of requesting a reference for each theorem he gave with an elementary proof, I’ve decided to make a thread for a big list of all his elementary proofs.

I’m excited. Let’s make an index of the pages of the Book shown to us!

Please feel free to contribute.

To get you guys started, I will make a wish list of his theorems who’s references I want to see. I encourage you to add to my wish list if you so desire.

Wish list :

  • The product of two or more consecutive positive integers is never a square or any other higher power.
  • A connected graph with a minimum degree d and at least 2d+1 vertices has a path of length at least 2d+1.
  • Let d(n) be the number of divisors of n. Then the series n=1d(n)/2n converges to an irrational number
  • Let g(n) be the minimal number of points in the general position in the plane needed to ensure a subset exists that forms a convex n-gon. Then 2n2+1g(n)(2n4)!(n2)!2+1
  • Erdos-Rado theorem
  • Erdős-Mordell inequality

Answer

I think this is worth posting here, mostly because I really enjoy the simplicity of this proof but also because I have no idea how well it is known. The result is not deep or important, so the main interest is in the simplicity of the argument. Erdős proved a lower bound on the number of primes before an integer n.

Wacław Sierpiński, in his Elementary Theory of Numbers, attributes to Erdős the following elementary proof of the inequality π(n)logn2log2for n=1,2,.

Please note that I have adapted the argument from the text of the book to make things, in my opinion, a bit clearer. Note also that the only tools used in the below proof are some basic combinatorial facts and some results about square-free numbers, which can, for example, be proved with the Fundamental Theorem of Arithmetic.

Let nN={1,2,3,}. Consider the set S(n)={(k,l)N2:l is square-free and k2ln}. It is a standard fact that every natural number has a unique representation in the form k2l, where k and l are natural numbers and l is square-free. This gives |S(n)|=n.

Now if we have a pair (k,l) with k2ln, then we must have k2n and ln, since k and l are positive. Note that this gives kn. Since l is square-free, l can be expressed as a product of distinct primes, each of which must be not-greater-than n since ln. That is, l can be expressed as a product of the primes p1,p2,,pπ(n). There are 2π(n) such products.

Therefore, if we know (k,l)S(n) then there are at most n possibilities for what k might be and at most 2π(n) possibilities for what l might be (independent of k, of course). It follows that |S(n)|2π(n)n, so n2π(n)n.

Taking logs and rearranging gives the result.

Attribution
Source : Link , Question Author : Community , Answer Author :
4 revs, 2 users 93%

Leave a Comment