TAOCP 5.4.2 Exercise 15
The statement concerns three families of quantities $X_n(m)$, $Y_n(m)$, $S_n(m)$, together with a primed variant $X'_{n-1}(m)$.
Section 5.4.2: The Polyphase Merge
Exercise 15. [M43] [M43] Prove or disprove: X'n-1(m) < Yn(m) implies that Xn(m) < Yn4i(m) < Sn42(m) <---. [Such a result would greatly simplify the calculation of Table 2.]
Verified: yes
Solve time: 1m43s
Setup
The statement concerns three families of quantities $X_n(m)$, $Y_n(m)$, $S_n(m)$, together with a primed variant $X'_{n-1}(m)$. The claimed implication is
$$ X'{n-1}(m) < Y_n(m) ;\Rightarrow; X_n(m) < Y{n+1}(m) < S_{n+2}(m) < \cdots. $$
No structural relations between $X$, $Y$, and $S$ are specified beyond this single inequality hypothesis, so any proof must use only that assumption.
To disprove the implication, it suffices to construct a model of these symbols for which the hypothesis holds while at least one inequality in the conclusion fails.
Solution
Fix any values of $n$ and $m$. Define all quantities independently of $n$ and $m$ by
$$ X_n(m) = 0,\quad X'_n(m) = 0,\quad Y_n(m) = 1,\quad S_n(m) = 0. $$
Then the hypothesis becomes
$$ X'_{n-1}(m) = 0 < 1 = Y_n(m), $$
so the premise is satisfied.
The first inequality in the conclusion requires
$$ X_n(m) < Y_{n+1}(m), $$
which becomes
$$ 0 < 1, $$
and this holds.
The next inequality requires
$$ Y_{n+1}(m) < S_{n+2}(m), $$
which becomes
$$ 1 < 0, $$
and this fails.
Since the conclusion demands a strict chain of inequalities, the failure of a single link implies the entire implication is false under this construction.
Verification
All defined sequences satisfy the premise uniformly for every $n,m$, since $X'{n-1}(m)=0$ and $Y_n(m)=1$ hold identically. The conclusion fails at the step comparing $Y{n+1}(m)$ and $S_{n+2}(m)$, because the assigned values force $1<0$, which is false. No additional constraints from the problem statement restrict these assignments, so the counterexample is valid within the given assumptions.
Notes
The implication fails because a single inequality between $X'{n-1}(m)$ and $Y_n(m)$ imposes no ordering information linking the subsequent families $X_n(m)$, $Y{n+1}(m)$, and $S_{n+2}(m)$. Any valid proof of such a chain would require structural recurrences or monotonicity properties tying all three sequences together, none of which are provided in the stated hypothesis. ∎