This article presents the two most common startegies to prove the correctness of Greedy algorithms.

### Exchange argument for Greedy algorithms

The Greedy solution $\text{Gr}$ makes a sequence of choices, and an optimal solution $\text{OPT}_0$ makes another sequence of choices.

$$
\left\{
\begin{array}{ll}
\text{Gr} & = C_1, C_2, ... \\
\text{OPT}_0 & = C_1', C_2', ...
\end{array}
\right.
$$

We are going to build by induction a sequence of optimal solutions where the last one agrees with $\text{Gr}$ on all the choices (proving that $\text{Gr}$ is optimal)
$$ \text{OPT}_0 \to \text{OPT}_1 \to ... \to \text{OPT}_n = \text{Gr} $$
and $\text{OPT}_i$ agrees with $\text{Gr}$ up to the $i$th choice:

$$
\left\{
\begin{array}{ll}
\text{Gr} & = C_1, C_2, ..., C_i, C_{i+1},... \\
\text{OPT}_i & = C_1, C_2, ..., C_i, C_{i+1}',...
\end{array}
\right.
$$

**Base case.** $\text{OPT}_0$ agrees with $\text{Gr}$ up to choice zero (vacuously true).

**Inductive step.** Suppose we have an optimal solution $\text{OPT}_i$ agreeing with $\text{Gr}$ up to choice $i$. We need to transform $\text{OPT}_i \to \text{OPT}_{i+1}$ such that it agrees also on choice $i+1$ and it is still optimal.

Here, it is problem specific.

**Conclusion.** We have built an optimal solution $\text{OPT}_n$ agreeing with $\text{Gr}$ on all choices. Therefore, $\text{Gr} = \text{OPT}_n$ is optimal.

### Greedy stays ahead

The method is good when there is a value that we are maximizing (or minimizing). We show that the Greedy algorithm produces, at each step of the algorithm, a larger (or lower) value than any other algorithm.

Let $V_0 = 0, V_1, V_2, ...$ the values of the Greedy algorithm after each choice, and $V_0' = 0, V_1', V_2', ...$ the values of any other algorithm. Let's prove by induction on $i$, that after each choice $i$, $V_i \geq V_i'$.

**Base case.** $V_0 = 0 = V_0'$ so Greedy is ahead before any choice.

**Inductive step.** Assume $V_i \geq V_i'$ (Greedy was ahead before the choice $i+1$). We need to show that $V_{i+1} \geq V_{i+1}'$ (Greedy is ahead after the choice $i+1$)

Here, it is problem specific.

**Conclusion.** Because Greedy is ahead after each choice, Greedy is ahead at the end of the algorithm, and therefore produces an optimal solution.