Combinatorial Sums
This is an interesting class of problems I came across in my math class1. My teacher showed a pretty ingenious solution but didn’t go in too deep with it. A few weeks later I watched this video by 3Blue1Brown, in which Grant introduces the concept of generating functions, and the solution overall reminded me of that problem, so I decided to write this as a note (and mostly to test out MathJax on this site).
The problem
The problem goes a little like this. Consider the following sum, where $n \in 4\mathbb{N}$.
$$ S = \sum_{k = 0}^{n/4} \binom{n}{4k} = \binom{n}{0} + \binom{n}{4} + \binom{n}{8} + \binom{n}{12} + \dots + \binom{n}{n} $$One interesting way to evaluate it involves treating it as a sum of binomial expansions, so our generating function in this case is the following polynomial.
$$ \begin{align*} f(x) &= (1 + x)^{n} \\\\ &= \sum_{k = 0}^{n} \binom{n}{k} x^k \\\\ &= \binom{n}{0} + \binom{n}{1} x + \binom{n}{2} x^{2} + \dots + \binom{n}{n} x^{n} \end{align*} $$Now, we need to express the original sum in terms of $f$. To do this, we need to find some values of $x$ for which all terms but the powers of 4 will cancel. In such situations, thinking about the roots of unity can be incredibly fruitful. So, let’s have $x$ take all values of the 4th roots of unity $R(4)$.
$$ \begin{alignat*}{2} f(1) = (1 + 1)^{n} &= \sum_{k = 0}^{n} \binom{n}{k} 1^{n - k} \cdot 1^{k} &&= \sum_{k = 0}^{n} \binom{n}{k} \\\\ f(i) = (1 + i)^{n} &= \sum_{k = 0}^{n} \binom{n}{k} 1^{n - k} \cdot i^{k} &&= \sum_{k = 0}^{n} i^{k} \binom{n}{k} \\\\ f(-1) = (1 - 1)^{n} &= \sum_{k = 0}^{n} \binom{n}{k} 1^{n - k} \cdot (-1)^{k} &&= \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} \\\\ f(-i) = (1 - i)^{n} &= \sum_{k = 0}^{n} \binom{n}{k} 1^{n - k} \cdot (-i)^{k} &&= \sum_{k = 0}^{n} (-i)^{k} \binom{n}{k} \end{alignat*} $$Expanding them out we find that terms do indeed cancel.
$$ \begin{alignat*}{6} f(1) = (1 + 1)^{n} &= &&\binom{n}{0} &&+ \binom{n}{1} 1 &&+ \binom{n}{2} 1^{2} &&+ \dots + &&\binom{n}{n} 1^{n} \\\\ f(i) = (1 + i)^{n} &= &&\binom{n}{0} &&+ \binom{n}{1} i &&+ \binom{n}{2} i^{2} &&+ \dots + &&\binom{n}{n} i^{n} \\\\ f(-1) = (1 - 1)^{n} &= &&\binom{n}{0} &&+ \binom{n}{1} (-1) &&+ \binom{n}{2} (-1)^{2} &&+ \dots + &&\binom{n}{n} (-1)^{n} \\\\ f(-i) = (1 - i)^{n} &= &&\binom{n}{0} &&+ \binom{n}{1} (-i) &&+ \binom{n}{2} (-i)^{2} &&+ \dots + &&\binom{n}{n} (-i)^{n} \\\\ \end{alignat*} $$Notice that, when adding all of these up, the terms with the same binomial coefficients will end up of the form:
$$ \binom{n}{k} \left(1^{k} + (-1)^{k} + i^{k} + (-i)^{k}\right) $$It turns out that the sum in the right parenthesis is equal to $0$ for $k \not\equiv 0 \pmod{4}$ and $4$ otherwise. This holds for all sums of powers of roots of unity (see the video for a nice visual explanation).
Anyhow, now we can add up the 4 sums, which leaves us with
$$ \begin{align*} f(1) + f(i) &+ f(-1) + f(-i) = \\\\ &= 2^{n} + (1 + i)^{n} + 0^{n} + (1 - i)^{n} \\\\ &= 4\left[\binom{n}{0} + \binom{n}{4} + \binom{n}{8} + \binom{n}{12} + \dots + \binom{n}{n} \right] \\\\ &= 4S \end{align*} $$Now we can do some relatively simple manipulations to solve for S. Note that, in order to calculate $(1 \pm i)^n$ we will write it in polar form or using Euler’s formula notation.
$$ \begin{alignat*}{2} 1 \pm i &= \sqrt{2} \left(\cos{\frac{\pi}{4}} \pm i\sin{\frac{\pi}{4}} \right) &&= \sqrt{2}e^{i\frac{\pi}{4}} \\\\ (1 \pm i)^{n} &= \sqrt{2}^{n} \left(\cos{\frac{n\pi}{4}} \pm i\sin{\frac{n\pi}{4}} \right) &&= \sqrt{2}^{n} e^{ni\frac{\pi}{4}} \end{alignat*} $$Thus, the final answer is
$$ \begin{align*} S &= \frac{1}{4} \left( 2^{n} + (1 + i)^{n} + (1 - i)^{n} \right) \\\\ &= \frac{1}{4} \left( 2^{n} + \sqrt{2}^{n}\left( \cos{\frac{n\pi}{4}} + i\sin{\frac{n\pi}{4}} + \cos{\frac{n\pi}{4}} - i\sin{\frac{n\pi}{4}} \right) \right) \\\\ &= \frac{1}{4} \left( 2^{n} + 2^{n/2} \cdot 2 \cdot \cos{\frac{n\pi}{4}} \right) \\\\ &= \frac{1}{2} \left( 2^{n-1} + 2^{n/2} \cos{\frac{n\pi}{4}}\right) \end{align*} $$Generalizing
This method works for any similar sum of binomial coefficients, where $p, n \in \mathbb{N} $ and $p \vert n$
$$ \sum_{k = 0}^{n/p} \binom{n}{pk} = \binom{n}{0} + \binom{n}{p} + \binom{n}{2p} + \binom{n}{3p} + \dots + \binom{n}{n} $$Where you evaluate $f(x) = (1 + x)^{n}$ in the $p$th roots of unity $R(p) = \\{ 1, \varepsilon, \varepsilon^{2}, \dots, \varepsilon^{n-1} \\}$ ($\varepsilon$ is the notation I use in my math class, however I’ve also seen $\zeta$ used for this).
Offsetting
You may need to offset the terms in the sum by some value $q \in \mathbb{N}$. Let’s take for example the first sum and offset it by, say, $3$, so that we get the sum
$$ S_{3} = \binom{n}{3} + \binom{n}{7} + \binom{n}{11} + \binom{n}{15} + \dots + \binom{n}{n} $$In this case, all you need to do is evaluate the generating function $f$ at the cubes of the 4th roots of unity.
$$ S_{3} = \frac{1}{4} \left(f(1^{3}) + f((-1)^{3}) + f(i^{3}) + f((-i)^3) \right) $$More generally, you evaluate the function at $x^{q}, \forall x \in R(p)$.
See also
I really recommend watching Olympiad level counting (generating functions) by 3Blue1Brown for a much better explanation of this idea.
C. Năstăsescu, M. Brandiburu, C. Niță and D. Joița, „Exerciții și probleme de algebră pentru clasele IX–XII”, Editura Didactică și Pedagogică, București, pp. 80, 1981 ↩︎