Asymptotic growth of a convolution (counting n-bead 2-colour necklaces) I'm seeking the asymptotic growth of the function $$f(n) = \frac{1}{n}\sum_{d | n} 2^d \varphi(n/d) = \frac{1}{n} \sum_{k=1}^n 2^{\gcd(n, k)} \tag{1}$$
which counts the number of necklaces made of $n$ black or white beads where turning over is not allowed (sequence A000031 in the OEIS).  Here, $\varphi$ is Euler's totient function. Formula (1) for $f$ is easily established by applying Burnside's lemma to the following action of $G = \mathbf{Z}/(n)$ on the set $\{0, 1\}^G$: $$(g\cdot f)(x) = f(xg).$$
The two representations of $f$ given in (1) yield the following bounds:
$$\frac{2^n}{n} \le f(n) \le \frac{2^{n+1}-2}{n} \tag{2}$$
the lower bound coming from picking $d = n$ and the upper bound by noting that $\gcd(n, k) \le k$ and summing the geometric series.
I'm pretty certain that $$f(n) \sim \frac{2^n}{n} \quad (n \to \infty)\tag{3}$$
but from (2) we can only get 
$$1 \le \varliminf_{n \to \infty} \frac{n f(n)}{2^n}\text{ and } \varlimsup_{n \to \infty} \frac{n f(n)}{2^n} \le 2.$$
My question(s) are: is (3) true? If so, how is it proved? If not, what is the correct statement?

Looking at the upper bound:
$$
\sum_{k=1}^n 2^{\operatorname{gcd}(n,k)}
= 2^n + \sum_{k=1}^{n-1} 2^{\operatorname{gcd}(n,k)}
$$
Now, each $1\leq k\leq n-1$ which divides $n$ is at most $\frac{n}{2}$; and there will be at most $n-1$ such terms. So we get the upper bound:
$$
\sum_{k=1}^n 2^{\operatorname{gcd}(n,k)}
\leq 2^n + (n-1)\cdot  2^{n/2} = 2^n + o(2^n)
$$
which should now allow you to conclude.
