3
$\begingroup$

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.]

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Tom De Medts Dec 13 '19 at 13:39
  • 1
    $\begingroup$ @Ira, the question asks for a binary vector, which I think means a vector whose entries are just zeros & ones. $\endgroup$ – Gerry Myerson Dec 13 '19 at 23:03
  • 1
    $\begingroup$ @Gerry you're right—I deleted my comment. $\endgroup$ – Ira Gessel Dec 14 '19 at 5:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Michal Dec 15 '19 at 14:52
  • 6
    $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Dec 16 '19 at 5:50
1
$\begingroup$

(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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Willie Wong Dec 13 '19 at 14:35
  • $\begingroup$ The next $k$ with $k = 3$ has $3k-1 = 14$ and is related to the sum mentioned in this comment $\endgroup$ – Willie Wong Dec 13 '19 at 14:37
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.