I just started greedy algorithms and I'm having some issues.
the proof is in slides 5-6. The algorithm is straightforward and the properties are clear, but I don't understand the induction in slide 6:
Theorem. Cashier's algorithm is optimal for U.S. coins: 1, 5, 10, 25, 100. Pf. [by induction on x]
- Consider optimal way to change ck ≤ x < ck+1 : greedy takes coin k.
- We claim that any optimal solution must also take coin k.
- if not, it needs enough coins of type c1, …, ck–1 to add up to x
- table below indicates no optimal solution can do this
- Problem reduces to coin-changing x – ck cents, which, by induction, is optimally solved by cashier's algorithm
I know induction as in base case, induction hypothesis, and the induction step, but it seems like it is missing here.
What is the induction hypothesis and induction step here? Why is this proof valid?