3
$\begingroup$

I don't know if this is true or not but I want this to be true and so far I don't have any counterexample.

Let $i$ be odd. Do there exist coefficients $a_k \in \{0,1\}$ such that

$$\sum_{k=1}^{i-1} (-1)^k \binom{i}{k} a_k = 1\text{?}$$

$\endgroup$
3

2 Answers 2

2
$\begingroup$

Given that $i=2j+1$ is odd, $a_k$ and $a_{i-k}$ cancel out if both are equal. So you could equivalently ask for coefficients $b_k\in \{-1,0,1\}$ such that $$\sum_{k=1}^jb_k\binom{i}{k}=1.$$

I will ignore the cases of $k=0$ and $k>j$

If there is a prime $p$ such that $p|\binom {i}{k}$ with few exceptions, then it may be possible to rule out a sum of the form you seek being any value congruent to $1 \bmod p.$

This eliminates the sum being $1 \bmod p$ for a prime power $i=p^e$, for any $i=3p$ and for all $i=5p$ except, perhaps, $i=35$ and $i=55$

If $i=p^e$ is a prime or prime-power then $p|\binom{i}{k}$ so the sum can't never be anything other than a multiple of $p.$

If $i=3p$ then $p|\binom{3p}{k}$ with the exception that $\binom{3p}{p} \equiv 3 \bmod p$ so the sum can only be $0,3$ or $p-3$ $\bmod p.$

For $i=5p$ we have $\binom{5p}{p} \equiv 5 \bmod p$ and $\binom{5p}{2p} \equiv 10 \bmod p$ so the sum can only be $0,\pm5,\pm 10,\pm 15$ $\bmod p$ For $p=7$ we do have $15 \equiv 1 \bmod p.$ And $p=11$ is not obviously ruled out.

However we do see that the only chance for $\sum_{k=1}^{27}b_k\binom{55}k=1$ is $b_{11}=0$,$b_{22}=-1$ and the other terms (which are all multiples of $11$) adding to $\binom{55}{22}+1.$ Looking $\bmod 5$ seems to force $b_5=0$ and $b_{25}=1.$

In general, for $i=qp$ with $q<p$ and both prime, $\binom{qp}{rp} \equiv \binom{q}{r} \bmod p$ This will eliminate all but a finite number of $p$ for any given $q$. And in the cases not immediately ruled, out the possibilities to search over are restricted.

Similar considerations rule out $i=7p$ for $p >7$ prime, with the possible exceptions of $p=11, 13, 17, 19, 29, 31, 41, 43$, the primes dividing $N-1,N$ or $N+1$ for $N=7,14,21,35,42,49,56,63$ , these being the numbers $N$ which can be formed from some or all of $7,21,35=\binom{7}{1},\binom{7}{2},\binom{7}{3}$ with addition and subtraction.

I don't immediately see an obstacle to $i=105.$

$\endgroup$
1
$\begingroup$

For $i = 35$, take $a_k = 1$ for $k = 11, 14, 15, 22, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34$, and $0$ otherwise.

$\endgroup$
4
  • $\begingroup$ Nice example. Given Gerhard's comments and some fiddling I did with small values, maybe the question should be about finding (characterizing?) $i$ for which this does work. $\endgroup$ Jul 14, 2020 at 23:23
  • $\begingroup$ If my computations are correct, $35$ is the least. $\endgroup$ Jul 15, 2020 at 1:05
  • $\begingroup$ That's a nice counterexample. Can we argue that once we have used some coefficients in a combination to sum to 1, then there does not exist any combination of the remaining terms that could sum to 0. $\endgroup$ Jul 16, 2020 at 4:06
  • $\begingroup$ I believe 35 is the least for which it holds. $\endgroup$ Jul 16, 2020 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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