Solving “coin exchange” for coins of power values by greedy algorithm

Question

When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?

For example, if $a = 3$, $n =3$, we get the following coin values: 1, 3, 9, 27. When total exchange is 16, answer is 4 coins, as returned by greedy algorithm, $16=9+3+3+1$.

Answer 1

For the coin values: 1, 3, 9, 27, suppose $16 = a_0 + 3a_1 + 9a_2 + 27a_3$ is the coin exchange with minimal number of coins. Note that $16\equiv a_0 \equiv 1(\operatorname{mod}3)$. If $a_0 \ge 3$, then we can subtract 3 from $a_0$ and add 1 to $a_1$ to obtain coin exchange with less number of coins. So, $a_0$ must be the remainder of 16 divided by 3. Hopefully, you can see where I am going.

---

All numbers or variables below are nonnegative integers. $(d_nd_{n-1}\cdots d_0)_a$ means the integer with those digits in base $a$, i.e., $(d_nd_{n-1}\cdots d_0)_a=\sum_{i=0}^{n}d_ia^i$ where $d_i\lt a $ for $i\le n$.

Here is the general theorem.

(Greedy algorithm works for power coins) Let $a\ge2$ and $n\ge0$. If $e_na^n+(e_{n-1}e_{n-2}\cdots e_0)_a=\sum_{i=0}^nc_ia^i$, then $ \sum_{i=0}^ne_i\le\sum_{i=0}^nc_i$.

Proof by mathematical induction on $n\ge0$.

The base case, when $n=0$ is trivial.

Suppose it is true for some $n\ge0$. Let us check the case of $n+1$. Suppose $m=e_{n+1}a^{n+1}+(e_ne_{n-1}\cdots e_0)_a=\sum_{i=0}^{n+1}c_ia^i$. Note that $e_0$ is the remainder of $m$ divided by $a$.

If $c_{0}\ge a$, we can subtract $a$ from $c_0$ and add $1$ to $c_1$ to reduce sum $\sum_{i=0}^{n+1}c_i$. Without loss of generality we can assume $c_{0}\lt a$, i.e., $c_0$ is also the remainder of $m$ divided by $a$.

Now let $m'=(m-e_0)/a=(m-c_0)/a$. Then $m'=e_{n+1}a^{n}+(e_{n}e_{n-1}\cdots e_1)_a=\sum_{i=0}^{n}c_{i+1}a^i$. By induction hypothesis, we know $\sum_{i=0}^ne_{i+1}\le\sum_{i=0}^nc_{i+1}$. Adding $e_0=c_0$ to both sides, we obtained the wanted inequality for the case of $n+1$. Q.E.D.

What is left to be explained is that $\sum_{i=0}^ne_i$ does come from the greedy algorithm. That easy task will be left for interested readers to verify.