Show that if $n \geq 2$ is even, then: $$\frac {2n}{3} \leq \sum_{k=1}^{n} \frac{p(k)}{k} \leq \frac {2(n+1)}{3}$$ where $p(k)$ is the greatest odd integer that divides $k$.

I think I'm almost done but cannot complete it. Well, it's known that there are $\frac {n}{2}$ odd naturals $ < n$. And for these integers, we have $\frac {p(k)}{k}=1$

Hence, we are left to show that: $$\frac {n}{6}\leq \sum_{k={\text {even}}, k\leq n}\frac{p(k)}{k}\leq \frac {n}{6} + \frac {2}{3}$$

Define $v_c(k)=d$ such that $c^d \mid k$ and $c^{d+1}\nmid k$.

If $k=2^x y$, then $\frac {p(k)}{k}=2^{-x}$.

Hence, if we find of $v_2(k)=1, v_{2^2}(k)=1, v_{2^3}(k)=1, \cdots$ for $k=2,4,6, \cdots , n$, and multiply $2^{-r}$ to each $v_{2^r}$, we get the value of the equation. Then, we can substitute it to show that it $\in [\frac {n}{6}, \frac{n+4}{6}]$

And the equation becomes, upon simplifying: $$\frac {n}{6}\leq \sum_{x=1}^{e} \left\lfloor\frac{n-2^x}{2^{x+1}}\right\rfloor \leq \frac {n}{6}+\frac {2}{3}$$ where we assume $2^e \leq n < 2^{e+1}$ for some $e\in \mathbb{N}$.

But how to prove this? Maybe it's quite simple but I can't do it unfortuantely.

  • $\begingroup$ I think there are some in-between errors as well, as a result of which the final equation doesn't seem to hold always. I took a few examples to verify it! $\endgroup$ – Mathejunior Oct 31 '17 at 17:34

As you found, we have

$$\frac{p(k)}{k} = 2^{-v_2(k)}.$$

Thus we can compute the sum if we know how many $k \leqslant n$ have $v_2(k) = m$ for every $m$. That's the number of multiples of $2^m$ not exceeding $n$ that are not multiples of $2^{m+1}$. The number of multiples of $r$ not exceeding $x$ is $\bigl\lfloor \frac{x}{r}\bigr\rfloor$, hence there are $\bigl\lfloor \frac{n}{2^m}\bigr\rfloor - \bigl\lfloor \frac{n}{2^{m+1}}\bigr\rfloor$ multiples of $2^m$ that aren't multiples of $2^{m+1}$ not exceeding $n$, and

$$\sum_{k = 1}^n \frac{p(k)}{k} = \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl(\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor\biggr).$$

The last sum is actually finite, since the terms are $0$ when $n < 2^m$, but $\infty$ is quicker to write. We can regroup this last sum,

\begin{align} \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl(\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor\biggr) &= \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \sum_{m = 0}^{\infty} \frac{2}{2^{m+1}}\biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor \\ &= \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - 2 \sum_{k = 1}^{\infty} \frac{1}{2^k} \biggl\lfloor \frac{n}{2^k}\biggr\rfloor \tag{$k = m+1$} \\ &= n - \sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl\lfloor \frac{n}{2^k}\biggr\rfloor. \end{align}

Now $\lfloor x\rfloor \leqslant x$ yields, together with the fact that all but finitely many terms are $0$, so the inequality is strict for almost all terms,

$$\sum_{k = 1}^{\infty} \frac{1}{2^k} \biggl\lfloor \frac{n}{2^k}\biggr\rfloor < \sum_{k = 1}^{\infty} \frac{n}{4^k} = \frac{n}{3}$$

and hence we have the lower bound

$$\sum_{k = 1}^n \frac{p(k)}{k} > \frac{2n}{3}.$$

This also holds for odd $n$.

For the upper bound, the estimate $\lfloor x\rfloor > x-1$ is not enough, that would yield an upper bound of $\frac{2n}{3} + 1$ rather that the desired $\frac{2n+2}{3}$. But for integer $n$ we have $\bigl\lfloor \frac{n}{2^k}\bigr\rfloor \geqslant \frac{n}{2^k} - 1 + \frac{1}{2^k}$, and for even $n$, we have $\bigl\lfloor \frac{n}{2^k}\bigr\rfloor \geqslant \frac{n}{2^k} - 1 + \frac{2}{2^k}$, with a strict inequality for all large enough $k$, hence

\begin{align} \sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl\lfloor \frac{n}{2^k}\biggr\rfloor &> \sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl( \frac{n}{2^k} - 1 + \frac{a}{2^k}\biggr) \\ &= \frac{n}{3} - 1 + \frac{a}{3} \end{align}

where $a = 1$ if $n$ is odd and $a = 2$ if $n$ is even. Thus we obtain

$$\frac{2n}{3} < \sum_{k = 1}^n \frac{p(k)}{k} < \frac{2n + (3-a)}{3},$$

and the upper bound $\frac{2(n+1)}{3}$ also holds for all $n$, and for even $n$ we can reduce it to $\frac{2n+1}{3}$.


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.