2

Define

$$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$

where $\mu()$ is the Möbius function.

Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq c(n)$ for all large enough $n$ such that

$$\limsup \frac{a(n)}{c(n)} = 1 = \liminf \frac{a(n)}{b(n)}.$$

The first few values of $a(n)$ are 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858.

  • Why do you think they must exist and what did you do so far (except for writing down the first few values)? – AlexR Nov 05 '14 at 19:30
  • I think the lims of $a(n)/2^n$ might be more interesting. – marty cohen Nov 05 '14 at 19:45
  • We have $$a(n) \geqslant \frac{1}{n} \left(2^n - 2\sqrt{n} 2^{n/2}\right) \to \infty.$$ – Daniel Fischer Nov 05 '14 at 19:46
  • @DanielFischer I have mucked up the question. Would you mind helping me fix it? I am trying to ask about the asymptotics of a function bounding the function from above and the asymptotics of a function bounding the function from below. What's the right way to say that? –  Nov 05 '14 at 19:50
  • You are looking for - easily computable - $b,c$ with $b(n) \leqslant a(n) \leqslant c(n)$ for all [large enough?] $n$ such that $$\limsup \frac{a(n)}{c(n)} = 1 = \liminf \frac{a(n)}{b(n)},$$ or do you want even better asymptotics [of the sort that $\limsup (c(n) - a(n)) < \infty$]? – Daniel Fischer Nov 05 '14 at 19:54
  • @DanielFischer I think your first definition looks great. I will copy it if you don't mind. –  Nov 05 '14 at 19:56
  • You can copy it, I don't mind. But we can take $b(n) = \frac{1}{n}\left(2^n - 2\sqrt{n}2^{n/2}\right)$ and $c(n) = \frac{1}{n}\left(2^n + 2\sqrt{n}2^{n/2}\right)$, and have $\frac{b(n)}{c(n)} \to 1$. – Daniel Fischer Nov 05 '14 at 19:59
  • @DanielFischer If you don't mind adding that as an answer I will happily accept it. –  Nov 05 '14 at 20:01

1 Answers1

6

For $d = n$, we always have the contribution

$$\mu\left(\frac{n}{n}\right)2^n = 2^n$$

to the sum. The remaining sum satisfies

$$\left\lvert \sum_{\substack{d\mid n\\ d < n}}\mu\left(\frac{n}{d}\right)2^d\right\rvert\leqslant \sum_{\substack{d\mid n\\ d < n}} 2^d \leqslant \tau(n)2^{n/2} \leqslant 2\sqrt{n}2^{n/2}$$

since $d\leqslant \frac{n}{2}$ for all divisors $< n$, and there are no more that $2\sqrt{n}$ divisors of $n$. (We can take a better bound on $\tau(n)$ to obtain tighter bounds, but off-hand, I don't recall the best bounds on $\tau$.)

Then we can take

$$b(n) = \frac{1}{n}\left(2^n - 2\sqrt{n}2^{n/2}\right) \leqslant a(n) \leqslant \frac{1}{n}\left(2^n + 2\sqrt{n}2^{n/2}\right) = c(n),$$

and since $b\sim c$ have the asymptotic equality

$$a(n) \sim \frac{2^n}{n}.$$

Daniel Fischer
  • 206,697