# Putting ${n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ in a closed form

As the title says, I'm trying to transform $\displaystyle{n \choose 0} + {n \choose 5} + {n \choose 10} + \cdots + {n \choose 5k} + \cdots$ into a closed form. My work:

$\displaystyle\left(1 + \exp\frac{2i\pi}{5} \right )^n = \displaystyle\sum_{p=0}^{n}\binom{n}{p}\exp\left(\frac{p\cdot2i\pi}{5} \right)$

$\displaystyle=\binom{n}{0} + \binom{n}{1}\exp\left(\frac{1\cdot2i\pi}{5} \right) + \binom{n}{2}\exp\left(\frac{2\cdot2i\pi}{5} \right) + \binom{n}{3}\exp\left(\frac{3\cdot2i\pi}{5} \right) + \binom{n}{4}\exp\left(\frac{4\cdot2i\pi}{5} \right) + \binom{n}{5} + \cdots = \left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] + \exp\left(\frac{2i\pi}{5} \right)\left[\binom{n}{1} + \binom{n}{6} + \binom{n}{11} \right ] + \exp\left(\frac{4i\pi}{5} \right)\left[\binom{n}{2} + \binom{n}{7} + \binom{n}{12} \right ] + \exp\left(\frac{6i\pi}{5} \right)\left[\binom{n}{3} + \binom{n}{8} + \binom{n}{13} \right ] + \exp\left(\frac{8i\pi}{5} \right)\left[\binom{n}{4} + \binom{n}{9} + \binom{n}{14} \right ] + \cdots$

I'll recall $\left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] = k$, $\left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] = u$, $\left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] = v$, $\left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] = w$ and $\left[\binom{n}{0} + \binom{n}{5} + \binom{n}{10} + \cdots\right ] = z$. Thus

$\displaystyle\left(1 + \exp\frac{2i\pi}{5} \right )^n = k + u\cdot\exp\frac{2i\pi}{5} + v\cdot\exp\frac{4i\pi}{5} + w\cdot \exp\frac{6i\pi}{5} + z\cdot\exp\frac{8i\pi}{5} = k + u\cdot\left (\cos\frac{2\pi}{5} + i\cdot\sin\frac{2\pi}{5} \right ) + v\cdot\left (\cos\frac{4\pi}{5} + i.\sin\frac{4\pi}{5} \right ) + w\cdot\left (\cos\frac{6\pi}{5} + i.\sin\frac{6\pi}{5} \right ) + z\cdot\left (\cos\frac{8\pi}{5} + i.\sin\frac{8\pi}{5} \right )$

Noting that $\cos\frac{2\pi}{5} = \cos\frac{8\pi}{5}$, $\cos\frac{4\pi}{5} = \cos\frac{6\pi}{5}$, $\sin\frac{2\pi}{5} = -\sin\frac{8\pi}{5}$ and $\sin\frac{4\pi}{5} = -\sin\frac{6\pi}{5}$:

$\displaystyle\left(1 + \exp\frac{2i\pi}{5} \right )^n = k + \left(u + z\right)\cos\frac{2\pi}{5} + i\cdot\left(u - z \right)\sin\frac{2\pi}{5} + \left(v + w\right)\cos\frac{4\pi}{5} + i\cdot\left(v - w \right)\sin\frac{4\pi}{5} = \left(k + \left(u + z\right)\cos\frac{2\pi}{5} + \left(v + w\right)\cos\frac{4\pi}{5}\right) + i\cdot\left(\left(u - z \right)\sin\frac{2\pi}{5} + \cdot\left(v - w \right)\sin\frac{4\pi}{5} \right)$

But $\displaystyle\left(1 + \exp\frac{2i\pi}{5} \right )^n = \left(2\cos\left(\frac{\pi}{5} \right)\cdot\exp\left(\frac{i\pi}{5}\right)\right)^n = \left(2^n\cos^n\left(\frac{\pi}{5} \right)\cdot\exp\left(\frac{ni\pi}{5}\right)\right) = \left(2^n\cos^n\frac{\pi}{5} \right)\left(\exp\left(\frac{ni\pi}{5}\right)\right) = \left(2^n\cos^n\frac{\pi}{5} \right)\left(\cos\frac{n\pi}{5} + i.\sin\frac{n\pi}{5} \right ) = \left(2^n\cos^n\frac{\pi}{5}\cos\frac{n\pi}{5} \right) + i\cdot \left(2^n\cos^n\frac{\pi}{5}\sin\frac{n\pi}{5} \right)$

So,

$\displaystyle k + \left(u + z\right)\cos\frac{2\pi}{5} + \left(v + w\right)\cos\frac{4\pi}{5} = 2^n\cos^n\frac{\pi}{5}\cos\frac{n\pi}{5}$

and

$\displaystyle\left(u - z \right)\sin\frac{2\pi}{5} + \left(v - w \right)\sin\frac{4\pi}{5} = 2^n\cos^n\frac{\pi}{5}\sin\frac{n\pi}{5}$

and I'm stuck here. I noted that $k + u + v + w + z = 2^n$ but I couldn't isolate $k$. So, any help finishing this result will be fully appreciated. Thanks.

-
–  Grigory M Sep 19 '12 at 18:18
add comment

## 3 Answers

Hint: with $\omega=\exp(2\pi i /5)$ a primitive $5$th root of unity, we have

$$\sum_{r=0}^4 \omega^{rk}=\begin{cases}5 & k\equiv 0 \bmod 5 \\ 0 & k\not\equiv 0\bmod 5.\end{cases}$$

So then what is

$$(1+\omega^0)^n+(1+\omega^1)^n+(1+\omega^2)^n+(1+\omega^3)^n+(1+\omega^4)^n~?$$

(Combine the binomial expansions...)

-
–  anon Jun 10 '12 at 19:28
And somewhat related: math.stackexchange.com/questions/134075/… –  anon Jun 10 '12 at 19:34
add comment

$$\sum_{k\geqslant0}{n\choose \color{red}{\mathbf 5}k}=\frac1{\color{red}{\mathbf 5}}\cdot\sum_{\ell=1}^{\color{red}{\mathbf 5}}\left(1+\mathrm e^{2\mathrm i\pi\ell/\color{red}{\mathbf 5}}\right)^n=\frac1{\color{red}{\mathbf 5}}\cdot\sum_{\zeta\in\mathbb C\,:\,\zeta^\color{red}{\mathbf 5}=1}\left(1+\zeta\right)^n$$

-
add comment

As you know, $\sum_{j=0}^n {n \choose j} = 2^n$, and if $\omega$ is a primitive $5$'th root of unity $\sum_{j=0}^n {n \choose j} \omega^j = (1 + \omega)^n$. Now $\sum_{i=0}^4 \omega^{ij} = 5$ if $j$ is divisible by $5$ and $0$ otherwise. So $$\sum_{k} {n \choose {5k}} = \frac{1}{5} \sum_{i=0}^4 \sum_{j=0}^n {n \choose j} \omega^{ij} = \frac{1}{5} \sum_{i=0}^4 (1+\omega^i)^n$$

-
add comment