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

206 Views Asked by At

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

* Additional Note *

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

1

There are 1 best solutions below

2
On BEST ANSWER

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