In his proof of the Sylvester-Schur Theorem, Paul Erdős does a step which seems to me to be invalid.
Since this is a classic proof, I know that I am wrong. So, I am looking for an explanation of why this step can be done in the proof.
I am fine with the base case and assumption.
Here's his definition of terms:
Let $\{x\}$ be the least integer greater or equal to $x$.
Let $a_i$ be shorthand for $\left\{\dfrac{n}{2^i}\right\}$ so that $a_1 =\left\{\dfrac{n}{2}\right\}, a_2 =\left\{\dfrac{n}{2^2}\right\}, a_k =\left\{\dfrac{n}{2^k}\right\}$ and $a_1 \ge a_2 \ge a_3 \ge \dots a_k$
$a_k \le 2a_{k+1}$ since $a_k < \dfrac{n}{2^k}+1 = \dfrac{2n}{2^{k+1}}+1 \le 2a_{k+1} + 1$
Let $m$ be the first exponent for which $\dfrac{n}{2^m} \le 1$, then $a_m = 1$
Here is the base case and assumption:
For $n \le 10$, it follows from simple arithmetic: $${{2a_1}\choose{a_1}}{{2a_2}\choose{a_2}}\dots{{2a_m}\choose{a_m}} < 4^n$$
We assume that it is true for $n \ge 10$
Here is the step that seems invalid to me:
- If we apply $n = 2a_2 - 1$, then we get: $${{2a_1}\choose{a_1}}{{2a_2}\choose{a_2}}\dots{{2a_m}\choose{a_m}} < {{2a_1}\choose{a_1}}4^{2a_2-1}$$ Since $\dfrac{1}{2}(2a_2-1)=a_2, \dfrac{1}{4}(2a_2-1)=a_3, \dots$
This seems to me to contradict the definition of $a_2$ in the first place.
$a_2 = \left\{\dfrac{n}{2^2}\right\} = \dfrac{n+c}{4}$ where $0 \le c < 4$
So, that, by definition, $n = 4a_2 - c$.
How can he possibly state that $n=2a_2 - 1$?
This appears to me to contradict his definition.
What am I misunderstanding?