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 $\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 $$2^{n-2} + 1 \leq g(n) \leq \frac{(2n-4)!}{(n-2)!^2} + 1$$
• Erdos-Rado theorem
• 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 $n$.

Wacław Sierpiński, in his Elementary Theory of Numbers, attributes to Erdős the following elementary proof of the inequality $$\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\in\mathbb{N}=\{1,2,3,\ldots\}.$ Consider the set $$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 $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $\lvert S(n)\rvert = n.$

Now if we have a pair $(k,l)$ with $k^{2}l\leq n,$ then we must have $k^{2}\leq n$ and $l\leq n$, since $k$ and $l$ are positive. Note that this gives $k\leq\sqrt{n}.$ 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 $l\leq n$. That is, $l$ can be expressed as a product of the primes $p_{1},p_{2},\ldots,p_{\pi(n)}.$ There are $2^{\pi(n)}$ such products.

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

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

Here is an exposition of the proof that made Erdos famous by David Galvin. An elementary proof of Bertrand's postulate, which states that there is a prime number in between every $n$ and $2n$. The essence of this proof is in noticing that the lower bound of $$\binom{2n}{n} \geq \frac{4^n}{2n + 1}$$ The binomial expression is the middle term (and the largest) of $(1+x)^{2n}$. The lower bound is the average of the sum of all binomial coefficients. This is obtained by putting $x=1$, and then dividing by the number of terms. This gives us the average. Obviously, the largest term should be bigger than the average. If the postulate does not hold, there is an upper bound that is smaller than this lower bound for large $n$. The postulate can easily be verified for the smaller values of $n$.

https://www3.nd.edu/~dgalvin1/pdf/bertrand.pdf