What it says in the title.
Just kidding, the title is very poorly explained, sorry about that. Here is a more descriptive question.
How can I prove the following.
Suppose we have some set of coins $C$, each with a value of the form $b^a$ where $a<k$, the base $b$ is constant and the exponent $a$ varies from coin to coin.
Suppose as well that the sum of all the coins in $C$ is greater than or equal to $b^k$. i.e.
$$\sum_{c \in C}\text{value}(c) \geq b^k$$
Then we must show that there exists $D \subseteq C$ such that all the coins in $D$ sum up exactly to $b^k$. i.e.
$$\sum_{d \in D}\text{value}(d) = b^k$$
I am trying to use this as a lemma in a longer proof, and it is the last link I need to complete the proof. I would appreciate any help I can get to point me in the right direction. Thank you.
Consider the collection, $\mathscr{C}$, of all subsets of $C$ which sum to $≥b^k$. We know that $\mathscr{C}$ is not empty (since it at least contains $C$). Let $C_0$ be a subset with minimal sum in $\mathscr C$. We claim that the sum of the coins in $C_0$ is exactly $b^k$, which will clearly conclude the proof. So, suppose otherwise. Suppose $$N=\sum_{c\in C_0}\text {value}(c)>b^k$$
As a special case, to illustrate the idea here, first note that $C_0$ does not contain a coin with value $1$, else we could remove it, contradicting the minimality of $C_0$.
We can easily generalize this argument. Let $b^{a_1}$ be the minimal value of a coin in $C_0$. Then $b^{a_1}\,|\,N$ so $b^{a_1}\,|\,(N-b^k)$. But then $N≥b^k+b^{a_1}$ so we can remove a coin of value $b^{a_1}$ and get a subset in $\mathscr{C}$ with smaller sum than $C_0$, contradicting the minimality of $C_0$, so we are done.