An elementary inequality for a recursive double sequence

Question

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.

Answer 1

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).$$