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

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)$?

• uhm, $S_k\geq \binom{3k}{3k}=1$, no? Perhaps you meant to divide by $2^{3k}$? – Wojowu Sep 25 '17 at 9:59
• @Wojowu Typo fixed. Thanks. – user66307 Sep 25 '17 at 10:00
• I'm pretty sure the $(1/2)^{3k}$ should be on the other hand of the inequaluty. – Wojowu Sep 25 '17 at 10:01
• @Wojowu Argh! Thanks. – user66307 Sep 25 '17 at 10:02
• Your summation should start with $i=0$ (not $i=1$). – drhab Sep 25 '17 at 10:12

\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$

• +1 The question has been edited and the summation now starts with $i=0$. – drhab Sep 25 '17 at 10:14
• @drhab: then I can delete the last formula :-) – robjohn Sep 25 '17 at 10:17
• Does this sum generalize to $\frac1c (2^{ck}+2(-1)^k)$ ? – user66307 Sep 25 '17 at 10:23
• @Lembik: no, asymptotically, it will tend to $\frac1c2^{ck}$, I am working on an addition to my answer. – robjohn Sep 25 '17 at 10:25
• @Lembik: Yes, since $\cos^{ck}(\pi d/c)\to0$ as $k\to\infty$. – robjohn Sep 25 '17 at 12:25

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.

• Thank you that's interesting. The question evolved a little (sorry) but your answer is interesting nonetheless. – user66307 Sep 25 '17 at 10:11