Natural proofs of theorems or exercises

Question

Some mathematicians wants to hide their reasoning and proof process so that they appear smart.

As most of the mathematics lovers I am not a genius and this is why I hate the magical proofs because they don't learn me anything.

Do you have striking theorems or exercises you encoutered many times in your life and you never understood up until you finally got the right natural proof ? If it's the case please feel free to share your knowledge. Even if it is an heuristic and not a proof

For exemple here is a topic for natural Cauchy - Schwarz proofs : A natural proof of the Cauchy-Schwarz inequality

I should start :

Theorem. [PNT] If $p_n$ denotes the $n$-th prime number, then $p_n \sim n \log n$.

Here is an heuristic based on the ideas of Euler.
The excellent idea of Euler is to aknowledge that we have a better knowledge of the sums than the numbers. We all know that with a simple integral test we have : $$\sum _{1 \leqslant k \leqslant n} \frac{1}{k} \sim \log n $$ The idea is then to find each integer $n$ with the primes. For the powers of a prime Euler simply wrote : $$ \frac{1}{1-\frac{1}{p}}= \sum_{ \alpha \geqslant 0} \frac{1}{p^{\alpha}} $$ To find each $\displaystyle \frac{1}{n}$ we just have to take the product : $$ \prod_{ p\in \mathbb{P} \atop p \leqslant N} \frac{1}{1-\frac{1}{p}}= \prod_{ p\in \mathbb{P} \atop p\leqslant N} \sum_{ \alpha \geqslant 0} \frac{1}{p^{\alpha}}$$ In the right hand side we find each $\frac{1}{n}$ pour tous les $n$ for $n$ that only involves primes such that $p \leqslant N$ so we basicly have every $1/n$ up to $n=N^2$. Let's say : $$\prod_{ p\in \mathbb{P} \atop p \leqslant N} \frac{1}{1-\frac{1}{p}} \approx \sum_{n \leqslant N^2} \frac{1}{n} \sim \log N^2 \sim \log N$$ Taking the logarithm : $$-\sum_{p \leqslant N} \log \left( 1-\frac{1}{p} \right) \sim \log \log N $$ Since : $$\log \left( 1- \frac{1}{p}\right) \sim - \frac{1}{p}$$ by summation we have : $$ \sum_{p \leqslant N} \frac{1}{p} \sim \ln \ln N $$

A discrete derivation (but not licite still) gives us : $$ \frac{1}{p_N}=\frac{1}{N \log N}$$ so that : $$ p_N \sim N \log N $$ it's the prime number theorem !

It's a quite simple way of understanding the theorem I found very clear. Of course this is not a proof,

Answer 1

Another thing wich is rarely told to undergraduates (I am still an undergradute) :

Exercise. Given $u_0 \in \mathbb{R}$ and $u_{n+1}=\sin u_n$, show that $u_n \to 0$ and find an equivalent of $u_n$.

First, showing that $u_n \to 0$ is standard and in any textbook.

Then here is the first proof someone gave to me : Set $$v_n = \frac{1}{u_n^2}$$ I found it so magical !

Here is the correct way of seeing this :

Since $u_n \to 0$ observe that $ \displaystyle u_{n+1} = u_n - \frac{u_n^3}{6} + o(u_n^3)$ and then : $$u_{n+1}-u_n \sim - \frac{u_n^3}{6}$$ this is the discrete equivalent of the ODE : $$y'(t) = \frac{-y(y)^3}{6}$$ which can be re-writed as : $$\left( \frac{1}{y^2} \right) ' = \frac{1}{3}$$ so that the discrete equivalent is : $$\frac{1}{u_{n+1}^2} - \frac{1}{u_n^2} = \frac{1}{3}$$ Well, this is not a proof but gives us the intuition to study $v_n$ and find out that $$v_{n+1}-v_n \to \frac{1}{3}$$ so that $\displaystyle v_n \sim \frac{n}{3}$ and : $$u_n \sim \sqrt{ \frac{3}{n} }$$

This is a general technique for those questions and I have more sophisticated examples if you want.

Answer 2

When it comes to epsilon-delta arguments this situation often takes place (to less-experienced readers); beginners often cannot tell why an author makes so-and-so choices.

For instance, suppose we are to prove that the map $f: x \mapsto 1/x$ is continuous everywhere except at $x := 0$; a typical proof would just give the reader a choice of $\delta$, and then show that $|f(x) - f(c)|$ can be made $< \varepsilon$ for $|x-c| < \delta$. A beginner of course wonders how the author knows in advance a suitable choice of $\delta$, which can hardly be seen within the proof. A more natural way may be preserving the lines of thought in a proof of continuity of $f$; for instance: We start by taking any $\varepsilon > 0$ and any $c \neq 0$ and observe that if $x \neq 0$, then $$ |f(x) - f(c)| =\frac{|x-c|}{|xc|}. $$ To get rid of $|xc|$, observe that if $|x-c| < \frac{|c|}{2}$, then by "triangle inequality" we have $| |x| - |c|| \leq |x-c| < |c|/2$, so $|c|/2 < |x| < 3|c|/2$, and hence $c^{2}/2 < |xc| < 3c^{2}/2$, whence $$ \frac{|x-c|}{|xc|} < \frac{2|x-c|}{c^{2}}; $$ but this is $< \varepsilon$ if in addition we have $|x-c| < \varepsilon c^{2}/2$; therefore, we have proved that for every $\varepsilon > 0$ and every $c \neq 0$, if $|x-c| < \min \{ |c|/2, \varepsilon c^{2}/2 \}$, then $|f(x) - f(c)| < \varepsilon$. Recall that a typical way is to assert in the first place that if $\delta := \min \{|c|/2, \varepsilon c^{2}/2 \}$ then $|f(x) - f(c)| < \varepsilon$ for $|x-c| < \delta$, which proceeds forwardly and makes a possibly backward analyzing process disappear.

A proof being natural or not is subjective, so I would say the above proof is more natural only in the sense of the fact that it shows at least the lines of thought; some people may very well also find it unnatural.