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

Improve this question
$\endgroup$
5
  • 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
    Commented Dec 13, 2019 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
    Commented Dec 13, 2019 at 23:03
  • 1
    $\begingroup$ @Gerry you're right—I deleted my comment. $\endgroup$
    – Ira Gessel
    Commented Dec 14, 2019 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
    Commented Dec 15, 2019 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
    Commented Dec 16, 2019 at 5:50

5 Answers 5

Reset to default
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.

Improve this answer
$\endgroup$
3
$\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.

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

Improve this answer
$\endgroup$
2
  • 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
    Commented Dec 13, 2019 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
    Commented Dec 13, 2019 at 14:37
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. $$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .