this problem is from the IMO 2021 shortlist:
Let n be an integer, and let A be a subset of
$\{0,1,2,3,\dots,5^n\}$ consisting of $4n+2$ numbers. Prove that there exist $a,b,c\in A$ such that $a<b<c$ and $c+2a>3b$.
They provide two solutions, one of which is as follows:
(By contradiction) Suppose that there exist $4n+2$ non-negative integers $x_0 < x_1 < \dots < x_{4n+1}$ that violate the problem statement. Then in particular $x_{4n+1}+2x_i \leq 3x_{i+1}$ for all $i=0,\dots,4n-1$ which gives
$$
x_{4n+1}-x_i \geq \frac{3}{2}(x_{4n+1}-x_{i+1})
$$
By a trivial induction we then get
$$
x_{4n+1}-x_i \geq \left(\frac{3}{2}\right)^{4n-i}(x_{4n+1}-x_{4n})
$$
Which for $i=0$ yields the contradiction
$$
x_{4n+1}-x_0 \geq \left(\frac{3}{2}\right)^{4n}(x_{4n+1}-x_{4n})
= \left(\frac{81}{16}\right)^{n}(x_{4n+1}-x_{4n})
> 5^n \cdot 1
$$
I'm struggling to understand the logic behind the trivial induction and the step that follows (i.e. moving from $i=4n-1$ to $i=0$. Specifically, I don't understand why this step is allowed).
I understand that $i=0$ leads to a contradiction, and I understand that $i = 4n-1$ satisfies the (false) inequality, but I would really like to understand how/why it is allowed to create the "trivial induction statement" and move backwards to get to $i = 0$?
What kind of method/technique of proof is this? It seems to differ from other examples that I have come across. Can I just make up any trivial statement that satisfies an assumed inequality and move backwards until I find a case that leads to a contradiction? And what have I really demonstrated in such cases?
I hope I'm getting my point across, and apologize if I haven't been clear enough. I would love to get the intuition behind this proof and would be grateful for any help!
Best Answer
The crucial observation is that for all $i = 0, 1, \dots, 4n-1$, $$ x_{4n+1} - x_i \geq \frac{3}{2}(x_{4n+1}-x_{i+1}). $$ Notice how this inequality relates $x_i$ to $x_{i+1}$, so we can chain them together: $$ 0 \leadsto 1 \leadsto 2 \leadsto \cdots \leadsto (4n-2) \leadsto (4n-1) $$
Perhaps it's easier to see if we define the auxiliary quantity $y_i = x_{4n+1} - x_i$ for all $i$. Then, we have the inequality $$ y_i \geq \frac32 y_{i+1}. $$ Starting with $i=0$, this says that $$ y_0 \geq \frac32 y_1 $$ and with $i=1$, $$ y_1 \geq \frac32 y_2, $$ which yields $$ y_0 \geq \left(\frac32\right)^2 y_2. $$ Chaining these all together (by induction formally), $$ y_0 \geq \left(\frac32\right)^1 y_1 \geq \left(\frac32\right)^2 y_2 \geq \cdots \geq \left(\frac32\right)^{4n-1} y_{4n-1} \geq \left(\frac32\right)^{4n} y_{4n}, $$ which leads to the contradiction.
Does this make sense?