Proving that $\sum_{i=0}^{n/2} (-1)^i \frac{n}{n-i} {n-i \choose i} = 2\cos(\frac{\pi n}{3})$

Question

I was investigating the Girard-Waring identity, specifically for two variables:

$$x_1^n + x_2^n = \sum_{i=0}^{\frac{n}{2}} (-1)^i \frac{n}{n-i} {n-i \choose i}(x_1+x_2)^{n-2i}(x_1x_2)^i $$

This lead to me considering the following simpler expression:

$$\sum_{i=0}^{\frac{n}{2}} (-1)^i \frac{n}{n-i} {n-i \choose i} $$

Plugging this into WolframAlpha tells us that the expression is actually equal to $2\cos\left(\frac{\pi n}{3}\right)$, but I don't know how to prove this.

Using Chebyshev polynomials or De Moivre's Theorem I made some progress:

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

But I'm not sure how to show this is equal to the original expression. Any help in proving this identity would be much appreciated!

Answer 1

I saw that one binomial coefficient, so that got me thinking about Fibonacci polynomials, and what do you know I find that this is an evaulation of a Lucas polynomial

$$L_n(x) = \sum_{k=0}^{\lfloor n/2 \rfloor}\frac{n}{n-k}\binom{n-k}{k}x^{n-2k}$$

By the Wikipedia page, $L_n(x) = \alpha^n(x) + \beta^n(x)$ where $\alpha(x) = \frac{x+\sqrt{x^2+4}}{2}$ and $\beta(x) = \frac{x-\sqrt{x^2+4}}{2}$

Now note that $(-1)^k = i^{-n} i^{n-2k}$

Using the identities $e^{ix} = \cos(x) + i\sin(x)$ and $\cos(x) = \frac{e^{ix} + e^{-ix}}{2}$, we obtain

\begin{align*} &\sum_{k=0}^{n/2} (-1)^k \frac{n}{n-k}\binom{n-k}{k} \\ &= i^{-n} L_n(i) \\ &= i^{-n} (\alpha^n(i)+\beta^n(i))\\ &= i^{-n} \left(\left(\frac{i+\sqrt{3}}{2}\right)^n+\left(\frac{i-\sqrt{3}}{2}\right)^n\right) \\ &= \left(\frac{1+i\sqrt{3}}{2}\right)^n+\left(\frac{1-i\sqrt{3}}{2}\right)^n \\ &= e^{\frac{n\pi i}{3}} + e^{-\frac{n\pi i}{3}} \\ &= 2\cos\left(\frac{n\pi}{3}\right) \end{align*}

Answer 2

You can actually use the aforementioned Girard-Waring identity to get your expression: $$\begin{split} 2\cos\left(\frac{\pi n}{3}\right) = e^{i\frac{\pi n}{3}} + e^{-i\frac{\pi n}{3}} \end{split} = \left(e^{i\frac{\pi}{3}}\right)^n + \left(e^{-i\frac{\pi}{3}}\right)^n =: x_1^n + x_2^n$$ by observing that $x_1 + x_2 = x_1x_2 = 1$, and as such only the other coefficients remain.
(You could see that as "cheating" since I used the identity I guess, would be neat if someone else were to have another path to the solution, but at least this is a simple short answer).