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$?
 A: 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$.
A: 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$.
A: $(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 $$
