Another prime year sum!

Let us define

$\displaystyle S_n = \binom{n}{0} - \binom{n-1}{1} + \cdots + {(-1)}^{\left \lfloor n/2 \right \rfloor} \binom{n - \left \lfloor n/2 \right \rfloor}{\left \lfloor n/2 \right \rfloor}$

For $n=2m$ ,

$\displaystyle S_{2m} = \binom{2m}{0} - \binom{2m-1}{1} + \cdots + {(-1)}^m \binom{m}{m}$

$\displaystyle S_{2m-1} = \binom{2m-1}{0} - \binom{2m-2}{1} + \cdots + {(-1)}^{m-1} \binom{m}{m-1}$

$\displaystyle S_{2m-2} = \binom{2m-2}{0} - \binom{2m-3}{1} + \cdots + {(-1)}^{m-1} \binom{m-1}{m-1}$

Therefore,

$\displaystyle S_{2m-1} - S_{2m-2} = \binom{2m-1}{0} - \binom{2m-1}{1} + \binom{2m-2}{2} - \cdots + {(-1)}^{m-1}\binom{m+1}{m-1} - {(-1)}^{m-1} \binom{m-1}{m-1}$

Since $\binom{2m-1}{0} = \binom{2m}{0}$ ,

$\displaystyle S_{2m-1} - S_{2m-2} = S_{2m} - {(-1)}^m \binom{m}{m} - {(-1)}^{m-1} \binom{m-1}{m-1}$

$S_{2m-1} = S_{2m} + S_{2m-2}$

For $n=2m+1$ ,

$\displaystyle S_{2m+1} = \binom{2m+1}{0} - \binom{2m}{1} + \cdots + {(-1)}^{m} \binom{m+1}{m}$

$\displaystyle S_{2m} = \binom{2m}{0} - \binom{2m-1}{1} + \cdots + {(-1)}^m \binom{m}{m}$

$\displaystyle S_{2m-1} = \binom{2m-1}{0} - \binom{2m-2}{1} + \cdots + {(-1)}^{m-1} \binom{m}{m-1}$

$\displaystyle S_{2m} - S_{2m-1} = \binom{2m}{0} - \binom{2m}{1} + \cdots + {(-1)}^{m} \binom{m+1}{m}$

$\displaystyle S_{2m} - S_{2m-1} = S_{2m+1}$

$\displaystyle S_{2m} = S_{2m-1} + S_{2m+1}$

Hence, our recurrence relation for $S_n$ becomes,

$\displaystyle S_n = S_{n-1} + S_{n+1}, n\geq 2$

$\displaystyle S_1 = 1, S_2 = 0$

Characteristic equation becomes - $x^2 - x + 1 =0$

$\displaystyle \implies S_n = A z^n + B z^{-n}$ , where $z = \frac{1 + \sqrt{3}\iota}{2} = e^{i\pi/3}$

$\displaystyle S_1 = A e^{i\pi/3} + B e^{-i\pi/3} = 1$

$\displaystyle S_2 = A e^{2i\pi/3} + B e^{-2i\pi/3} = 0$

$\displaystyle \implies A = \frac{1}{1+e^{i\pi/3}}, B = \frac{e^{i\pi/3}}{1+e^{i\pi/3}}$

$\displaystyle S_n = \frac{e^{ni\pi/3}}{1 + e^{i\pi/3}} + \frac{e^{(1-n)i\pi/3}}{1+e^{i\pi/3}}$

$\displaystyle S_n = \frac{\sin\left(\frac{n\pi}{3}\right)}{\sqrt{3}} + \cos\left(\frac{n\pi}{3}\right)$