# Rewrite $\sum_{n\ge0}{z^{kn}}$ to $\sum_{n\ge0}{f(n,k)z^n}$

In the simplest case: $\sum_{n\ge0}{z^{2n}}=\sum_{n\ge0}{\frac12((-1)^n+1)z^n}$.

How to express $f(n,k)$ in closed form? If it's intractable, how to avoid piecewise expression?

## 2 Answers

$$f(n,k)=\mathbf 1_{k\mid n}=\frac1k\sum_{j=1}^k\cos(2jn\pi/k)$$

Here goes an explanation: the crucial tool here is the complex number $$\zeta=\mathrm e^{2\mathrm i\pi/k}=\cos(2\pi/k)+\mathrm i\sin(2\pi/k),$$ known as the $k$th primitive root of unity. You may already be aware of the fact that $$\zeta+\zeta^2+\cdots+\zeta^k=0,$$ since, for example, the LHS is, by the usual formula for geometric sums with ratio different from $1$, $$\zeta\frac{1-\zeta^k}{1-\zeta}=0.$$ Likewise, let us evaluate, for some integer $n$, the sum $$\zeta^n+\zeta^{2n}+\cdots+\zeta^{kn}.$$ Either $\zeta^n=1$, then the sum is $k$. Or $\zeta^n\ne1$, then the same argument as before shows that it is $$\zeta^n\frac{1-\zeta^{kn}}{1-\zeta^n}=0,$$ since $\zeta^{kn}=(\zeta^k)^n=1^n=1$. The first case happens when $k\mid n$, the second case for every other $n$. Considering the real parts yields the formula above, since $\Re(\zeta^{jn})=\cos(2jn\pi/k)$ for every $j$.

All these arguments are (basics from) discrete Fourier theory. Needless to say, they apply to your other question as well.

• WOW! great formula! Thank you! does the explanation is this comment? – Dan Oak Oct 1 '14 at 16:26
• thank you a lot!! That was very interesting and i'm inspired to learn DFT now! [: – Dan Oak Oct 2 '14 at 14:23

Try $$f(n,k)=\left\lfloor\frac{n}{k}-\Big\lfloor\frac{n-1}{k}\Big\rfloor \right\rfloor$$

• Thank you. Although, I was interested in closed-form, this one is very interesting and simple. Flooring can do magic thinks, indeed. :D I see it can be very useful in different problems. – Dan Oak Oct 2 '14 at 14:41