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

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 $\sum_{n=1}^\infty d(n)/2^n$ 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
• Erdős-Mordell inequality

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 $$nn$$.

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,….\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$

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 $$n∈N={1,2,3,…}.n\in\mathbb{N}=\{1,2,3,\ldots\}.$$ Consider the set $$S(n)={(k,l)∈N2:l is square-free and k2l≤n}.S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq n\}.$$ It is a standard fact that every natural number has a unique representation in the form $$k2l,k^{2}l,$$ where $$kk$$ and $$ll$$ are natural numbers and $$ll$$ is square-free. This gives $$|S(n)|=n.\lvert S(n)\rvert = n.$$

Now if we have a pair $$(k,l)(k,l)$$ with $$k2l≤n,k^{2}l\leq n,$$ then we must have $$k2≤nk^{2}\leq n$$ and $$l≤nl\leq n$$, since $$kk$$ and $$ll$$ are positive. Note that this gives $$k≤√n.k\leq\sqrt{n}.$$ Since $$ll$$ is square-free, $$ll$$ can be expressed as a product of distinct primes, each of which must be not-greater-than $$nn$$ since $$l≤nl\leq n$$. That is, $$ll$$ can be expressed as a product of the primes $$p1,p2,…,pπ(n).p_{1},p_{2},\ldots,p_{\pi(n)}.$$ There are $$2π(n)2^{\pi(n)}$$ such products.

Therefore, if we know $$(k,l)∈S(n)(k,l)\in S(n)$$ then there are at most $$√n\sqrt{n}$$ possibilities for what $$kk$$ might be and at most $$2π(n)2^{\pi(n)}$$ possibilities for what $$ll$$ might be (independent of $$kk$$, of course). It follows that $$|S(n)|≤2π(n)√n,\lvert S(n)\rvert \leq 2^{\pi(n)}\sqrt{n},$$ so $$n≤2π(n)√n.n\leq2^{\pi(n)}\sqrt{n}.$$

Taking $$log\log$$s and rearranging gives the result.