Big List of Erdős' elementary proofs

Question

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

Answer 1

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

Answer 2

Erdos answered the following question in the affirmative - Are there infinitely many odd numbers that are not expressible as the sum of a prime number and a power of $2$. The proof is explained in this paper : http://www.maa.org/sites/default/files/3004416309960.pdf.bannered.pdf

The essence of the proof is in showing that for every integral value of $k$, there is a $2^k$ which has a certain residue with certain moduli. By the Chinese remainder theorem, there are infinitely many odd numbers that satisfy those same congruences. Whenever they do, $a - 2^k$ is composite for all integer values of $k$.

Answer 3

One very simple, and yet one of my favorites is the Erdős-Anning theorem:

Let $ A \subseteq \mathbb C $ be an infinite set of points, such that

$$ \forall x, y\in A \quad |x-y| \in \mathbb N $$

then there exists some $ c,k \in \mathbb C $, such that all $ a \in A $ is of the form $ a = cx + k $ for some $ x \in \mathbb R $.

It was proved in 1945 in the American Mathematical Bulletin. http://www.ams.org/journals/bull/1945-51-08/S0002-9904-1945-08407-9/S0002-9904-1945-08407-9.pdf

---

A more colorful formulation is that an infinite sets of points on the Cartesian plain with mutual integer distances must lie on a straight line.

To prove it, we need an upper bound on the number of non collinear points possible in a set with integral distances. More specifically, if there is a set of non collinear points have integer distances, all at most $d$, then at most $4(d + 1)^2$ points with integer distances can be added to the set.

Answer 4

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.