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?
Best Answer
The second (equation (4) in the article) is applied with a different $n$ (and thus different $a_k$'s).
Put more accurate, $a_k(n) = \lceil n/2^k\rceil$ should be written as a function of $n$; the same pertains to $m(n) = \min\{k : a_k(n) = 1\}$. Then the equation (4) (being proven inductively) states that $$\prod_{k = 1}^{m(n)}\binom{2a_k(n)}{a_k(n)} < 4^n;$$ if we call it $P(n)$, then (in the article) $P(n)$ is derived from $P(2a_2(n) - 1)$ (for $n \geqslant 10$).