Stays Ahead Structure

Here is the formal structure of a stays ahead argument:

Claim: The greedy solution G is optimal. Proof by induction: Let OPT be any optimal solution. I will show that after step $k$, G is at least as good as OPT.

Base case: After step $0$ (or $1$), G is at least as good as OPT. Inductive step: Assume after step $k$, G is at least as good as OPT. Show after step $k+1$, G is still at least as good. Conclusion: At the final step, G is at least as good as OPT. Since OPT is optimal, G is too.