1
$\begingroup$

I'm trying to compute \begin{align} \lim_{n \to \infty} \frac{1}{n}\sum_{k = 1}^n \bigg( \bigg\lfloor \frac{2n}{k} \bigg\rfloor - 2 \bigg\lfloor \frac{n}{k} \bigg\rfloor\bigg) \end{align} Numericaly the limit does not appear to be 0 but around $0.386$. Using Hermite's Identity I reduced the sum to \begin{align} \sum_{k = 1}^n \bigg( \bigg\lfloor \frac{n}{k} + \frac{1}{2} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\bigg) \end{align} and noticed that the terms can either be 0 or 1. I know that $\lfloor x + \frac{1}{2} \rfloor = \lfloor x \rfloor$ when $\{ x\} < \frac{1}{2}$. I figured that I need to find a way to count the zero terms(or non zero terms and subtract them from n) using a function say $f(n)$, and then computing $\lim_{n \to \infty} \frac{f(n)}{n}$. This is where I get stuck since I can't easily find the fractional part of $\frac{n}{k}$. I've also tried to count numbers such that $(n \mod k) < \frac{k}{2}$ but to no avail. I also can't see any squeeze theorem solutions. Any help is appreciated. (This problem is homework, so I would prefer a hint as opposed to a full solution).

$\endgroup$
  • 1
    $\begingroup$ I wonder if $0.368$ could not be $0.386$ instead. Minor detail. $\endgroup$ – Claude Leibovici Jun 23 '17 at 14:40
2
$\begingroup$

This is the Riemann sum limit for $$\int_0^1 (\lfloor 2/x \rfloor - 2 \lfloor 1/x \rfloor) \, dx = \int_1^\infty \frac{\lfloor 2x \rfloor - 2 \lfloor x \rfloor}{x^2} \, dx =\log(4) -1 \approx 0.386$$

To compute, note that

$$\int_1^\infty \frac{\lfloor 2x \rfloor - 2 \lfloor x \rfloor}{x^2} \, dx = \sum_{k=1}^\infty \left(\int_k^{k+1/2} \frac{2k - 2 k}{x^2} \, dx + \int_{k+1/2}^{k+1} \frac{2k+1 - 2k}{x^2} \, dx\right)$$

$\endgroup$
1
$\begingroup$

By defining the fractional part as $\{x\}=x-\lfloor x\rfloor$ we have $$ \{ x \} = \frac{1}{2}-\sum_{m\geq 1}\frac{\sin(2\pi m x)}{m\pi} \tag{1} $$ and:

$$\left\lfloor\frac{2n}{k}\right\rfloor -2\left\lfloor\frac{n}{k}\right\rfloor = 2\left\{\frac{n}{k}\right\}-\left\{\frac{2n}{k}\right\}=\frac{1}{2}-2\sum_{m\geq 1}\frac{\sin(2\pi m \frac{n}{k})}{m\pi}+\sum_{m\geq 1}\frac{\sin(2\pi m \frac{2n}{k})}{m\pi}$$ or, in a more compact form: $$ \left\lfloor\frac{2n}{k}\right\rfloor -2\left\lfloor\frac{n}{k}\right\rfloor = \frac{1}{2}-2\sum_{\substack{m\geq 1\\ m\text{ odd}}}\frac{\sin\left(2\pi m\frac{n}{k}\right)}{m\pi}\tag{2} $$ and by Riemann sums the wanted limit equals $$ L=\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^{n}\left(\left\lfloor\frac{2n}{k}\right\rfloor -2\left\lfloor\frac{n}{k}\right\rfloor\right)=\frac{1}{2}-2\sum_{\substack{m\geq 1\\ m \text{ odd}}}\frac{1}{m\pi}\int_{0}^{1}\sin\left(\frac{2m\pi}{z}\right)\,dz \tag{3}$$ or: $$ L = \frac{1}{2}+4\sum_{j\geq 0}\text{Ci}((4j+2)\pi)=\frac{1}{2}-4\int_{0}^{+\infty}\sin(z)\sum_{j\geq 0}\frac{1}{(z+(4j+2)\pi)^2}\,dz \tag{4}$$ where $\text{Ci}$ stands for a cosine integral. By the Laplace transform we get: $$ L = \frac{1}{2}-2\int_{0}^{+\infty}\frac{s}{(1+s^2)\sinh(2\pi s)}\,ds \approx \color{red}{0.38629436111989}\tag{5}$$ where $L=\color{red}{2\log 2-1}$ follows from the residue theorem.

$\endgroup$
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\lim_{n \to \infty}\bracks{{1 \over n}\sum_{k = 1}^{n} \pars{\left\lfloor\,{2n \over k}\,\right\rfloor - 2\left\lfloor\,{n \over k}\,\right\rfloor}} \,\,\,\stackrel{\substack{Riemann\\[0.5mm] Sum\\ \mbox{}}}{=}\,\,\, \int_{0}^{1}\pars{\left\lfloor\,{2 \over x}\,\right\rfloor - 2\left\lfloor\,{1 \over x}\,\right\rfloor}\dd x \\[5mm] \stackrel{x\ \mapsto\ 1/x}{=}\,\,\, & \int_{1}^{\infty}{\left\lfloor\,2x\,\right\rfloor - 2\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x = \lim_{\Lambda \to \infty}\pars{% \int_{1}^{\Lambda}{\left\lfloor\,2x\,\right\rfloor \over x^{2}}\,\dd x - 2\int_{1}^{\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x} \\[5mm] = &\ 2\lim_{\Lambda \to \infty}\pars{% \int_{2}^{2\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x - \int_{1}^{\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x} \\[5mm] = &\ 2\lim_{\Lambda \to \infty}\bracks{% \int_{2}^{2\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x - \pars{\int_{1}^{2}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x + \int_{2}^{\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x}} \\[5mm] = &\ -1 + 2\lim_{\Lambda \to \infty} \int_{\Lambda}^{2\Lambda}{\left\lfloor\,x\,\right\rfloor \over x^{2}}\,\dd x = -1 + 2\lim_{\Lambda \to \infty}\pars{% \int_{\Lambda}^{2\Lambda}{\dd x \over x} - \int_{\Lambda}^{2\Lambda}{\braces{x} \over x^{2}}\,\dd x} \\[5mm] = &\ 2\ln\pars{2} - 1 - 2\lim_{\Lambda \to \infty} \int_{\Lambda}^{2\Lambda}{\braces{x} \over x^{2}}\,\dd x = \bbx{2\ln\pars{2} - 1} \approx 0.3863 \end{align}

Note that $\ds{0 < \int_{\Lambda}^{2\Lambda}{\braces{x} \over x^{2}}\,\dd x < \int_{\Lambda}^{2\Lambda}{\dd x \over x^{2}} = {1 \over 2\Lambda} \,\,\,\stackrel{\mrm{as}\ \Lambda\ \to\ \infty}{\to}\,\,\, \color{#f00}{\large 0}}$.

$\endgroup$

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.