Skip to main content
2 of 3
added 748 characters in body
David E Speyer
  • 156.4k
  • 14
  • 422
  • 763

Is the following any clearer? (Read the subscripts carefully!)

$$\begin{array}{ll} f_1(y_1) + f_2(y_2) + f_3(y_3) + \cdots + f_n(y_n) &\leq \\ f_1(y_2) + f_2(y_2) + f_3(y_3) + \cdots + f_n(y_n) & \leq \\ f_1(y_3) + f_2(y_3) + f_3(y_3) + \cdots + f_n(y_n) & \leq \\ \qquad \qquad \qquad \vdots & \leq \\ f_1(y_n) + f_2(y_n) + f_3(y_n) + \cdots + f_n(y_n) & \leq \\ f_1(x) + f_2(x) + f_3(x) + \cdots + f_n(x). &\\ \end{array}$$

I don't think this is different from the induction proof in any serious way, but sometimes "$\cdots$" is more intuitive than a formal induction.


Here is a remark that might be useful: There are only $n(n+1)$ relevant variables: $f_i(y_j)$ and $f_i(x)$. The hypotheses are linear inequalities between them, and so is the conclusion.

One way to state Farkas' Lemma (aka Linear Programming Duality) is that, if we have a collection of inequalities $\sum_i A_{ij} x_i \geq 0$ in variables $x_i$, and they imply that $\sum_i y_i x_i \geq 0$, then there must be some nonnegative $b_j$ such that $\sum y_i x_i = \sum_j b_j \left( \sum_i A_{ij} x_i \right)$. In words, if some collection of linear inequalities implies another linear inequality, then there must be a linear proof.

So there had to be a way to write the conclusion as a linear consequence of the hypotheses, and I just had to find it.

David E Speyer
  • 156.4k
  • 14
  • 422
  • 763