Upper bound on Frobenius Coin Problem Given a set of coin denominations $d_1<d_2<\cdots<d_k$ such that $\gcd(d_1,d_2,\dots,d_k)=1$, identifies the largest change that can not be given using these denominations.
Based on what I see online, it seems that $d_k^2$ is a proper upper bound.
According to page 43 and page 44 of this document, if we group all the natural numbers by size of $d_k$, the number of change amounts that can be made in the next group is always more than the number in the previous group. Can anyone show me why this statement is true or why $d_k^2$ is a proper upper bound. Thanks!
 A: A nerdy way of saying this is to let $S_m$ be the set of values $v$ in the range $1,2,\dots,d_k$ for which change can be made for $md_k+v$. 
The key is that $S_m\subseteq S_{m+1}$, and:

Claim: $S_{m+1}$ depends only only $S_0$ and $S_{m}$. That is, there is a value $v\in S_{m+1}$ if and only if there is a value $u\in S_{m}$ and values $w_1,w_2\in S_0\cup\{0\}$ with $d_k<u+w_1+w_2\leq 2d_k$ so that $u+w_1+w_2=v+d_k$.

So if $S_{m+1}=S_{m}$ then $S_{m+2}=S_{m+1}$ and $S_{m+3}=S_{m+2}$, etc, and thus if $S_{m}=S_{m+1}$ and $S_m\neq \{1,2,\dots d_k\}$ then there is no Frobenius value.
Presumably, elsewhere in the slides, you have already proved that there is some Frobenius value for any set $d_1,\dots,d_k$ with $\gcd(d_1,\dots,d_k)=1$.
The proof of my claim is tedious, but fairly direct.
Proof of claim:
If $u\in S_m$ and $w_1,w_2\in S_0$ and $d_k<u+w_1+w_2\leq 2d_k$ then $u+w-d_k\in S_{m+1}$, since we have $0<u+w_1+w_2-d_k\leq d_k$ and we can make change for $w_1,w_2$ and $md_k+u$ so we can make change for $(m+1)d_k+v=(md_k+u)+w_1+w_2$.
On the other hand, if we can make change for $(m+1)d_k+v$, for $1\leq v\leq d_k$, then start subtracting coins from that change until we have a value remaining $\leq (m+1)d_k$. 
Since each such coin has value $\leq d_k$ we know the remaining coins value is of the form $md_k+u$ for $u\in S_m$. If the total value removed is $\leq d_k$ we are done - we pick $w_1$ to be that value, and $w_2=0$.
If the total removes is more than $d_k$, then the last coin removed necessarily "put us over the edge" to get us $\leq (m+1)d_k$, and thus we can choose $w_1$ be the value of that last coin, and $w_2$ be the value of the rest of the coins, both of which values are in $S_0$.

Initially I thought we needed just one $w\in S_0$, but there are tricky cases like $d_1=5,d_2=13$ where $12\in S_1$ because $25=5+5+5+5+5$, but we can't subtract coins of value $\leq 13$ to get the remaining coins less than $\leq 13$. In this case, we need $w_1=10,w_2=5,u=10$.
We've actually proven a stronger result, that we can find $w_1\in S_0$ and $w_2\in\{0,d_1,\dots,d_{k-1}\}$. (Excluding $w_2=d_k$ isn't hard.)
