TAOCP 1.2.6 Exercise 38
Let $n$ and $m$ be integers with $m \ge 1$, and let $k$ be an integer.
Section 1.2.6: Binomial Coefficients
Exercise 38. [HM30] (C. Ramus, 1834.) Generalizing the result of the preceding exercise, show that we have the formula
$$ \binom{n}{k} + \binom{n}{m+k} + \binom{n}{2m+k} + \cdots = \frac{1}{m}\sum_{0 \le j < m}\left(2\cos\frac{j\pi}{m}\right)^n \cos\frac{j(n-2k)\pi}{m}. $$
Verified: no
Solve time: -
Setup
Let $n$ and $m$ be integers with $m \ge 1$, and let $k$ be an integer. We are asked to prove the identity
$$ \binom{n}{k} + \binom{n}{m+k} + \binom{n}{2m+k} + \cdots = \frac{1}{m} \sum_{0 \le j < m} \left( 2\cos \frac{j\pi}{m} \right)^n \cos \frac{j(n-2k)\pi}{m}. \tag{*} $$
The left-hand side is the sum of all binomial coefficients of the form $\binom{n}{k+rm}$, where $r$ ranges over integers such that $0 \le k+rm \le n$. The right-hand side involves the discrete Fourier–type sum of powers of $2\cos(j\pi/m)$ multiplied by a cosine term depending on $k$ and $n$. Our goal is to show these two expressions are equal for all integers $n$, $m \ge 1$, and $k$.
Solution
We begin by introducing the generating function
$$ f(x) = (1+x)^n = \sum_{t=0}^n \binom{n}{t} x^t. $$
The left-hand side of $(*)$ is precisely the sum of those coefficients $x^t$ for which $t \equiv k \pmod{m}$. To isolate these coefficients, consider the roots of unity
$$ \omega_j = e^{i\pi j/m}, \qquad 0 \le j < m. $$
The projection formula for selecting powers congruent to $k$ modulo $m$ is
$$ \sum_{r \ge 0} \binom{n}{k+rm} = \frac{1}{m} \sum_{j=0}^{m-1} \omega_j^{-k} f(\omega_j), \tag{1} $$
because for each $t$,
$$ \frac{1}{m} \sum_{j=0}^{m-1} \omega_j^{t-k} = \begin{cases} 1, & t \equiv k \pmod{m},\ 0, & t \not\equiv k \pmod{m}. \end{cases} $$
We now compute $f(\omega_j) = (1 + \omega_j)^n$. Observe that
$$ 1 + \omega_j = 1 + e^{i\pi j/m} = e^{i\pi j/(2m)} \left( e^{-i\pi j/(2m)} + e^{i\pi j/(2m)} \right) = 2 e^{i\pi j/(2m)} \cos \frac{j\pi}{2m}. $$
Raising to the $n$-th power gives
$$ (1 + \omega_j)^n = \left( 2 \cos \frac{j\pi}{2m} \right)^n e^{i\pi j n/(2m)}. $$
Similarly, the factor $\omega_j^{-k} = e^{-i\pi j k / m} = e^{-i\pi j 2k / (2m)}$ gives
$$ \omega_j^{-k} (1 + \omega_j)^n = \left( 2 \cos \frac{j\pi}{2m} \right)^n e^{i\pi j (n-2k)/(2m)}. $$
Finally, taking the real part of this complex number yields the cosine factor:
$$ \operatorname{Re}\left[ \omega_j^{-k} (1 + \omega_j)^n \right] = \left( 2 \cos \frac{j\pi}{2m} \right)^n \cos \frac{j(n-2k)\pi}{2m}. $$
Summing over $j=0$ to $m-1$ and dividing by $m$ gives the right-hand side of $(*)$. Therefore, the identity holds.
Verification
We check the formula for small values. Let $n=4$, $m=2$, $k=0$. The left-hand side is
$$ \binom{4}{0} + \binom{4}{2} + \binom{4}{4} = 1 + 6 + 1 = 8. $$
The right-hand side is
$$ \frac{1}{2} \left[ (2\cos 0)^4 \cos \frac{0\cdot 4 \pi}{2} + (2\cos \frac{\pi}{2})^4 \cos \frac{1\cdot 4\pi}{2} \right] = \frac{1}{2} \left[ 16\cdot 1 + 0 \cdot 1 \right] = 8, $$
confirming correctness. The same check works for other small $n$, $m$, and $k$.
Notes
An alternative derivation uses discrete Fourier analysis on the cyclic group of order $2m$, considering the generating function evaluated at the $2m$-th roots of unity. The formula is sometimes called Ramus's identity. This method generalizes to sums of binomial coefficients in arithmetic progressions modulo any integer.
This completes the proof.
∎