Proving one of the Binomial Identities The binomial identity is
$$\sum^{\left \lfloor{n/3}\right \rfloor }_{k=-\left \lfloor{n/3}\right \rfloor} (-1)^k \binom{2n}{n+3k} = 2  \cdot 3^{n-1} $$
and this is valid for all positive integers $n$. What would be some proofs to show that this identity is true?
 A: This can be proved by induction on $n$. Instead of writing it up as efficiently as possible, I’ll show you how I got there.
First note that there’s no need to specify limits on the index $k$: the sum is taken over all $k$ for which the binomial coefficient is non-zero, with the usual convention that $\binom{n}k=0$ if $k>n$ or $k<0$. With the induction hypothesis
$$\sum_k(-1)^k\binom{2n}{n+3k}=2\cdot3^{n-1}\;,\tag{1}$$
the natural approach to the induction step looks like this:
$$\begin{align*}
\sum_k(-1)^k\binom{2n+2}{n+1+3k}&=\sum_k(-1)^k\left(\binom{2n}{n-1+3k}+2\binom{2n}{n+3k}+\binom{2n}{n+1+3k}\right)\\
&=4\cdot3^{n-1}+\sum_k(-1)^k\binom{2n}{n-1+3k}+\sum_k(-1)^k\binom{2n}{n+1+3k}\\
&=4\cdot3^{n-1}+\sum_k(-1)^k\binom{2n}{n+1-3k}+\sum_k(-1)^k\binom{2n}{n+1+3k}\\
&=4\cdot3^{n-1}+2\sum_k(-1)^k\binom{2n}{n+1+3k}\;,
\end{align*}$$
and we’d like to know that
$$\sum_k(-1)^k\binom{2n}{n+1+3k}=3^{n-1}\;.\tag{2}$$
Fine: we can try proving both identities by induction simultaneously. In that case $(2)$ is also part of our induction hypothesis, alongside $(1)$, so we can finish off the calculation with
$$4\cdot3^{n-1}+2\sum_k(-1)^k\binom{2n}{n+1+3k}=4\cdot3^{n-1}+2\cdot3^{n-1}=2\cdot3^n\;,$$
as desired, and the rest of our induction step looks like this:
$$\begin{align*}
\sum_k(-1)^k\binom{2n+2}{n+2+3k}&=\sum_k(-1)^k\left(\binom{2n}{n+3k}+2\binom{2n}{n+1+3k}+\binom{2n}{n+2+3k}\right)\\
&=2\cdot3^{n-1}+2\cdot 3^{n-1}+\sum_k(-1)^k\binom{2n}{n+2+3k}\\
&=4\cdot3^{n-1}+\sum_k(-1)^k\binom{2n}{n+2+3k}\\
&=4\cdot3^{n-1}-\sum_k(-1)^k\binom{2n}{n-1+3k}\\
&=4\cdot3^{n-1}-\sum_k(-1)^k\binom{2n}{n+1-3k}\\
&=4\cdot3^{n-1}-\sum_k(-1)^k\binom{2n}{n+1+3k}\\
&=4\cdot3^{n-1}-3^{n-1}\\
&=3^n\;,
\end{align*}$$
again as desired.
This is yet another induction in which it seems to be easier to prove a stronger result.
A: Suppose we seek to prove that
$$\sum_{k=-\lfloor n/3\rfloor}^{\lfloor n/3\rfloor} (-1)^k {2n\choose n+3k}
= 2\times 3^{n-1}.$$
We start by introducing the integral
$${2n\choose n+3k} = {2n\choose n-3k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n-3k+1}} (1+z)^{2n}
\; dz.$$
Observe  that this  vanishes for  $3k\gt  n$ (pole  canceled) and  for
$3k\lt -n$ (upper range of polynomial  term exceeded) so we may extend
the summation to $[-n, n]$ getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n+1}} (1+z)^{2n}
\sum_{k=-n}^{n} (-1)^k z^{3k}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n+1}} (1+z)^{2n} (-1)^n z^{-3n}
\sum_{k=0}^{2n} (-1)^k z^{3k}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{4n+1}} (1+z)^{2n} (-1)^n 
\frac{1-(-1)^{2n+1} z^{3(2n+1)}}{1+z^3}
\; dz
.$$
Only the first  piece from the difference due to  the geometric series
contributes and we get
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{4n+1}} (1+z)^{2n} (-1)^n
\frac{1}{1+z^3}
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{4n+1}} (1+z)^{2n-1} (-1)^n
\frac{1}{1-z+z^2}
\; dz
.$$
We have two poles other than zero and infinity at $\rho$ and $1/\rho$ where
$$\rho = \frac{1+\sqrt{3}i}{2}$$
and using the fact that residues sum to zero we obtain
$$S + \frac{(-1)^n}{\rho(1+\rho)} \frac{1}{\rho-1/\rho}
\left(\frac{(1+\rho)^2}{\rho^4}\right)^n
+ \frac{(-1)^n}{1/\rho(1+1/\rho)} \frac{1}{1/\rho-\rho}
\left(\frac{(1+1/\rho)^2}{1/\rho^4}\right)^n
\\ + \mathrm{Res}_{z=\infty} \frac{1}{z^{4n+1}} (1+z)^{2n-1} (-1)^n
\frac{1}{1-z+z^2} = 0.$$
We get for the residue at infinity
$$-\mathrm{Res}_{z=0} \frac{1}{z^2}
z^{4n+1} (1+1/z)^{2n-1} (-1)^n \frac{1}{1-1/z+1/z^2} 
\\= -\mathrm{Res}_{z=0} 
z^{2n+2} (1+z)^{2n-1} (-1)^n \frac{1}{z^2-z+1} = 0.$$
Now if $z^2 = z-1$ then $z^4 = z^2-2z+1 = -z$ and thus
$$\frac{(1+1/\rho)^2}{1/\rho^4} = \frac{(1+\rho)^2}{\rho^4} 
= \frac{\rho-1+2\rho+1}{-\rho} = -3$$
and furthermore with $z(1+z)(z-1/z) = (1+z)(z^2-1)$ and
$(1+z)(z-2) = z^2-z-2 = -3$ we finally get
$$S + (-1)^n \times \left(-\frac{1}{3}\right) (-3)^n 
+ (-1)^n \times \left(-\frac{1}{3}\right) (-3)^n = 0$$
or 
$$\bbox[5px,border:2px solid #00A000]{S = 2\times 3^{n-1}.}$$
