Why QI Implies Monotonicity

I'll prove: if cost satisfies QI, then $opt[i] \leq opt[i+1]$. This means $opt$ is monotonic (non-decreasing): as the state index grows, the optimal split never moves backward.

Assume for contradiction that $opt[i+1] = j < k = opt[i]$. Since $k$ is optimal for $i$: $dp[k] + cost(k,i) \leq dp[j] + cost(j,i)$. Since $j$ is optimal for $i+1$: $dp[j] + cost(j,i+1) \leq dp[k] + cost(k,i+1)$. Add these inequalities.

After canceling $dp[j]$ and $dp[k]$: $cost(k,i) + cost(j,i+1) \leq cost(j,i) + cost(k,i+1)$. But QI with $a=j < b=k < c=i < d=i+1$ says the opposite! Contradiction. So $opt[i] \leq opt[i+1]$.