# Non-trivial alternating sums of binomial coefficients

Consider a binary vector $$a_0, a_1,\,\dots\,, a_n$$ and an equation

$$\sum_{i=0}^n a_i \cdot (-1)^i {n \choose i} = 0.$$

You can satisfy this trivially when

1) all $$a_i$$ are 0, or

2) all $$a_i$$ are 1, or

3) $$n$$ is odd and $$a$$ satisfies $$a_i = a_{n-i}$$ for all $$i$$, because the summands for $$i$$ and $$n-i$$ cancel out.

My question is if there are any other vectors $$a$$ satisfying the equation?

[There has been a related question but regarding $$a_i \in \{-1,1\}$$. There are non-trivial examples given in the answers but they do not seem to work in this setup. I have also asked this at math.stackexchange but then I read that this community if better suited for research-level questions.]

• I'm not sure I understand your last comment. If you have a solution with $a_i \in \{ -1, 1\}$, then you also have a solution with $a_i \in \{ 0, 1\}$ simply by replacing each $a_i$ with $(a_i + 1)/2$ (using the fact that setting all $a_i = 1$ is also a valid solution). Am I misunderstanding something? – Tom De Medts Dec 13 '19 at 13:39
• @Ira, the question asks for a binary vector, which I think means a vector whose entries are just zeros & ones. – Gerry Myerson Dec 13 '19 at 23:03
• @Gerry you're right—I deleted my comment. – Ira Gessel Dec 14 '19 at 5:41
• @TomDeMedts Yes, you are totally right. So my question trivially reduces to an already addressed one. I guess I cannot mark a comment as a solution, but I would if you only post it as an answer. – Michal Dec 15 '19 at 14:52
• The number of solutions for $n=1,2,3,\ldots,25$ is $$2,2,4,2,8,2,16,6,32,2,64,2,144,14,256,2,512,2,1024,6,2048,2,4096,50,8192.$$ As the OP notes, it is easy to construct $2$ solutions for $n$ even, and $2^k$ solutions for $n=2k-1$; but note that there are $16$ more for $n=13$. The four extra solutions for $n=8$ are obtained from $001001100$ (the identity ${8 \choose 2} - {8 \choose 5} + {8 \choose 6} = 0$ noted by LeechLattice) by reflection and 1's complement; the twelve for $n=14$ are the orbits of $000001001110000, 000001100110000, 000010000110000$. – Noam D. Elkies Dec 16 '19 at 5:50

(Reposting my comment as an answer, as requested by the OP.)

If you have a solution with $$a_i \in \{−1,1\}$$, then you also have a solution with $$a_i \in \{0,1\}$$ simply by replacing each $$a_i$$ with $$(a_i+1)/2$$ (using the fact that setting all $$a_i=1$$ is also a valid solution). In other words, your question had already been answered by some of the comments to this question.

$${8\choose{2}}-{8\choose{5}}+{8\choose{6}}=28-56+28=0$$, so there's a solution for $$n=8$$.

• More generally: if $k$ is odd, then $$\binom{3k - 1}{k-1} - \binom{3k-1}{k} + \binom{3k-1}{2k} = 0$$ the case $k = 1$ is a trivial case. This answer was $k = 2$. – Willie Wong Dec 13 '19 at 14:35
• The next $k$ with $k = 3$ has $3k-1 = 14$ and is related to the sum mentioned in this comment – Willie Wong Dec 13 '19 at 14:37

What you have is the $$n$$-th difference operator applied to the sequence $$(a_i)$$.

In particular, the value is 0 if $$a_i=f(i)$$ for any polynomial $$f$$ of degree less than $$n$$.

The converse is also true. If the sum is 0 it means that the $$n$$-th difference is 0, which means there is a polynomial $$f$$ of degree less than $$n$$ such that $$a_i=f(i)$$ for all $$i$$. This is therefore a complete characterisation.

The binomial coefficients $${n\choose k-1}, {n\choose k}$$, and $${n\choose k+1}$$ are in arithmetic progression if and only if $$n=m^2-2$$ and $$k=\frac 12(n-m)$$ or $$\frac 12(n+m)$$. For such $$n$$ and $$k$$ we have $${n\choose k-1}-{n\choose k}+{n\choose k+1}-{n\choose n-k}=0.$$

We may similarly wonder whether any partial sums in the trinomial expansion

$$(1+z+z^2)^n = \sum_{k=0}^{2n} {n \choose k}_{\!2}z^k$$

could be $$0$$ when $$z = e^{2i\pi/3}$$ cancels the whole. The answer is positive too :

$${5 \choose 2}_{\!2}z^2+{5 \choose 3}_{\!2}+{5 \choose 7}_{\!2}z+{5 \choose 8}_{\!2}z^2 = 15z^2+30+30z+15z^2 = 0$$

. $${11 \choose 0}_{\!2} + {11 \choose 4}_{\!2}z + {11 \choose 6}_{\!2} + {11 \choose 9}_{\!2} + {11 \choose 11}_{\!2}z^2 + \\{11 \choose 13}_{\!2}z + {11 \choose 16}_{\!2}z + {11 \choose 18}_{\!2} + {11 \choose 22}_{\!2}z =\\ 1+880z+4917+19855+25653z^2+19855z+4917z+880+z = 0$$

. $${13 \choose 1}_{\!2}z+{13 \choose 3}_{\!2}+{13 \choose 5}_{\!2}z^2+{13 \choose 8}_{\!2}z^2+{13 \choose 10}_{\!2}z+{13 \choose 12}_{\!2}+\\ {13 \choose 14}_{\!2}z^2+{13 \choose 16}_{\!2}z+{13 \choose 18}_{\!2}+{13 \choose 21}_{\!2}+{13 \choose 23}_{\!2}z^2+{13 \choose 25}_{\!2}z =\\ 13z + 442 + 5005z^2 + 52624z^2 + 129844z + 201643 + \\ 201643z^2 + 129844z + 52624 + 5005 + 442z^2 + 13z = 0$$