A type of Combinatorial equality：$\sum_{k=0}^{n}\binom{n}{k} \cos\frac{k}{2}\pi=2^{\frac{n}{2}}\cos\frac{n}{4}\pi.$ When computing the Taylor series of the function $f(z)=e^z\cos z,$
I use two methods:
On the one hand, using Cauchy product, 
\begin{align*}
e^z\cos z
&=\left(\sum_{n=0}^{\infty}\frac{z^n}{n!}\right)
\left(\sum_{n=0}^{\infty}\frac{\cos\frac{n}{2}\pi}{n!}z^n\right)\\
&=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{1}{(n-k)!}
\frac{\cos\frac{k}{2}\pi}{k!}\right)z^n\ (\text{Cauchy Product})\\[3pt]
&=\sum_{n=0}^{\infty}\frac{1}{n!}\left(\sum_{k=0}^{n}\binom{n}{k}\cos\frac{k}{2}\pi
\right)z^n,\ z\in\mathbb{C};
\end{align*}
On the other hand, 
\begin{align*}
e^z\cos z
&=e^z\cdot\frac{e^{i z}+e^{-i z}}{2}\\
&=\frac{e^{(1+i)z}+e^{(1-i)z}}{2}\\[3pt]
&=\frac{1}{2}\left(\sum_{n=0}^{\infty}\frac{(1+i)^n}{n!}z^n
+\sum_{n=0}^{\infty}\frac{(1-i)^n}{n!}z^n\right)\\
&=\frac{1}{2}\sum_{n=0}^{\infty}\frac{(1+i)^n+(1-i)^n}{n!}z^n\\
&=\frac{1}{2}\sum_{n=0}^{\infty}
\frac{2^{\frac{n}{2}}\left(e^{\frac{n}{4}\pi i}+e^{-\frac{n}{4}\pi i}\right)}{n!}z^n\\
&=\sum_{n=0}^{\infty}\left(\frac{2^{\frac{n}{2}}}{n!}\cos\frac{n}{4}\pi\right)z^n,\ z\in\mathbb{C}.
\end{align*}
So Compare the corresponding coefficients, we get the following Combinatorial equality:
$$\sum_{k=0}^{n}\binom{n}{k} \cos\frac{k}{2}\pi=2^{\frac{n}{2}}\cos\frac{n}{4}\pi.$$
What I want to konw: is there an elementary method or constructive method ( which is suitable for high school student!) to prove this Combinatorial equality?
Any help and hint will welcome!
 A: There is a fundamental way to prove this.
I used a simple binomial expansion and Euler's identity to solve this...
Here's the solution:
$$
\begin{aligned}
&\sum_{k=0}^{n}\left(\begin{array}{l}
n \\
k
\end{array}\right) \cos \frac{k \pi}{2}=?\\
&\text { Let } T_{k}=\left(\begin{array}{l}
n \\
k
\end{array}\right)\left\{\cos \left(\frac{k \pi}{2}\right)+i \sin \left(\frac{k \pi}{2}\right)\right\}\\
&=\left(\begin{array}{l}
n \\
k
\end{array}\right) e^{\frac{i k \pi}{2}} \quad[\text { Euler's identity }]
\end{aligned}
$$
$$
\begin{aligned}
\sum_{k=0}^{n} T_{k} &=\sum_{k=0}^{n}\left(\begin{array}{l}
n \\
k
\end{array}\right) e^{\frac{i k \pi}{2}} \\
&=\left(e^{i \pi / 2}+1\right)^{n} \quad[\text { Binomial expansion }] \\
&=(1+i)^{n} \\
&=2^{n / 2}\left(\frac{1}{\sqrt{2}}+\frac{i}{\sqrt{2}}\right)^{n} \\
&=2^{n / 2}\left(\cos \frac{\pi}{4}+i \sin \frac{\pi}{4}\right)^{n} \\
S_{k} &=2^{n / 2} e^{\frac{i n \pi}{4}}
\end{aligned}
$$
$$
\text { But, } \operatorname{Im}\left(T_{k}\right)=\left(\begin{array}{l}
n \\
k
\end{array}\right) \cos \frac{k \pi}{2}
$$
$$
\operatorname{Im}\left(S_{k}\right)=\sum_{k=0}^{n}\left(\begin{array}{l}
n \\
k
\end{array}\right) \cos \frac{k \pi}{2}=2^{n / 2} \cos \frac{n \pi}{4}
$$
A: Here are some more general results.  Let $\theta$ and $\phi$ be arbitrary complex numbers.  For any integer $n\geq 0$, we have $$\sum_{k=0}^n\,\binom{n}{k}\,\cos(\theta+k\phi)=2^n\,\cos^n\left(\frac{\phi}{2}\right)\,\cos\left(\theta+\frac{n\phi}{2}\right)\,;\tag{*}$$ $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\cos(\theta+k\phi)=\left\{\begin{array}{ll}(-1)^{\frac{n}{2}}2^n\,\sin^n\left(\frac{\phi}{2}\right)\,\cos\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is even}\,,\\ (-1)^{\frac{n-1}{2}}2^n\,\sin^n\left(\frac{\phi}{2}\right)\,\sin\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is odd}\,;\end{array}\right.\tag{#}$$
$$\sum_{k=0}^n\,\binom{n}{k}\,\sin(\theta+k\phi)=2^k\,\cos^k\left(\frac{\phi}{2}\right)\,\sin\left(\theta+\frac{k\phi}{2}\right)\,;\tag{$\star$}$$ and $$\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\sin(\theta+k\phi)=\left\{\begin{array}{ll} (-1)^{\frac{n}{2}}2^n\,\sin^n\left(\frac{\phi}{2}\right)\,\sin\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is even}\,,\\(-1)^{\frac{n+1}{2}}2^n\,\sin^n\left(\frac{\phi}{2}\right)\,\cos\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is odd}\,.\end{array}\right.\tag{\$}$$ A way to prove these identities is just as in P. Patil's answer.  Here is another way.
Consider the operator $\hat{\gamma}_\phi$ defined by
$$(\hat{\gamma}_\phi\,f)(\theta):=2\,\cos\left(\frac{\phi}{2}\right)\,f\left(\theta+\frac{\phi}{2}\right)$$
for all $f:\mathbb{C}\to\mathbb{C}$ and $\theta\in\mathbb{C}$.  Observe that
$$(\hat{\gamma}_\phi\,\cos)(\theta)=\cos\left(\theta\right)+\cos\left(\theta+\phi\right)$$
for all $\theta\in\mathbb{C}$.  By induction, we can easily see that
$$2^n\,\cos^n\left(\frac{\phi}{2}\right)\,\cos\left(\theta+\frac{n\phi}{2}\right)=(\hat{\gamma}_\phi^n\,\cos)(\theta)=\sum_{k=0}^n\,\binom{n}{k}\,\cos(\theta+k\phi)\,.$$
This proves (*).  Similarly, we can prove ($\star$) by observing that
$$(\hat{\gamma}_\phi\,\sin)(\theta)=\sin(\theta)+\sin(\theta+\phi)\,.$$
We can also take the derivative of (*) with respect to $\theta$ to get ($\star$).
For (#), if we replace $\phi$ by $\phi+\pi$ in (*), then the left-hand side becomes
$$\sum_{k=0}^n\,\binom{n}{k}\,\cos(\theta+k\phi+k\pi)=\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\cos(\theta+k\phi)\,.$$
The right-hand side is as given in (#) since $\cos\left(\dfrac{\phi+\pi}{2}\right)=-\sin\left(\dfrac{\phi}{2}\right)$ and
$$\cos\left(\theta+\frac{n\phi+n\pi}{2}\right)=\left\{\begin{array}{ll}(-1)^{\frac{n}{2}}\,\cos\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is even}\,,\\ (-1)^{\frac{n+1}{2}}\,\sin\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is odd}\,.\end{array}\right.$$
Likewise, if we replace $\phi$ by $\phi+\pi$ in ($\star$), the left-hand side becomes
$$\sum_{k=0}^n\,\binom{n}{k}\,\sin(\theta+k\phi+k\pi)=\sum_{k=0}^n\,(-1)^k\,\binom{n}{k}\,\sin(\theta+k\phi)\,.$$
The right-hand side is as given in (\$) since $\cos\left(\dfrac{\phi+\pi}{2}\right)=-\sin\left(\dfrac{\phi}{2}\right)$
and
$$\sin\left(\theta+\frac{n\phi+n\pi}{2}\right)=\left\{\begin{array}{ll}(-1)^{\frac{n}{2}}\,\sin\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is even}\,,\\ (-1)^{\frac{n-1}{2}}\,\cos\left(\theta+\frac{n\phi}{2}\right)&\text{if $n$ is odd}\,.\end{array}\right.$$
Alternatively, we can simply take the derivative of (#) with respect to $\theta$.
Another way to deal with (#) and (\$) is to define the operator $\hat{\sigma}_\phi$ as follows.  For $f:\mathbb{C}\to\mathbb{C}$, let
$$(\hat{\sigma}_\phi\,f)(\theta):=2\,\sin\left(\frac{\phi}{2}\right)\,f\left(\theta+\frac{\phi}{2}\right)$$
for all $\theta\in\mathbb{C}$.  Show that
$$(\hat{\sigma}_\phi\,\cos)(\theta)=-\sin(\theta)+\sin(\theta+\phi)$$
and
$$(\hat{\sigma}_\phi\,\sin)(\theta)=+\cos(\theta)-\cos(\theta+\phi)$$
for all $\theta\in\mathbb{C}$.  Then, perform induction to get (#) and (\$) (both identities should be proven within the same induction procedure).
