1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ $$\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\}$. $\endgroup$ – Daniel Fischer Nov 24 '16 at 15:48
  • $\begingroup$ @DanielFischer - That is most imaginative! (+1). If you would post that as a solution, I would upvote and accept it. $\endgroup$ – hypergeometric Nov 24 '16 at 15:59
3
$\begingroup$

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

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

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.