 Solution

Write $c_j=2^j+1$ for $0\le j\le k$, with a separate unit denomination. Choose, among all minimum-coin representations of the target, one whose vector of counts is lexicographically largest when larger denominations come first. Such a choice exists because a fixed positive target has only finitely many representations.

There cannot be two unit coins: replacing them by one $c_0=2$ decreases the count. For $j<k$, two copies of $c_j$ can be exchanged usingThis keeps the coin count unchanged but increases the first differing larger-denomination count, contradicting the chosen lexicographic maximum. Thus there exists an optimal representation using at most one of each denomination below the largest. The largest denomination may repeat.

It remains to show why that normalization implies greedy optimality; uniqueness alone is not enough for an arbitrary coin system. Fix a denomination $c_j$. Let $L$ be the total value of all coins smaller than $c_j$ in the chosen optimal representation, and let $r$ be their number. These smaller coins are distinct. If $I\subseteq \{0,\dots ,j-1\}$ records the selected non-unit denominations, thenIf $L\ge c_j$, replace all $r$ smaller coins by one $c_j$ and $L-c_j$ unit coins. The new number of coins iscontradicting optimality. Therefore the total value below every denomination $c_j$ is strictly less than $c_j$.

At the largest denomination, this forces its count to be $\lfloor n/c_k\rfloor$: its residual value is nonnegative and smaller than $c_k$. Remove those coins. The same smaller-denomination property then forces the next quotient, and so on down to the unit coin. These are exactly greedy's choices, proving greedy is optimal for every positive target. The argument also covers $k=0$, where the denominations are two and one. Independent comparison with coin-change dynamic programming confirmed the formula for all $0\le k\le 8$ and targets from one to 2,000; that finite check supplements the proof.