# Hard elementary combinatorics problem

How does one compute (without brute force) the smallest integer $n$ such that

$\binom{2n}{1}(-3)^0 + \binom{2n}{3}(-3)^1 + \binom{2n}{5}(-3)^2 + \cdots + \binom{2n}{2n-1}(-3)^{(n-1)} = 0$?

-
What does $C$ mean? – Dimitrije Kostic Dec 1 '11 at 2:05
You can use \binom{a}{b} if you mean the binomial coefficient. – alex.jordan Dec 1 '11 at 2:10
@jebyrnes - is this a hint or something else? – Victor Dec 1 '11 at 2:19
@Victor: I'm not trying to criticize your question. I'm just saying you'll get more helpful responses if you use notation that people recognize. Your question will just be easier to understand. – Dimitrije Kostic Dec 1 '11 at 2:25
I hope my substantial edit doesn't offend anyone. The question was unreadable as originally posted. – user02138 Dec 1 '11 at 2:30

$(1+i \sqrt{3})^{2n} = \binom{2n}{0} (i \sqrt{3})^0 + \binom{2n}{1} (i \sqrt{3})^1 + \binom{2n}{2} (i \sqrt{3})^2 + \cdots + \binom{2n}{2n} (i \sqrt{3})^{2n}$

$(1-i \sqrt{3})^{2n} = \binom{2n}{0} (i \sqrt{3})^0 + \binom{2n}{1} (-i \sqrt{3})^1 + \binom{2n}{2} (i \sqrt{3})^2 + \cdots + \binom{2n}{2n} (i \sqrt{3})^{2n}$

Subtract both to get,

$$\frac{(1+i \sqrt{3})^{2n} - (1-i \sqrt{3})^{2n}}{2} = \binom{2n}{1} (i \sqrt{3})^1 + \binom{2n}{3} (i \sqrt{3})^3 + \cdots + \binom{2n}{2n-1} (i \sqrt{3})^{2n-1}$$

$$\frac{(1+i \sqrt{3})^{2n} - (1-i \sqrt{3})^{2n}}{2 i \sqrt{3}} = \binom{2n}{1} + \binom{2n}{3} (i \sqrt{3})^2 + \binom{2n}{5} (i \sqrt{3})^4 + \cdots + \binom{2n}{2n-1} (i \sqrt{3})^{2n-2}$$

$$\frac{(1+i \sqrt{3})^{2n} - (1-i \sqrt{3})^{2n}}{2 i \sqrt{3}} = \frac{2^{2n}}{2i\sqrt{3}} \left(\cos \left(\frac{2n \pi}{3} \right) + i \sin \left(\frac{2n \pi}{3} \right) - \cos \left(\frac{2n \pi}{3} \right) + i \sin \left(\frac{2n \pi}{3} \right)\right)$$

Hence, we get $$\binom{2n}{1} + \binom{2n}{3} (- 3)^1 + \binom{2n}{5} (- 3)^2 + \cdots + \binom{2n}{2n-1} (- 3)^{n-1} = \frac{4^{n}}{\sqrt{3}} \sin \left( \frac{2n \pi}{3} \right)$$ Hence, whenever $n = \frac{3 k}{2}$ where $k \in \mathbb{Z}$, $$\binom{2n}{1} + \binom{2n}{3} (- 3)^1 + \binom{2n}{5} (- 3)^2 + \cdots + \binom{2n}{2n-1} (- 3)^{n-1} = 0$$

-

Let's replace an explicit number $-3$ with a symbol $z$, so that we consider: $$\sum_{k=1}^n z^{k-1} \binom{2n}{2k-1} = \sum_{m=0}^{2n} \left( \frac{1-(-1)^m}{2} \right)z^{(m-1)/2} \binom{2n}{m} = \frac{\left(1+\sqrt{z}\right)^{2n} - \left(1-\sqrt{z}\right)^{2n}}{2 \sqrt{z}}$$ Now substitute $z=-3$. Notice that $1 \pm \sqrt{-3} = 2 \exp\left( \pm i \frac{\pi}{3} \right)$, so it follows that the smallest such an integer is $n=3$.

-

Here is a hint. Prove the identity \begin{align} \sum_{i = 1}^{n} \binom{2n}{2i-1} x^{i-1} = \frac{(1 + 2 \sqrt{x} + x)^{n} - (1 - 2 \sqrt{x} + x)^{n} }{2 \sqrt{x}}. \end{align} Setting $x = -3$, we have \begin{align} \frac{(1 + 2 \sqrt{-3} -3)^{n} - (1 - 2 \sqrt{-3} -3)^{n} }{2 \sqrt{-3}} = \frac{4^{n}}{\sqrt{3}} \sin (\tfrac{2 \pi n}{3}) \end{align} Using an argument involving periodicity, you should conclude that this sum vanishes infinitely often and you can therefore determine the smallest $n$ accordingly, which is $n = 3$.

-