Problem 1: Find the sum of the coefficients of the even-power terms of the polynomial $f(x)$ given that $f(1) = 5$ and $f(-1) = 3.$

To solve this problem, let’s write down a simple example: $g(x) = 4x^3 + x^2 -3x+5 .$ Now lets plug in 1 and -1. We get $\displaystyle g(1) =4 + 1-3 + 5=7$ and $\displaystyle g(-1) = -4 +1 +3+5 =5.$ We realize that if we add together $g(1)$ and $g(-1)$, the odd-power terms get canceled out, so the answer to our original problem is $\frac{f(1)+f(-1)}{2}=4.$

 

Problem 2: Find the sum $\displaystyle \sum_{k=0}^{50}\binom{100}{2k}.$

The binomial theorem says that $\displaystyle (x+y)^a = \sum_{k=0}^{a}\binom{a}{k}x^ky^{a-k}$, so we know that $\displaystyle \sum_{k=0}^{100}\binom{100}{k}=(1+1)^{100}.$ Let $\displaystyle f(x) = (x+1)^{100}=\sum_{k=0}^{100}\binom{100}{k}x^k .$ Then we are trying to find the sum of the coefficients of even-power terms of $f(x)$, and that can be done by the same trick we learned in problem 1. Thus, $\displaystyle \sum_{k=0}^{50}\binom{100}{2k} = \frac{f(1)+f(-1)}{2}=\frac{2^{100}+0}{2}=2^{99}.$

 

Problem 3. Find the sum $\displaystyle \sum_{k=0}^{33}\binom{99}{3k}.$

We put $f(x) = (x+1)^{99}$, but it is not clear how we will cancel out all powers not divisible by 3. First we need to build some theory.

 

$\displaystyle \rule{8cm}{0.4pt}$

Definition 1. An nth root of unity $\zeta$ satisfies $\zeta ^n = 1$. The kth nth root of unity is $\zeta_k=\displaystyle e^{\frac{2\pi i k}{n}}$ for $0\leq k\leq n-1.$

Example 1. There are two 2nd roots of unity, $\zeta_1 = 1$ and $\zeta_2 = -1$; these roots you know very well, since any time you take a square root, you need to add the plus-minus symbol.

Example 2. There are three 3rd roots of unity (in general, there are n nth roots of unity). Heuristically, they can be found by writing $\zeta =e^{i\theta},\displaystyle \zeta^3 =1 \implies e^{3\theta i }=1=e^{2\pi i}=e^{4\pi i}=e^{6\pi i}.$ Equating the powers, we see that $\theta = \frac{2\pi}{3}, \frac{4\pi}{3}, 2\pi$ all work. By convention, the first root of unity is always 1, corresponding with $\theta = 2\pi$. Note that large values of $\theta$ do not count as distinct roots of unity; for example, $\displaystyle e^{10/3\pi i}=e^{2\pi i}e^{4/3\pi i}=e^{4/3\pi i}=\zeta_3.$ Using Euler’s Formula $e^{i x} = \cos x + i \sin x$ we can calculate the 3rd roots of unity: $\displaystyle\zeta_1 = \cos 2\pi + i\sin 2\pi = 1,$ $\displaystyle\zeta_2= \cos\frac{2\pi }{3} + i\sin\frac{2\pi }{3} = -\frac{1}{2} +i \frac{\sqrt{3}}{2}$ and $\displaystyle\zeta_3 = \cos\frac{4\pi}{3} + i\sin\frac{4\pi}{3} = -\frac{1}{2}-i\frac{\sqrt{3}}{2}.$

 

Definition 2. A primitive root of unity is a root of unity that generates all the other roots via exponentiation. Any kth nth root of unity with gcd(k,n)=1 is primitive.

Example 3. The second 3rd root of unity $\displaystyle\zeta_2 = e^{\frac{2\pi i }{3}}$ is primitive since $\displaystyle \zeta_2^2=e^{\frac{2\pi i }{3}\cdot 2} = \zeta_3$ and $\displaystyle \zeta_2^3=e^{\frac{2\pi i }{3}\cdot 3}=\zeta_1.$ In general, the second nth root of unity is primitive (why? hint: use the gcd property). Check that the third root of unity $\zeta_3$ is also primitive.

 

Theorem 1. The sum of the nth roots of unity is 0.

Proof. Let $\omega$ be a primitive root (note that $w\neq 1$). Then $\displaystyle\sum_{k=0}^{n-1}\omega^k = \frac{\omega^n-1}{\omega -1} = \frac{1-1}{\omega -1}=0.\qquad\square$

$\displaystyle \rule{8cm}{0.4pt}$

 

OK, now we are ready to approach the problem.

Just as $1 +(-1)^n$ cancels out for odd n, $1 + w^{n} + w^{2n}$ cancels out for $n \not\equiv 0 \pmod 3$.
Proof. Consider the case $n=3m$: $\displaystyle 1+w^{3m}+w^{6m}=1+1+1=3.$ Put $n=3m+1$, and find that $\displaystyle 1 + w^{3m+1}+w^{2(3m+1)}=1+w^{3m}w^1+w^{6m}w^2 = 1+w+w^2,$ which is 0 by theorem 1, so the case  $n \equiv 1 \pmod 3$ does result in 0. Now put $n=3m+2$, and find that $\displaystyle 1 + w^{3m+2}+w^{2(3m+2)}=1+w^{3m}w^2+w^{6m}w^1w^3 =1+w^2+w$, so we have verified $n \equiv 2 \pmod 3$ as well. This principle works for any nth roots of unity, as summarized in the following theorem.

 

Theorem 2. For a set of nth roots of unity $\zeta_i$ and an integer a, $\displaystyle \sum_{k=0}^{n-1}\zeta_k^a = n$ iff n divides a and  $\displaystyle \sum_{k=0}^{n-1}\zeta_k^a = 0$ otherwise.

Proof. Let w be a primitive root. We know that $w^a = 1$ iff n divides a. In this case, $\displaystyle \sum_{k=0}^{n-1}\zeta_k^a =\sum_{k=0}^{n-1}(w^a)^k=\sum_{k=0}^{n-1} 1 = n.$ Otherwise, $w^a \neq 1$, so we can interpret the sum as geometric: $\displaystyle \sum_{k=0}^{n-1}(w^a)^k = \frac{w^{a\cdot n}-1}{w^a-1}= \frac{1-1}{w^a-1}=0.\qquad\square$

 

To finish the problem, we need to compute $\displaystyle \frac{f(1)+f(w)+f(w^2)}{3}.$ Since the actual expressions of the roots of unity look complicated, we will just manipulate the ws. $\displaystyle \frac{2^{99} + (1+w)^{99} + (1+w^2)^{99}}{3}=\frac{2^{99} + (-w^2)^{99}+(-w)^{99}}{3}$ $\displaystyle =\frac{2^{99}-2}{3}$

 

Problem 4 (North Fulton 2017 Varsity Written): Find $\displaystyle \binom{2017}{1} + \binom{2017}{5}+\binom{2017}{9}+\cdots+\binom{2017}{2017}$

Obviously, we will be using fourth roots of unity. They are: $1,-1,i,-i.$ In the previous problem, we expressed the roots of unity in terms of $w$, but since the 4th roots of unity are so simple, we will just use them directly here. OK, so we begin by filtering out the evens by using the roots 1 and $-1$:

$\displaystyle 2^{2016} = \binom{2017}{1} + \binom{2017}{3}+\binom{2017}{5}+\cdots+\binom{2017}{2017}.$ Now let’s use the roots $i,-i$:

$\displaystyle (1+i)^{2017}-(1-i)^{2017} =$ $\displaystyle \binom{2017}{0} + \binom{2017}{1}i-\binom{2017}{2}-\binom{2017}{3}i+\cdots +\binom{2017}{2017}i$$\displaystyle -\binom{2017}{0} +\binom{2017}{1}i+\binom{2017}{2}-\binom{2017}{3}i-\cdots +\binom{2017}{2017}i$$\displaystyle =2i\binom{2017}{1}-2i\binom{2017}{3}+2i\binom{2017}{5}+\cdots +2i\binom{2017}{2017}.$ Therefore, the answer is $\displaystyle 2^{2015}+\frac{(1+i)^{2017}-(1-i)^{2017}}{4i}.$ To calculate the fraction, we use $\displaystyle 1+i=\sqrt{2}e^{\pi/4} \implies (1+i)^{2017}=2^{2017/2}e^{\pi/4}=2^{1008}+i2^{1008}.$ So we have $\displaystyle 2^{2015}+\frac{2^{1008}+i2^{1008}-2^{1008}+i2^{1008}}{4i}=2^{2015}+2^{1007}.$