Greedy optimality for one-plus-power-of-two coins ($c_j=2^j+1$)

For denominations $1$ and $c_j=2^j+1$ with $0\le j\le k$, greedy minimizes coin count. Among optimal representations choose a lexicographically maximal descending denomination-count vector. Two unit coins can be replaced by one two; two $c_j$ below the largest can be replaced by $c_{j+1}+1$ without increasing count but improving that vector. Thus all smaller denominations occur at most once. For the coins below $c_j$, write their value as $L=B+r$, where $r$ is their count and $B\le 2^j-1$ is the sum of their distinct power-of-two parts. If $L\ge c_j$, one $c_j$ and $L-c_j$ units use $L-2^j\le r-1$ coins, contradicting optimality. Therefore the residual below each denomination is smaller than it, forcing precisely the greedy quotients.