DEFINITIONS:
A complex number $z_0$ is called a fixed point of $f$ if $f(z_0)=z_0$. It is called a periodic point of period $n>1$ of $f$ if $f^i(z_0)\neq z_0$ for $1\leq i \leq n-1$ but $f^n(z_0)=z_0$. A complex number $z_0$ is called a preperiodic point if $z_0,f(z_0),\ldots ,f^{k-1}(z_0)$ are not periodic points but $f^k(z_0)$ is a periodic point for some $k\geq 1$. Let $Fix(f^n)=\{z\in \Bbb C\mid f^n(z)=z\}$ be the set of all fixed points of $f^n$. Let $Per_n(f)$ be the set of all periodic points of period $n$. Then it is clear $Per_n(f)\subseteq Fix(f^n)$.
QUESTION:
Consider $f(z)=z^2$.
(a) Describe $Fix(f^n)$ and all preperiodic points.
(b) Calculate $\#(Per_n(f))$.
ATTEMPT:
I answered part (a) by finding all solutions of $z^{2^n}=z$. I found that $Fix(f^n)=\{0\}\cup\{e^{2\pi ik/(2^n-1)}\mid k\in\Bbb Z , 1\leq k \leq 2^n-1\}.$ i.e. zero union all $2^n-1^{th}$ roots of unity. Then, with a little more thought, I found that $\{\text{preperiodic points of } f\}=\{e^{2\pi ir}\mid r\in \Bbb Q, r\neq {k\over{2^n-1}} \text{for any } k,n\in \Bbb N\}.$ i.e. The periodic points of $f$ are all the rational roots of unity that are not fixed points themselves.
I found part (b) to be much harder, and this is the question I pose to the forum. I calculated these sets by hand for $1\leq n\leq 8$, working with modular arithmetic, and thought I was on to something but hit a wall. Then I made the sort of obvious realization that $\#(Per_n(f))=2^n-\sum _{k\mid n, 1\leq k\leq n} \#(Per_k(f)).$ I think that this is correct, but I'm unhapy with the recursive definition (although it does simplify to be just $2^n-2$ when $2^n-1$ is prime). Is it possible to find the order of this set explicitly for all $n$?