Tricky binomial coefficients problem

Question

Let $k$ be a positive integer and let $n = 6k - 1$. Let

$$S(n)=\sum_{j=1}^{2k-1} (-1)^{j+1} {{n}\choose{3j-1}}$$

How do you prove that $S(n)$ is never zero?

Answer 1

The sequence $0,0,1,0,0,-1,0,0,1,0,0,-1,\ldots$ that your coefficients of $\binom nk$ got through for $k=0,1,2,\ldots$ is periodic of period $6$, so it is a linear combination of the geometric sequences with ratios the $6$-th roots of unity. Specifically if $z_l=\exp(l\pi\mathbf i/3)$ for $l=1,\ldots,5$, the general term of your sequence is $$ c_k=\frac13(z_4.z_1^k+(-1)^k+z_2.z_5^k) $$ This allows you to write $$ \sum_{j=1}^{2k-1} (-1)^{j+1} \binom n{3j-1} =\sum_{k=0}^nc_k\binom nk =\frac13\bigl(z_4(1+z_1)^n+(1-1)^n+z_2(1+z_5)^n\bigr), $$ where the middle term is $0$ (since $n>0$) and the other terms are complex conjugates. To see that the result is never zero is a question of checking that the argument of $1+z_1$ is not a rational multiple of$~\pi$, so the outer terms never become purely imaginary.

Answer 2

By way of enrichment here is another algebraic proof using basic complex variables.

Suppose we first compute $$Q(k) = \sum_{q=1}^{2k} (-1)^{q+1} {6k-1\choose 3q-1}.$$

Introduce the integral representation $${6k-1 \choose 6k-3q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{6k-1}}{z^{6k-3q+1}} \; dz.$$

We use this to obtain an integral for the sum. Note that when $q>2k$ the integral becomes zero and for $q=0$ is zero as well. Therefore we may extend the sum from $q$ being zero to infinity to obtain

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{6k-1}}{z^{6k+1}} \sum_{q\ge 0} (-1)^{q+1} z^{3q} \; dz \\ = - \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{6k-1}}{z^{6k+1}} \frac{1}{1+z^3} \; dz.$$

Introduce the roots where $p=0,1,2$ $$\rho_p = \exp(\pi i/3 + 2\pi i p/3)$$

Using partial fractions by the Cauchy Residue Theorem on simple poles we thus obtain $$\frac{1}{1+z^3} = \sum_\rho \frac{1}{z-\rho} \times \mathrm{Res}_{z=\rho} \frac{1}{1+z^3} \\= \sum_\rho \frac{1}{z-\rho} \frac{1}{3\rho^2} = \sum_\rho \frac{1}{z-\rho} \frac{\rho}{3\rho^3} = -\frac{1}{3} \sum_\rho \frac{\rho}{z-\rho}.$$

Substituting this into the integral we have $$ \frac{1}{3} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{6k-1}}{z^{6k+1}} \sum_\rho \frac{\rho}{z-\rho} \; dz \\ = - \frac{1}{3} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{6k-1}}{z^{6k+1}} \sum_\rho \frac{1}{1-z/\rho}\; dz.$$

The integral is prepared for coefficient extraction which gives (use $\rho^6 = 1$) $$-\frac{1}{3} \sum_\rho \sum_{q=0}^{6k-1} {6k-1\choose q} \rho^{-(6k-q)} \\ = -\frac{1}{3} \sum_\rho \rho^{-6k} \sum_{q=0}^{6k-1} {6k-1\choose q} \rho^q = -\frac{1}{3} \sum_\rho \rho^{-6k} (1+\rho)^{6k-1} \\ = -\frac{1}{3} \sum_\rho (1+\rho)^{6k-1}.$$

The term for $\rho_0 = -1$ is zero and we are left with $$-\frac{1}{3} \left((1+\rho_1)^{6k-1} + (1+\rho_2)^{6k-1}\right).$$

Note that $$|1+\rho_{1,2}| = \sqrt{(3/2)^2 + (\sqrt{3}/2)^2} = \sqrt{3} \quad\text{and}\quad \arg(1+\rho_{1,2}) = \pm\frac{\pi}{6}.$$

This finally yields the value $$-\frac{1}{3} \sqrt{3}^{6k-1} \left(\exp(i\pi/6\times(6k-1)) + \exp(-i\pi/6\times(6k-1)) \right) \\ = -\frac{1}{3} (-1)^k \frac{27^k}{\sqrt{3}} \times 2 \cos(\pi/6) = -\frac{1}{3} (-1)^k \times 27^k.$$

The question asked to show that $$Q(k) - (-1)^{2k+1}{6k-1\choose 6k-1} = -\frac{1}{3} (-1)^k \times 27^k + 1$$ is never zero. This follows by inspection at this point with the first term having modulus at least nine and the second one being one.

Apparently this method is due to Egorychev.