# If $(x_n)_{n\in\mathbb N}$ is subadditive, show that $x_n\le\left\lfloor\frac nk\right\rfloor x_k+x_{n-k\left\lfloor\frac nk\right\rfloor}$

Let $$(x_n)_{n\in\mathbb N}\subseteq[-\infty,\infty)$$ with $$x_{m+n}\le x_m+x_n\;\;\;\text{for all }m,n\in\mathbb N.\tag1$$

How can we show that $$x_n\le\left\lfloor\frac nk\right\rfloor x_k+x_{n-k\left\lfloor\frac nk\right\rfloor}\;\;\;\text{for all }k,n\in\mathbb N\tag2$$ and how can we conclude that $$\limsup_{n\to\infty}\frac{x_n}n\le\frac{x_k}k\;\;\;\text{for all }k\in\mathbb N?\tag3$$

Clearly, if $$\operatorname{frac}(x):=x-\lfloor x\rfloor\in[0,1)\;\;\;\text{for }x\in\mathbb R$$ and $$k,n\in\mathbb N$$, we may write $$n=k\left(\left\lfloor\frac nk\right\rfloor+\operatorname{frac}\left(\frac nk\right)\right),\tag3$$ but since $$\operatorname{frac}\left(\frac nk\right)$$ does not necessarily belong to $$\mathbb N$$, I don't see how I could use the subadditivity $$(1)$$.

As you stated, you have

$$x_{m+n}\le x_m+x_n\;\;\;\text{for all }m,n\in\mathbb{N} \tag{1}\label{eq1A}$$

and you want to show

$$x_n \le \left\lfloor\frac nk\right\rfloor x_k+x_{n-k\left\lfloor\frac nk\right\rfloor}\;\;\;\text{for all }k,n\in\mathbb{N} \tag2\label{eq2A}$$

Note \eqref{eq1A} means for all $$k \in \mathbb{N}$$ you have

\begin{aligned} x_{k+k} & \le x_k + x_k \\ x_{2k} & \le 2x_k \end{aligned}\tag{3}\label{eq3A}

Also,

\begin{aligned} x_{2k+k} & \le x_{2k} + x_k \\ x_{3k} & \le 2x_k + x_k = 3x_k \end{aligned}\tag{4}\label{eq4A}

You can show quite easily, say by induction, which I'll leave to you, that for any integer $$j \ge 1$$ you have

$$x_{jk} \le jx_{k} \tag{5}\label{eq5A}$$

With \eqref{eq2A}, if $$k \gt n$$, then $$\lfloor \frac{n}{k} \rfloor = 0$$, with the RHS side becoming $$0(x_k) + x_{n-k(0)} = x_n$$, so it's quite clear \eqref{eq2A} is true. Otherwise, for $$k \le n$$, using \eqref{eq5A} since $$\lfloor \frac{n}{k} \rfloor \ge 1$$, from \eqref{eq1A} you have

\begin{aligned} x_{k\left\lfloor\frac{n}{k}\right\rfloor + \left(n - k\left\lfloor\frac{n}{k}\right\rfloor\right)} & \le x_{k\left\lfloor\frac{n}{k}\right\rfloor} + x_{n-k\left\lfloor\frac nk\right\rfloor} \\ x_{n} & \le \left\lfloor\frac{n}{k}\right\rfloor x_k+x_{n-k\left\lfloor\frac nk\right\rfloor} \end{aligned}\tag{6}\label{eq6A}

which shows that \eqref{eq2A} also holds for these cases.

For the other part of the question, i.e., concluding that

$$\limsup_{n\to\infty}\frac{x_n}x\le\frac{x_k}k\;\;\;\text{for all }k\in\mathbb{N }\tag{7}\label{eq7A}$$

note that when $$k \mid n$$, you have $$\left\lfloor\frac{n}{k}\right\rfloor = \frac{n}{k}$$, so \eqref{eq2A} becomes

\begin{aligned} x_n & \le \left(\frac{n}{k}\right)x_k + x_{n - k\left(\frac{n}{k}\right)} \\ & = \left(\frac{n}{k}\right)x_k + x_{0} \end{aligned}\tag{8}\label{eq8A}

Although $$\mathbb{N}$$ often doesn't include $$0$$, but if it's to be included for this question's purpose (although this means you also need to specify that $$k \gt 0$$ for equations like \eqref{eq2A}, \eqref{eq6A} and \eqref{eq8A} to make sense), note you have from \eqref{eq1A} that

$$x_{0+0} \le x_0 + x_0 \implies x_{0} \le 2x_0 \implies x_{0} \ge 0 \tag{9}\label{eq9A}$$

Alternatively, you can just assign that $$x_{0} \ge 0$$. Either way, this means \eqref{eq8A} becomes

$$x_n \le \left(\frac{n}{k}\right)x_k \implies \frac{x_n}{n} \le \frac{x_k}{k} \tag{10}\label{eq10A}$$

I'll leave the rest for you to finish yourself.

• How did you obtain $x_{\left\lfloor\frac{n}{k}\right\rfloor + \left(n - \left\lfloor\frac{n}{k}\right\rfloor\right)} \le x_{\left\lfloor\frac{n}{k}\right\rfloor} + x_{n-k\left\lfloor\frac nk\right\rfloor}$ from $(5)$? What I get is $x_{\left\lfloor\frac{n}{k}\right\rfloor + \left(n - \left\lfloor\frac{n}{k}\right\rfloor\right)} \le x_{\left\lfloor\frac{n}{k}\right\rfloor} + x_{n-\left\lfloor\frac nk\right\rfloor}$ from $(5)$ – 0xbadf00d Apr 25 '20 at 6:22
• You're right my ($6$) is not correct. I'm sorry about that mistake. I've now corrected it so it shows what I initially intended, i.e., $x_{k\left\lfloor\frac{n}{k}\right\rfloor + \left(n - k\left\lfloor\frac{n}{k}\right\rfloor\right)} \le x_{k\left\lfloor\frac{n}{k}\right\rfloor} + x_{n-k\left\lfloor\frac nk\right\rfloor}$, with this coming from ($1$). Next, with the $j$ in ($5$) being $\left\lfloor\frac{n}{k}\right\rfloor$, I then get the next line in my ($6$). I trust this is now correct. Please let me know if you see any other errors. – John Omielan Apr 25 '20 at 6:34
• (a) Thank you for the correction. $(2)$ should now be correct. I think it's easiest to note that $n=ak+r$ for some unique $a\in\{0,\ldots,n\}$ and $r\in\{0,\ldots,k-1\}$. Now, $\frac rk\in[0,1)$ and hence $\left\lfloor\frac nk\right\rfloor=a$. Thus, $x_n\le ax_k+a_r=\left\lfloor\frac nk\right\rfloor x_k+a_{n-k\left\lfloor\frac nk\right\rfloor}$. – 0xbadf00d Apr 25 '20 at 8:09
• (b) $\mathbb N$ does not contain $0$, but we can define $x_0:=0$. (c) Regarding $(3)$: How do you conclude from your consideration where you've assumed that $k\mid n$? I've found a proof which argues that $\left\lfloor\frac nk\right\rfloor\sim\frac nk$ as $n\to\infty$, but what does that mean (i.e. what does the $\sim$ mean? Some kind of "asymptotical equivalence"?)? – 0xbadf00d Apr 25 '20 at 8:09
• If $k \mid n$, this means $n$ is a multiple of $k$, so $\frac{n}{k}$ is an integer, meaning $\left\lfloor \frac{n}{k} \right\rfloor = \frac{n}{k}$, as I stated. As for $\sim$, I believe in the context you use that it that (i.e., "asymptotical equivalence") is what it basically means. In particular, you have $\lim_{n\to \infty}\frac{\left\lfloor \frac{n}{k} \right\rfloor}{\frac{n}{k}} = 1$. – John Omielan Apr 25 '20 at 8:13