0
$\begingroup$

Helo,

I am still interested in the asymptotic behavior of certain sums of type $\sum_{k=1}^{n}\left\{ \frac{h(n)}{h(k)}\right\}$ and here I conjecture that we have

$$\sum_{k=1}^{n}\left\{ \frac{2^{n}+1}{2^{k}+1}\right\}=\log(2)n+O \left(n^{1/2}\right)$$

where $\{x\}$ is the fractional part of $x$. But I had little trouble showing it. I manage to get

$$\sum_{n/2<k\leq n}\left\{ \frac{2^{n}+1}{2^{k}+1}\right\} =n/2+O\left (1\right)$$

and relationships

$\left\lfloor \frac{n+1}{2}\right\rfloor \leq k\leq n-1\Longrightarrow \left\{\frac{2^{n}+1}{2^{k} +1}\right\}=\frac{2^{k}+2-2^{n-k}}{2^{k}+1}$

$\left\lfloor \frac{n+3}{3}\right\rfloor \leq k\leq\left\lfloor \frac{n}{2}\right\rfloor \Longrightarrow \left\{\frac{2^{n}+1}{2^{k} +1}\right\}=\frac{2^{n-k}+1}{2^{k}+1}$

but that is not enough for me to conclude. Thanks for your help.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ For $m$ even the sum for $n/(m+1)<k\le n/m$ is a $O(1)$, and for $m$ odd it is $n(1/m-1/(m+1))+O(1)$, so indeed the sum is $n\log(2)+O(1)$ (at least if the $O(1)$ form a convergent series). $\endgroup$
    – Henri Cohen
    Commented Apr 20 at 20:17
  • $\begingroup$ Thanks this confirms the assertion for the main term. But I think we need to be finer to have the error term in $O(n^{1/2})$. My real guess is that it is in $O(n^{1/4+\epsilon})$ as for the Dirichlet divisor problem. $\endgroup$
    –  Babar
    Commented Apr 20 at 22:28
  • $\begingroup$ Henri Cohen's argument yields an error term of $O(n^{1/2})$. Namely, by summing up the contributions of the intervals $(n/(m+1),n/m]$ for $m\in\{1,\dotsc,M\}$, you can see that the sum is $n\log 2+O(M+N/M)$. Now choose $M=\lfloor\sqrt{n}\rfloor$ to conclude that the sum is $n\log 2+O(\sqrt{n})$. This is much the same as (in fact simpler than) my response for mathoverflow.net/q/467934, which is not surprising as the sequence $(2^n+1)$ is very similar to the Fibonacci sequence $\endgroup$
    – GH from MO
    Commented Apr 20 at 23:22
  • $\begingroup$ @GH from MO Thanks! I was applying your arguments on Fibonacci but I had not seen the idea of intervals that Henri Cohen pointed out. Unless I am mistaken, I also manage to show that: $\sum_{k=1}^{n}\left\{ \frac{\lambda^{n}+1}{\lambda^{k}+1}\right\} =\log(2)n+O \left(n^{1/2}\right)$ where $\lambda\geq2$ is an integer. $\endgroup$
    –  Babar
    Commented Apr 21 at 8:00
  • $\begingroup$ Yes, $(\lambda^n+1)$ is also very similar to Fibonacci. I guess any linear binary recurrence sequence leads to a result similar to the one at mathoverflow.net/q/467934. $\endgroup$
    – GH from MO
    Commented Apr 21 at 13:16

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .