How can this step in an inductive proof by Paul Erdős be valid?

Question

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?

Answer 1

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

Answer 2

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