Divisibility of Sum of Equally Spaced Binomial Coefficients

Question

According to a numerical calculation I did for small values of $k$, it appears that the following is true.

$$4|\left[\sum_{j=1}^{n-1}\binom{3n}{3j}\right]$$ or $$\sum_{j=1}^{n-1}\binom{3n}{3j}=4p, p\in\mathbb{Z}$$

Ex.

If $n=2, \binom{6}{3}=20=4\cdot 5$

If $n=3, \binom{9}{3}+\binom{9}{6}=2\cdot 84=168=4\cdot 42$

If $n=4, \binom{12}{3}+\binom{12}{6}+\binom{12}{9}=2\cdot 220+924=1364=4\cdot341$

If $n=5, \binom{15}{3}+\binom{15}{6}+\binom{15}{9}+\binom{15}{12}=2\cdot 455+2\cdot 5005=10920=4\cdot 2730$

Is there a way to prove this? Using induction, as above I've shown the base case is true. Then if we assume that

$$S_m=\sum_{j=1}^{m-1}\binom{3m}{3j}=4q, q\in\mathbb{Z}$$

Then

$$S_{m+1}=\sum_{j=1}^{m}\binom{3m+3}{3j}=?$$

And I have no idea how to go forward. Perhaps its not true? Is there a counterexample?

Answer 1

Starting with the binomial theorem, $$(1+x)^{3m} = \sum_{k=0}^{3m} \binom{3m}{k} x^k,$$ we see that for the cube root of unity $\omega = e^{2\pi i/3}$, $$(1+x)^{3m} + (1+\omega x)^{3m} + (1+\omega^2 x)^{3m} = 3 \sum_{\substack{k=0 \\ k \equiv 0 \pmod{3}}}^{3m} \binom{3m}{k} x^k.$$ The terms where $k \not\equiv 0 \pmod{3}$ are sifted away, since $1 + \omega + \omega^2 = 0$. Now evaluate at $x=1$: $$2^{3m} + (1+\omega)^{3m} + (1+\omega^2)^{3m} = 3 \sum_{\substack{k=0 \\ k \equiv 0 \pmod{3}}}^{3m} \binom{3m}{k}.$$ Since $1+\omega = e^{\pi i/3}$ and $1+\omega^2 = e^{-\pi i/3}$ are 6-th roots of unity, it follows that $(1+\omega)^3 = (1+\omega^2)^3 = -1$.

The right-hand side is almost 3 times your sum $S_m$, but $S_m$ does not include the $k=0$ and $k=3m$ terms. Subtracting them away, we find $$S_m = \frac{2^{3m} + 2((-1)^m-3)}{3}.$$ For $m \geqslant 1$, the numerator is always divisible by 4, which explains the observed divisibility.

Answer 2

Let $$S=\sum_{j=1}^{n-1}\binom {3n}{3j}$$ Adding terms for $j=0$ and $j=n$ gives $$\begin{align} S+2 &=\sum_{j=0}^n \binom {3n}{3j}\\ &=\sum_{r=0}^{3n}\binom {3n}r-\left[\sum_{j=0}^{n-1}\binom {3n}{3j+1}+\binom {3n}{3j+2}\right]\\ &=2^{3n}+2\Re\left[\sum_{j=0}^{n-1}\binom {3n}{3j+1}e^{i2\pi/3}+\binom {3n}{3j+2}e^{i4\pi/3}\right]\\ &=8^n+2\Re\left[\sum_{j=0}^{n-1}\binom {3n}{3j+1}e^{i2\pi(3j+1)/3}+\binom {3n}{3j+2}e^{i2\pi(3j+2)/3}\right]\\ &=8^n+2\Re\left[\underbrace{\binom {3n}{3n}+\sum_{j=0}^{n-1}\sum_{k=1}^3\binom {3n}{3j+k}e^{i2\pi(3j+k)/3}}-\sum_{j=0}^{n}\binom {3n}{3j}\right]\\ &=8^n+2\Re\left[\qquad\ \ \quad\overbrace{\sum_{r=0}^{3n}\binom {3n}r e^{i2\pi r/3}}\qquad \qquad -\left(S+2\right)\right]\\ &=8^n+2\Re\big[\big(1+e^{i2\pi /3}\big)^{3n}-\left(S+2\right)\big]\\ &=8^n+2\Re\big[\big(e^{i\pi /3}\big)^{3n}\big]-2\big(S+2\big)\\ &=8^n+2\Re \big[e^{i\pi n}\big]-2\big(S+2\big)\\ &=8^n+2(-1)^n-2\big(S+2\big)\\ 3\big(S+2\big) &=2(-1)^n+8^n\\ 3S&=2(-1)^n+8^n-6\\ &\equiv 2(-1)^n+0+2\mod 4\\ &\equiv 2\pm 2\mod 4\\ &\equiv 0\mod 4\\ S=\sum_{j=1}^{n-1}\binom {3n}{3j}&\equiv 0\mod 4\\ \Longrightarrow 4\bigg|&\sum_{j=1}^{n-1}\binom {3n}{3j}\; \blacksquare\end{align}$$

Answer 3

I know this is an old question but I wanted to add my two cents. What you wronte has a closed for. $\sum_{3j=0}^n\binom{n}{3j} = \frac{2^n+m}{3}$ where m = 2, 1, −1, −2, −1, 1, when n is congruent to 0, 1, 2, 3, 4, 5 (mod 6). according to https://math.hmc.edu/benjamin/wp-content/uploads/sites/5/2019/06/Sums-of-Evenly-Spaced-Binomial-Coefficients.pdf That said, let us write your special case $\sum_{j=1}^{n-1} \binom{3n}{3j} = -2 + \sum_{j=1}^{n-1} \binom{3n}{3j}$ Obvoiusly $3n\equiv 0,or 3 mod{6}$. Then m = 2 or -2. Therefore $\sum_{j=1}^{n-1} \binom{3n}{3j} = -2 +\frac{2^{3n}\pm2}{3} = \frac{2^{3n}\pm2-6}{3} = \frac{2^{3n}-4}{3} or \frac{2^{3n}-8}{3}$ Since $gcd(3,4)=1$ and $4|2^{3n}-4$ and $4|2^{3n}-8$ Then $4|\sum_{j=1}^{n-1} \binom{3n}{3j} |$ . This gives us even a stronger version of your conclusion

$4|\sum_{j=1}^{n-1} \binom{3n}{3j}$ if n is even and $8|\sum_{j=1}^{n-1} \binom{n}{3j}$ if n is odd I hope this helped