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?

  • 1
    $\begingroup$ I have read many of Erdos's papers and I can ensure you that sometimes he is too complicated. $\endgroup$ – Konstantinos Gaitanas Sep 21 '18 at 8:25

You misquoted some of the equations, leaving out the rounding – it's $\left\{\frac12(2a_2-1)\right\}=a_2$ etc., not $\frac12(2a_2-1)=a_2$ etc. (which is clearly false).

As to your question how he can state that $n=2a_2-1$: It's not the most well-written proof or the most clear notation, but I understand this to mean that $2a_2-1$, with $a_2$ defined in terms of the $n$ for which we want to prove the result, is substituted for the lower $n$ in the induction hypothesis, which is valid, since $2a_2-1=2\left\{\frac n4\right\}-1\lt n$ for $n\ge10$.


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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.