To prove the Quadrangle Inequality on \( f(i, j) \), the statement is written out and then expanded until a true statement is reached.

Recall that \( f(i, j) = A(psa[i] - psa[j])^2 + B(psa[i] - psa[j]) + C \). Also, for the sake of saving space, \( psa[i] \) will be denoted as \( p_i \).

\[ \begin{align} \require{cancel} \scriptsize f(i, j) + f(i + 1, j + 1) & \scriptsize \geq f(i + 1, j) + f(i, j + 1) \\ \scriptsize \left[ A(p_{i} - p_{j})^2 + B(p_{i} - p_{j}) + C \right ] + \left[ A(p_{i + 1} - p_{j + 1})^2 + B(p_{i + 1} - p_{j + 1}) + C \right ] & \scriptsize \geq \left[ A(p_{i + 1} - p_{j})^2 + B(p_{i + 1} - p_{j}) + C \right ] + \left[ A(p_{i} - p_{j + 1})^2 + B(p_{i} - p_{j + 1}) + C \right ] \\ \scriptsize \left[ Ap_{i}^2 - 2Ap_{i}p_{j} + Ap_{j}^2 + Bp_{i} - Bp_{j} + C \right ] + \left[ Ap_{i + 1}^2 - 2Ap_{i + 1}p_{j + 1} + Ap_{j + 1}^2 + Bp_{i + 1} - Bp_{j + 1} + C \right ] & \scriptsize \geq \left[ Ap_{i + 1}^2 - 2Ap_{i + 1}p_{j} + Ap_{j}^2 + Bp_{i + 1} - Bp_{j} + C \right ] + \left[ Ap_{i}^2 - 2Ap_{i}p_{j + 1} + Ap_{j + 1}^2 + Bp_{i} - Bp_{j + 1} + C \right ] \\ \scriptsize \left[ \cancel{Ap_{i}^2} - 2Ap_{i}p_{j} + \cancel{Ap_{j}^2} + \cancel{Bp_{i}} - \cancel{Bp_{j}} + \cancel{C} \right ] + \left[ \cancel{Ap_{i + 1}^2} - 2Ap_{i + 1}p_{j + 1} + \cancel{Ap_{j + 1}^2} + \cancel{Bp_{i + 1}} - \cancel{Bp_{j + 1}} + \cancel{C} \right ] & \scriptsize \geq \left[ \cancel{Ap_{i + 1}^2} - 2Ap_{i + 1}p_{j} + \cancel{Ap_{j}^2} + \cancel{Bp_{i + 1}} - \cancel{Bp_{j}} + \cancel{C} \right ] + \left[ \cancel{Ap_{i}^2} - 2Ap_{i}p_{j + 1} + \cancel{Ap_{j + 1}^2} + \cancel{Bp_{i}} - \cancel{Bp_{j + 1}} + \cancel{C} \right ] \\ \scriptsize - 2Ap_{i}p_{j} - 2Ap_{i + 1}p_{j + 1} & \scriptsize \geq - 2Ap_{i + 1}p_{j} - 2Ap_{i}p_{j + 1} \\ \scriptsize - 2Ap_{i}p_{j} - 2Ap_{i + 1}p_{j + 1} + 2Ap_{i + 1}p_{j} + 2Ap_{i}p_{j + 1} & \scriptsize \geq 0 \\ \scriptsize 2A(- p_{i}p_{j} - p_{i + 1}p_{j + 1} + p_{i + 1}p_{j} + p_{i}p_{j + 1}) & \scriptsize \geq 0 \\ \scriptsize -2A(p_{i + 1} - p_{i})(p_{j + 1} - p_{j}) & \scriptsize \geq 0 \end{align} \]

Recall that \( p_{} \) or \( psa[] \) is a prefix sum array on positive elements, so for all \( i \), \( p_{i + 1} > p_{i} \), which makes both \( p_{i + 1} - p_{i} \) and \( p_{j + 1} - p_{j} \) positive.

Additionally, it is given in the problem statement that \( A \lt 0 \), so \( -A \) is positive. Therefore, the left-hand side product must be positive. This means that starting from the statement of the inequality, a true statement is reached, and the Quadrangle Inequality is indeed satisfied. \( \square \)