1
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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{equation}\begin{aligned} x_{k+k} & \le x_k + x_k \\ x_{2k} & \le 2x_k \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

Also,

$$\begin{equation}\begin{aligned} x_{2k+k} & \le x_{2k} + x_k \\ x_{3k} & \le 2x_k + x_k = 3x_k \end{aligned}\end{equation}\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{equation}\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}\end{equation}\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{equation}\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}\end{equation}\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.

$\endgroup$
5
  • $\begingroup$ 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)$ $\endgroup$ – 0xbadf00d Apr 25 '20 at 6:22
  • $\begingroup$ 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. $\endgroup$ – John Omielan Apr 25 '20 at 6:34
  • $\begingroup$ (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}$. $\endgroup$ – 0xbadf00d Apr 25 '20 at 8:09
  • $\begingroup$ (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"?)? $\endgroup$ – 0xbadf00d Apr 25 '20 at 8:09
  • $\begingroup$ 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$. $\endgroup$ – John Omielan Apr 25 '20 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.