An elementary inequality for a recursive double sequence Here is what looks like (but is not) an Olympiad problem. Is it really that tough, or am I overlooking a simple solution?
I have a system of sequences $\sigma_0(m),\sigma_1(m),\ldots\,$ defined for all integer $m\ge 0$ as follows. If $\min\{m,n\}=0$, then $\sigma_n(m)=0$. If
both $m$ and $n$ are positive, then find the (uniquely defined) integers
$K\ge 1$ and $j\in[0,n-1]$ such that $K^n\le m<(K+1)^n$ and indeed,
$K^{n-j}(K+1)^j\le m<K^{n-j-1}(K+1)^{j+1}$, and writing $m=K^{n-j}(K+1)^j+R$,
let
  $$ \sigma_n(m) := (Kn+n-j)K^{n-j-1}(K+1)^{j-1} + \sigma_{n-1}(R). $$
(The expression $(Kn+n-j)K^{n-j-1}(K+1)^{j-1}$ can be understood as the "formal
derivative" $\frac{d}{dK}K^{n-j}(K+1)^j$.) Thus, for instance,
$\sigma_1(m)=1$ for all $m\ge 1$, and
  $$ \sigma_2(m) = \begin{cases}
                     2K+1\ &\text{if}\ K^2<m\le K^2+K, \\
                     2K+2\ &\text{if}\ K^2+K<m\le (K+1)^2.
                   \end{cases} $$

Is it true that for all $k,n,m_1,\ldots,m_k\ge 1$, we have
    $$ \sigma_n(m_1+\dotsb+m_k)
       \le \sigma_{n-1}(m_1)+\dotsb+\sigma_{n-1}(m_k)
                                            + \max\{ m_1,\ldots,m_k \} ? $$

The cases where $n=2$ and $m_1=\dotsb=m_k=1$ follow without much effort, but already the general case where $k=1$ seems difficult:

Is it true that $\sigma_n(m)\le\sigma_{n-1}(m)+m$ for all integer $m,n\ge 1$?

Computations seem to confirm the inequality in question.
 A: So far I was not able to prove the inequality $\sigma_n(m)\leq\sigma_{n-1}(m)+m$ and have not even convinced myself that it is true. Still, I have deduced a number of properties that one may find helpful. I state them as lemmas below with only brief proof ideas, but can provide complete proof(s) upon request.
Everywhere below I assume $m,n\geq 1$ be integer and $K,R,j$ be defined as in the question.
Lemma 1. 
$$\sigma_{n}(m) = \frac{Kn+n-j}{K(K+1)}(m-R) + \sigma_{n-1}(R).$$
Proof. Trivial.
Lemma 2. 
$$R < \frac{m}{K+1} < m^{(n-1)/n} \leq \frac{m}{K}.$$
Lemma 3. For any fixed $n\geq 0$, $\sigma_n(m)$ is a non-decreasing function of $m$.
Proof idea. Use Lemmas 1,2 and induction on $n$.
Lemma 4. 
$$\frac{mn}{K+1} \leq \sigma_n(m) \leq \frac{mn}{K-1},$$
where the upper bound holds for $K>1$. For $K=1$ (i.e., $m<2^n$), we have
$$\sigma_n(m) \leq mn.$$
Proof idea. Use Lemmas 1,2,3 and induction on $n$.
Lemma 5.
$$\sigma_n(m) \geq \frac{(K+2)n-j-1}{(K+1)^2}m.$$
Furthermore, for $1<K\leq n$, we have
$$\sigma_n(m) \leq \frac{K}{K^2-1}mn - \frac{j+1}{(K+1)^2}m \leq \frac{K}{K^2-1}mn,$$
while for $K=1$ (i.e., $m<2^n$), we have
$$\sigma_n(m) \leq mn-\frac{j+2}{4}m \qquad (m>1).$$
