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?


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

  • $\begingroup$ WOW! great formula! Thank you! does the explanation is this comment? $\endgroup$ – Dan Oak Oct 1 '14 at 16:26
  • $\begingroup$ thank you a lot!! That was very interesting and i'm inspired to learn DFT now! [: $\endgroup$ – 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 $$

  • $\begingroup$ 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. $\endgroup$ – Dan Oak Oct 2 '14 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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