# Finding a Big Theta Bound for a Summation Involving the Möbius Inversion Formula

I am currently in the midst of a summer research project and have run across an interesting summation: $F(n) = \sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}(n - 2i + 1)P_2(i)$.

And here are some necessary definitions:

• $P_2(i)$ is the number of primitive words over the binary alphabet, and I have from one of my books that $P_2(i) = \sum\limits_{d|n}\mu(d)2^{n/d}$ (a result of the Möbius inversion formula). I have also proved that $P_2(i) \geq 2^{i-\omega(i)}$.

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

• $\omega(n)$ is the number of distinct prime factors of $n$.

I know that $\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}(n - 2i + 1)2^i$ is $\Theta(2^{n/2})$ and is an upper bound for $F(n)$. I also am pretty sure that $\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}(n - 2i + 1)2^{i-\log(i)}$ is a lower bound. But this would imply that $\sum\limits_{i=1}^{\lfloor\frac{n}{2}\rfloor}(n - 2i + 1)2^{ci}$ is a lower bound for any $c \in (0,1)$ and sufficiently large $n$, and thus $F(n)$ is $\Omega(2^{cn/2})$. But I don't think this is quite enough to prove that $F(n)$ is $\Theta(2^{n/2})$. Can anyone give me a solid proof for a $\Theta$ bound on $F(n)$?

-
If a word is not primitive, it is a power of a word of length at most half as long. There aren't many of those compared with all words of full length. So, $P_2(i)/2^i \to 1$ as $i \to \infty$ and you only need that the limit infinum is not $0$.