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