Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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$.

share|improve this answer
True, but it would be more fun to actually write down the dirichlet generating function for this, and that way get better asymptotics than what the OP is asking for :) –  Igor Rivin Jul 4 '12 at 0:39
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.