I am trying to work through a few problems, and one asks to sum over the Fibonacci numbers which are even-valued (it is the Euler Project problem #2). I realized that (if we index like $\langle 1, 2, 3, 5, 8, \ldots \rangle$) that $F_n$ is even $\iff n \equiv 1~(mod~3)$. Therefore I thought that I would take the generating function I have
\begin{equation} F(z) = \frac{1+z}{1-z-z^2} = \sum_{n\geq0}F_nz^n \end{equation}
and try to find
\begin{equation} G(z) = \sum_{n\geq0}F_n[n \equiv 1~(mod~3)]z^n \end{equation}
where the bracket notation just evaluates to $1$ if the statement is true and $0$ if it is false. Then I could use
\begin{equation} \frac{1}{1-z}G(z) = \sum_{n\geq0}z^n\sum_{k\leq n}{F_n[n \equiv 1~(mod~3)]} \end{equation}
and probably be able to extract coefficients how I need to. I know that for any generating function
\begin{equation} F(z) = \sum_{n \geq 0}a_nz^n \end{equation}
implies that
\begin{equation} \frac{F(z) + F(-z)}{2} = \sum_{n \geq 0}a_n[n \equiv 0~(mod~2)]z^n \end{equation}
and I was wondering if there was a simple generalization to the same thing $mod~k$, possibly with the restriction that $k$ is prime.
Edit: Also I realized that if the solution is similar to the one for $2$, then this is equivalent to finding units in the complex field $\omega_1, \omega_2, \ldots, \omega_l$ such that
\begin{equation} \omega_1^n + \omega_2^n + \ldots + \omega_l^n = [n \equiv 0~(mod~k)] \end{equation}
where $l$ is finite (and hopefully small), I assumed $l = 3$ was probably sufficient but was unable to find any numbers that work.
I actually just solved this so no need, but the solution is that we use the $k$ roots of unity, and then
\begin{equation} \omega_1^n + \omega_2^n + \ldots + \omega_k^n = k[n \equiv 0~(mod~k)] \end{equation}
but I believe this only works when $k$ is prime.
Hint:
$F(z)+F(-z)=F(z e^{i0(2 \pi /2)})+F(z e^{i1(2 \pi /2)})$
then what is $F(z e^{i0(2 \pi /3)})+F(z e^{i1(2 \pi /3)})+F(z e^{i2(2 \pi /3)})$ ?
and higher unity roots ?
You can find that somewhere on Wikipedia (don't remember the english name given to that).