# Ramus's Identity

## Theorem

Let $k, m, n \in \Z_{\ge 0}$ be positive integers such that $0 \le k < m$.

Then:

 $\displaystyle \sum_{j \mathop \ge 0} \binom n {j m + k}$ $=$ $\displaystyle \dbinom n k + \dbinom n {m + k} + \dbinom n {2 m + k} + \cdots$ $\displaystyle$ $=$ $\displaystyle \dfrac 1 m \sum_{0 \mathop \le j \mathop < m} \left({2 \cos \dfrac {j \pi} m}\right)^n \cos \dfrac {j \left({n - 2 k}\right) \pi} m$

## Proof

Let $\omega := e^{2 \pi i / m}$.

Then by the Binomial Theorem:

$(1): \quad \displaystyle \sum_{0 \mathop \le j \mathop < m} \left({1 + \omega^j}\right)^n \omega^{-j k} = \sum_t \sum_{0 \mathop \le j \mathop < m} \binom n t \omega^{j \left({t - k}\right)}$
$\displaystyle \sum_{0 \mathop \ge j \mathop < m} \omega^{j \left({t - k}\right)} = \begin{cases} \dfrac {1 - \omega^{m \left({t - k}\right)} } {1 - \omega^{t - k} } & : t - k \not \equiv 0 \pmod m \\ m & : t \equiv k \pmod m \end{cases}$

We have that:

$\omega = \exp \dfrac {2 \pi i} m \implies \omega^m = 1$

and so:

 $\displaystyle \sum_{0 \mathop \le j \mathop < m} \omega^{r j}$ $=$ $\displaystyle \frac {1 - \omega^{r m} } {1 - \omega^r}$ Sum of Geometric Progression $\displaystyle$ $=$ $\displaystyle m \left[{r \equiv 0 \pmod m}\right]$ where $\left[{\cdots}\right]$ is Iverson's convention

Thus the summation on the right hand side of $(1)$ is:

$m \displaystyle \sum_{t \bmod m \mathop = k} \binom n t$

The summation on the left hand side of $(1)$ is:

 $\displaystyle \sum_{0 \mathop \le j \mathop < m} \left({1 + \omega^j}\right)^n \omega^{-j k}$ $=$ $\displaystyle \sum_{0 \mathop \le j \mathop < m} \left({\omega^{-j / 2} + \omega^{j / 2} }\right)^n \omega^{j \left({n / 2}\right) - k}$ $\displaystyle$ $=$ $\displaystyle \sum_{0 \mathop \le j \mathop < m} \left({2 \cos \dfrac {j \pi} m}\right)^n \omega^{j \left({n / 2}\right) - k}$

Because the right hand side is wholly real, so must the left hand side be.

So, taking the real parts of the left hand side and equating it to the right hand side reveals the result.

$\blacksquare$

## Examples

### Example: $k = 1, m = 3$

 $\displaystyle \sum_{j \mathop \ge 0} \binom n {3 j + 1}$ $=$ $\displaystyle \binom n 1 + \binom n 4 + \binom n 7 + \cdots$ $\displaystyle$ $=$ $\displaystyle \dfrac 1 3 \left({2^n + 2 \cos \dfrac {\left({n - 2}\right) \pi} 3}\right)$

## Source of Name

This entry was named for C. Ramus.