Good afternoon. I have a particular summation,


$$\zeta\_{n,k}(N)=\frac{k!}{N^{n+1-k}}\sum\_{j=0}^n\sum\_{i=0}^{N-1}\binom{n}{j}w\_N^{(j-k)i}$$
Here, the $w\_N$ is the root of unity $w\_N=e^\frac{2i\pi}{N}$. Given certain conditions on the $n$ and $k$, it is pretty easy to show that for positive integers $k, m, n, N$,


$$n<k\Rightarrow \zeta\_{n,k}(N)=0$$
$$n=k\Rightarrow \zeta\_{n,k}(N)=k!$$
$$k+m<2n\Rightarrow \zeta\_{n,k}(N)=\frac{k!}{N^j}\binom{k+n}{m}$$


Once you are past this threshold, i've been having trouble nailing down a closed form. For cases where $j\neq k$, the term will be $0$ due to the nature of the sums of powers of complex roots of unity. Therefore, the meaningful terms occur when $j=k$ or when $i=N\cdot r$, with $r\in \mathbb{N}$. Is there a way to simplify this expression given this without involving floor function bounds on the outer sum? is there a closed form for the numbers generated?



Simplifying Root of Unity Double Summation
I will elaborate on Fedor Petrov's comment.


Interchanging the order of summation and using the binomial theorem, we remain with 
$$\frac{k!}{N^{n+1-k}}\sum\_{i=0}^{N-1} \omega\_N^{-ki} (\sum\_{j=0}^{n} \binom{n}{j} \omega\_N^{ji} (1+\omega\_N^i)^n)=$$
$$(\*)\frac{k!}{N^{n+1-k}}\sum\_{i=0}^{N-1} \omega\_N^{(N-k)i} (1+\omega\_N^i)^n.$$


Let $f(x):=x^{N-k}(1+x)^n=\sum\_{l} a\_l x^l$. Your sum is 
$$\frac{k!}{N^{n-k}} \frac{\sum\_{i=0}^{N-1} f(\omega\_N^i)}{N}$$


Now, using the formula for the geometric sum $\sum\_{i=0}^{N-1} (\omega\_N^{i})^{\ell}$ (0 when $N \nmid l$, and otherwise $N$), we find that your sum is essentially just the sum of certain coefficients of $f(x)$:
$$\frac{k!}{N^{n-k}} \sum\_{l \equiv 0 \mod N} a\_l = \frac{k!}{N^{n-k}}\sum\_{j \equiv k \mod N} \binom{n}{j}.$$
This trick is sometimes called "roots of unity filter".


The best closed form seems to be expression $(\*)$ - for fixed $N$ this is a simple, finite sum to evaluate and understand (try $N=2$), and it also allows one to perform asymptotic analysis - the term $i=0$ contributes the majority of the sum ($2^n$ times a simple expression), the other terms contribute an exponential term in $n$ of smaller magnitude.


Thinking of $N,k$ as fixed, and ignoring the outer term, your sum is a linear combination of $N$ geometric sequences: $$\sum\_{i=0}^{N-1} \lambda\_i c\_i^n,$$ where $$c\_i=1+\omega\_N^i, \lambda\_i = \omega\_N^{(N-k)i}.$$ 
Such a sequence necessarily satisfies a homogeneous recurrence relation, whose coefficients belong to a polynomial vanishing on all the $c\_i$'s simultaneously.


Since the $c\_i$'s are algebraic integers, a recurrence exists with integer coefficients. We can find it: Since $x^n-1$ vanishes on $\omega\_n^i=c\_i-1$, the polynomial $$(x-1)^n-1=x^n+\sum\_{i=1}^{n-1}x^{n-i}\binom{n}{i}(-1)^{i}+((-1)^n-1)$$ vanishes on the $c\_i$'s, and hence the sequence
$$S(n):=\frac{1}{N}(\sum\_{i=0}^{N-1} \omega\_N^{(N-k)i} (1+\omega\_N^i)^n)=\sum\_{j \equiv k \mod N} \binom{n}{j}$$ 
satisfies the following linear homogeneous recurrence relation with integer coefficients:


$$S(n) = \sum\_{j=0}^{N-1}(-1)^{j-1} \binom{N}{j}S(n-j) + (1+(-1)^{n-1})S(n-N).$$


If you want a reference for all of this, I suggest [this short, elementary paper by Konvalina and Liu](http://www.sciencedirect.com/science/article/pii/S0893965997000517).


