Editing Greedy algorithm (section)

===Correctness Proofs=== 
A common technique for proving the correctness of greedy algorithms uses an [[inductive reasoning|inductive]] exchange argument.<ref>{{cite book |last=Erickson |first=Jeff |title=Algorithms |url=https://jeffe.cs.illinois.edu/teaching/algorithms/ |year=2019 |publisher=University of Illinois at Urbana-Champaign |chapter=Greedy Algorithms}}</ref> The exchange argument demonstrates that any solution different from the greedy solution can be transformed into the greedy solution without degrading its quality. This proof pattern typically follows these steps:

This proof pattern typically follows these steps (by contradiction): 
# Assume there exists an optimal solution different from the greedy solution 
# Identify the first point where the optimal and greedy solutions differ 
# Prove that exchanging the optimal choice for the greedy choice at this point cannot worsen the solution 
# Conclude by induction that there must exist an optimal solution identical to the greedy solution 

In some cases, an additional step may be needed to prove that no optimal solution can strictly improve upon the greedy solution.