# Greedy algorithms coin changing problem - induction

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.

My question:

What is the induction hypothesis and induction step here? Why is this proof valid?

Base case: $k=1$. Suppose that you want to change a value $x$ between $c_1=1$ (inclusive) and $c_2=5$ (not inclusive), i.e. $1\le x<5$. Then, the greedy will take a coin of $k=1$ and will set $x \leftarrow x-1$. That the greedy solves here optimally is more or less trivial.
Induction hypothesis: $k$. The greedy solves optimally for any value of $x$ such that $c_{k-1}\le x<c_k$.
Induction step: $k+1$. Show that the greedy solves optimally for any value of $x$ such that $c_k\le x<c_{k+1}$. Then, they use this table that you mention to show that this problem reduces to solving for $x\leftarrow x-c_k$ for which $0\le x-c_k<c_{k+1}-c_k$, which has been treated in the induction hypothesis.