Alternating Lacunary Sum of Binomial Coefficients $\sum_{j=0}^{n} \binom{n}{dj}(-1)^j$

From this question and the solution here a nice closed form has been provided for the sum of a lacunary series of binomial coefficients as follows:

$$\sum_{j=0}^{n} \binom{n}{dj} = \frac{1}{d} \sum_{j=0}^{d-1} (1 + \omega^j)^n$$ where $\omega$=primitive $d$-th root of unity.

The question here is whether there is a closed form (or a form similar to the above) if the lacunary series is of alternating sign, i.e. $$\sum_{j=0}^n \binom n{dj}(-1)^j$$

Perhaps the upper limit of the original summation should be $\big\lfloor\frac nd\big\rfloor$.

• $$\sum_{j = 0}^n \binom{n}{dj}(-1)^j = 2\sum_{j = 0}^n \binom{n}{2dj} - \sum_{j = 0}^n \binom{n}{dj},$$ assuming $d \in \mathbb{N}\setminus \{0\}$. – Daniel Fischer Nov 24 '16 at 15:48
• @DanielFischer - That is most imaginative! (+1). If you would post that as a solution, I would upvote and accept it. – hypergeometric Nov 24 '16 at 15:59

For the factors $(-1)^j$, we have "sum of terms with even index minus sum of terms with odd index", and that can be expressed as "twice the sum of terms with even index minus sum of all terms", that is

$$\sum_{j = 0}^n \binom{n}{dj} (-1)^j = 2\sum_{j = 0}^n \binom{n}{2dj} - \sum_{j = 0}^n \binom{n}{dj},$$

and we can express each of the terms on the right with what we know.

Generally, for $n \geqslant d$, we have

\begin{align} \sum_{j = 0}^{d-1} a_j(1+\omega^j)^n &= \sum_{j = 0}^{d-1} \sum_{k = 0}^n \binom{n}{k} a_j\omega^{jk} \\ &= \sum_{k = 0}^n \binom{n}{k}\sum_{j = 0}^{d-1} a_j\omega^{jk}. \end{align}

The $d\times d$-matrix with entries $\omega^{jk}$ with $0 \leqslant j,k < d$ is invertible (it's a Vandermonde matrix), and the factors $\omega^{jk}$ are $d$-periodic in $k$. Thus a sum

$$\sum_{k = 0}^n \binom{n}{k}\cdot b_k$$

can be expressed as a linear combination of the $(1 + \omega^j)^n$, $0 \leqslant j < d$ if and only if the factor sequence $(b_k)$ is periodic with period $d$.

• Very nice answer. Thanks for posting. – hypergeometric Nov 24 '16 at 17:08
• very clever indeed ! – G Cab Nov 24 '16 at 17:10