$\binom{28}{2}+\binom{28}{5}+\binom{28}{8}+\cdots+\binom{28}{26}=\frac{2}{3}(2^{27}+1)$

Question

I need to prove the following identity $$ \binom{28}{2}+\binom{28}{5}+\binom{28}{8}+\cdots+\binom{28}{26} = \frac{2}{3}(2^{27}+1). $$

I have tried to use the fact that $\binom{m}{n}=\binom{m}{m-n}$ but it doesn't help.

Answer 1

Hint. Let $w=\exp(2\pi i/3)$. Then $w^3=1$ and $1+w+w^2=0$, and hence $$ (1+1)^{28}+w(1+w)^{28}+w^2(1+w^2)^{28}=3 \left(\binom{28}{2}+\binom{28}{5}+\cdots+\binom{28}{26}\right), $$ since the sum above is a real number.

Next $$ 1+w=-w^2\quad\Rightarrow\quad(1+w)^{28}=w^{54}=w^2\\ 1+w^2=-w\quad\Rightarrow\quad(1+w^2)^{28}=w^{28}=w $$ Finally $$ (1+1)^{28}+w(1+w)^{28}+w^2(1+w^2)^{28}=2^{28}+2. $$

Answer 2

Another solution(just for fun)

Let $F_j(x)= \sum_{x \in 0..n}\binom{n}{x} | x \mod 3 = j$

$F_0(x) + F_1(x) +F_2(x) =2^x$

$F_j(x)=F_j(x-1) + F_{(j-1) \mod 3}(x-1)$

Self-cast previous equation

$F_j(x) = F_j(x-2) + 2*F_{(j-1) \mod 3}(x-2) + F_{(j-2) \mod 3}(x-2)$ = $2^{x-2} + F_{(j-1) \mod 3}(x-2)$

Another self-cast

$F_j(x) = 2^{x-2} + 2^{x-4} + 2^{x-6} + F_j(x-6)$

So, $F_2(28) = 2^{26} + 2^{24} + ... + 2^4 + F_2(4)$ = $2^{26} + 2^{24} + ... + 2^2 + F_1(2) = 2^{26} + 2^{24} + ... + 2^2 + \binom{2}{1} $ = $2 + 4\sum_{i\in 0..12}4^i = 2 +4\frac{4^{13}-1}{3} = \frac{4^{14} - 4 + 6}{3}$ = $\frac{2^{28} +2}{3}$

Answer 3

I want to give an alternative presentation of the solution by Yiorgos S. Smyrlis to make it look a little less like magic. Hopefully it will give a context that will make solving similar problems easy.

Let $\omega$ such that $\omega^n=1$. Then $1+\omega+\ldots+\omega^{n-1}=0$, unless $\omega=1$, in which case it equals $n$. In particular, if $\omega$ is a primitive $n$th root of unity, and we define $\alpha_n(k)=1+\omega^k+\omega^{2k}+\ldots+\omega^{(n-1)k}$, then $\alpha_n(k)=0$ unless $n|k$, in which case it is equal to $n$.

Next, let $a_0, a_1, a_2, \ldots$ be some sequence, and let $f(x)=\sum a_i x^i$ (which we will assume converges in some circle of radius bigger than 1, which happens, for example, when the sequence is a finite sequence).

Now, let us look at $f(1)+f(\omega)+f(\omega^2)+\ldots+f(\omega^{n-1})$. Writing it out as a big sum and grouping together all the terms with coefficient $a_i$ together${}^{\dagger}$, we can rewrite this as

$$\sum a_i \alpha_n(i)=n\sum_{n|i}a_i$$.

Now, let us apply this to your specific problem.

By the binomial theorem, $(1+x)^{28}=\sum \binom{28}{i}x^i$, and we would like to extract out the terms where $i$ is congruent to $2\mod 3$ and take their sum. However, from what we developed above, we can only extract out the terms whose index are multiples of 3. However, we can fix this by shifting everything over by $1$. If instead of $(1+x)^{28}$ we look at $x(1+x)^{28}$, the coefficient of $x^{3i}$ is now $\binom{28}{3i-1}$. Thus, if we let $\omega=e^{2\pi i/3}$, the sum we want is equal to

$$\frac{1}{3}\left(1(1+1)^{28}+\omega(1+\omega)^{28}+\omega^2(1+\omega^2)^{28}\right).$$

The rest of Yiorgos S. Smyrlis's answer shows how to further simplify this sum.

${}^{\dagger}$ Note that to rearrange the terms in the sum like this, we need that everything is absolutely convergent, which we get from our assumption that $f(x)$ converged on a circle with radius bigger than $1$.