Bounds for $S_k = \sum_{i=1}^k {3k \choose 3i}$

Question

Consider:

$$S_k = \sum_{i=0}^k {3k \choose 3i}.$$

Is it true that for all sufficiently large values of $k$, $S_k(1/2)^{3k} < 1/2$?

In general, for:

$$S_{c,k} {ck \choose ci} = \sum_{i=0}^k,$$

for integer $c > 1$.

Is it true that for all sufficiently large values of $k$, $S_{c,k}(1/2)^{ck} < 1/(c-1)$?

Answer 1

$$ \begin{align} \sum_{j=0}^k\binom{3k}{3j} &=\frac13\left(\sum_{j=0}^{3k}\binom{3k}{j}+\sum_{j=0}^{3k}\binom{3k}{j}e^{2\pi ij/3}+\sum_{j=0}^{3k}\binom{3k}{j}e^{-2\pi ij/3}\right)\\ &=\frac13\left(2^{3k}+\left(\frac12+i\frac{\sqrt3}2\right)^{3k}+\left(\frac12-i\frac{\sqrt3}2\right)^{3k}\right)\\[3pt] &=\frac13\left(2^{3k}+2(-1)^k\right) \end{align} $$

---

If $c\nmid j$, then $e^{2\pi ij/c}\ne1$. Therefore, by the formula for the sum of a geometric series, $$ \begin{align} \frac1c\sum_{d=0}^{c-1}e^{2\pi ijd/c} &=\frac1c\frac{\overbrace{e^{2\pi ijc/c}}^1-1}{\underbrace{\ e^{2\pi ij/c}\ }_{\text{not }1}-1}\\ &=0 \end{align} $$ If $c\mid j$, then $e^{2\pi ijd/c}=1$. Therefore, $$ \begin{align} \frac1c\sum_{d=0}^{c-1}e^{2\pi ijd/c} &=\frac1c\sum_{d=0}^{c-1}1\\[6pt] &=1 \end{align} $$ Thus, using Iverson brackets, $$ \frac1c\sum_{d=0}^{c-1}e^{2\pi ijd/c}=[\,c\mid j\,] $$ Applying this, $$ \begin{align} \sum_{j=0}^k\binom{ck}{cj} &=\sum_{j=0}^{ck}\binom{ck}{j}[\,c\mid j\,]\\ &=\frac1c\sum_{d=0}^{c-1}\sum_{j=0}^{ck}\binom{ck}{j}e^{2\pi ijd/c}\\ &=\frac1c\sum_{d=0}^{c-1}\left(1+e^{2\pi id/c}\right)^{ck}\\ &=\frac1c\sum_{d=0}^{c-1}\color{#C00}{e^{\pi idk}}\color{#090}{\left(e^{\pi id/c}+e^{-\pi id/c}\right)^{ck}}\\ &=\frac1c\color{#090}{2^{ck}}\left(1+\sum_{d=1}^{c-1}\color{#C00}{(-1)^{dk}}\color{#090}{\cos^{ck}(\pi d/c)}\right)\\ \end{align} $$ Note that $\cos^{ck}(\pi d/c)\to0$ as $k\to\infty$

Answer 2

There actually is a closed form for this sum.

Let $\lambda \in \mathbb{C}$. By the binomial formula we know that

$$\sum_{i=0}^{3k} \binom{3k}{i} \cdot \lambda^i = (1+\lambda)^{3k}.$$

We can view this in terms of linear algebra: let

$$\begin{align*} u & = \left[ \binom{3k}{0}, \binom{3k}{1}, \binom{3k}{2}, \ldots, \binom{3k}{3k} \right] \\[1ex] v & = [1, \lambda, \lambda^2, \ldots, \lambda^{3k}] \end{align*}$$

so that $u, v \in \mathbb{R}^{3k+1}$ and $\left< u, v \right> = (1+\lambda)^{3k}$. Now let $\omega = \cos \frac{2 \pi}{3} + i \sin \frac{2 \pi}{3}$ be the $3$rd root of unity and substitute $\alpha = 1, \ \omega, \ \omega^2$ in the definition of $v$ to get $v_0, v_1, v_2$ respectively. Now consider

$$w = [1, 0, 0, 1, 0, 0, 1, \ldots, 1] \in \mathbb{R}^{3k+1}.$$

Then our sum can expressed as

$$\sum_{i=0}^k \binom{3k}{3i} = \left< u, w \right>$$

but it's easy to see that $w \in \operatorname{span} \{ v_0, v_1, v_2 \}$, hence there are $\alpha_0, \alpha_1, \alpha_2 \in \mathbb{C}$ such that

$$w = \alpha_0 v_0 + \alpha_1 v_1 + \alpha_2 v_2.$$

Then

$$\left< u, w \right> = \alpha_0 \left< u, v_0 \right> + \alpha_1 \left< u, v_1 \right> + \alpha_2 \left< u, v_2 \right> = \alpha_0 2^{3k} + \alpha_1 (1+\omega)^{3k} + \alpha_2 (1+\omega^2)^{3k}.$$

This easily generalizes to finding the sum $\displaystyle \sum_{i=0}^k \binom{ck}{ci}$ for any positive integer $c$, namely

$$\sum_{i=0}^k \binom{ck}{ci} = \sum_{j=0}^{c-1} \alpha_j \cdot (1+\omega^j)^{3k}$$

where $\omega = \cos \frac{2 \pi}{c} + i \sin \frac{2 \pi}{c}$ and the coeffiecients $\alpha_j$ are found by solving an analogous system of equations.

I don't know if this helps finding real lower bounds on the sum though.