Return to Answer

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 equation $(*)$ - 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.

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.

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 equation $(*)$ - 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 outside constant, 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$ and $\lambda_i = \omega_N^{(N-k)i}$. Such a sequence satisfies a homogeneous recurrence relation, whose coefficients come from a polynomial vanishing on all the $c_i$'s simultaneously. Since the $c_i$'s are algebraic integers, a recurrence exists with integer coefficients.

If you want a reference for all of this, I suggest this short, elementary paper by Konvalina and Liu, which proves in particular the following explicit result: For fixed $k$ and $N$, the sum $S(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).$$

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 equation $(*)$ - 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.

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^{(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^{ik}$ (0 when $N \nmid k$, 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 equation $(*)$ - 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 scalar), the other terms contribute an exponential term in $n$ of smaller magnitude.

If you want a reference for all of this, I suggest this short, elementary paper by Konvalina and Liu, in which they cite the above result and also prove that for fixed $k$ and $N$, the sum $S(n):=\sum_{j \equiv k \mod N} \binom{n}{j}$ satisfies a 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).$$

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 equation $(*)$ - 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 outside constant, 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$ and $\lambda_i = \omega_N^{(N-k)i}$. Such a sequence satisfies a homogeneous recurrence relation, whose coefficients come from a polynomial vanishing on all the $c_i$'s simultaneously. Since the $c_i$'s are algebraic integers, a recurrence exists with integer coefficients.

If you want a reference for all of this, I suggest this short, elementary paper by Konvalina and Liu, which proves in particular the following explicit result: For fixed $k$ and $N$, the sum $S(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).$$