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](http://mathworld.wolfram.com/MoebiusInversionFormula.html)). I have also proved that $P\_2(i) \geq 2^{i-\omega(i)}$.
* $\mu(d)$ is the [Möbius function](http://mathworld.wolfram.com/MoebiusFunction.html).
* $\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)$?



Finding a Big Theta Bound for a Summation Involving the Möbius Inversion Formula
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$.


