Let $n = km +r$ with $k \geq 1$, $r \in \{0,...,m-1\}$. We need to show that $a_{km+r} \leq ma_1 + \left(\frac{km+r}{m}-1\right)a_m$ or equivalently $ma_{km+r} \leq m^2a_1 + ((k-1)m+r)a_m$ We will prove the statement by induction with respect to $k$. 1. $k=1$ We have to prove that $ma_{m+r} \leq m^2a_1 + ra_m$. We obtain it by summing following inequalities (remember $m-r > 0$): $ra_{m+r} \leq r^2a_1+ra_m$ $(m-r)a_{m+r} \leq (m-r)(m+r)a_1 = (m^2-r^2)a_1$ 2. Assume that the statement is true for some $k$, ie. $ma_{km+r} \leq m^2a_1 + ((k-1)m+r)a_m$. By adding $ma_m$ to both sides we obtain: $ma_{km+r} + ma_m \leq m^2a_1 + (km+r)a_m$ but ${ma_{(k+1)m+r}} \leq m(a_{km+r} + a_m) = ma_{km+r} + ma_m$ hence the statement is true for $k+1$.