Prove $\sum_{k=0}^n\binom{n}{k}\cos\left(\frac{k\pi}{2} - \frac{n\pi}{4}\right) = \sqrt{2^n}$

Question

While working on a separate problem, I stumbled upon a beautiful fact that I simply couldn't prove.. I suspect it requires some tools/tactics I've not encountered yet. The statement is the following: $$\sum_{k=0}^n\binom{n}{k}\cos\left(\frac{k\pi}{2} - \frac{n\pi}{4}\right) = \sqrt{2^n}$$

From my humble experience, I've got two suspicions for a successful approach:

• Complex number manipulation and working with the real part;
• Some kind of Fourier transform... this really just reminds me of it.

I couldn't come up with anything nice using complex numbers and I'm not that familiar with Fourier transforms yet, so I don't have the right intuition there.

Furthermore, this sum is just begging to employ Newton's binomial at some point, but I couldn't transform it to a form where it is applicable.

Any advice is welcome! Thanks in advance!

P. S. I don't opt for induction proofs, I'm rather interested in evaluating the sum on the LHS and arriving at the RHS.

Answer 1

You first idea is correct.

$$\begin{align} \sum_{k=0}^n\binom nk\cos\left(\frac{k\pi}2-\frac{n\pi}4\right)&= \sum_{k=0}^n\binom nk \Re\left(\exp\left(\frac{k\pi i}2-\frac{n\pi i}4\right)\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\sum_{k=0}^n\binom nk \left(e^{\pi i/2}\right)^k\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\sum_{k=0}^n\binom nk i^k\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)(1+i)^n\right)\\ &=\Re\left(\left(e^{-n\pi i/4}\right)\left(\sqrt2e^{\pi i/4}\right)^n\right)\\ &=\sqrt{2^n} \end{align}$$

Answer 2

This answer adapted from the AoPS link in comments $$\sum_{k=0}^n\binom nk\cos(k\pi/2-n\pi/4)$$ $$=\operatorname{Re}\left(\sum_{k=0}^n\binom nk(\cos(k\pi/2-n\pi/4)+i\sin(k\pi/2-n\pi/4))\right)$$ $$=\operatorname{Re}\left(\sum_{k=0}^n\binom nke^{i(k\pi/2-n\pi/4)}\right)$$ $$=\operatorname{Re}\left(e^{-in\pi/4}\sum_{k=0}^n\binom nk i^k\right)$$ $$=\operatorname{Re}\left(\left(\frac{\sqrt2}2(1+i)\right)^{-n}(1+i)^n\right)$$ $$=\left(\frac{\sqrt2}2\right)^{-n}=2^{n/2}$$