# Partial sums of signed binomial coefficients

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{?}$$

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

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.

• 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. – Brian Hopkins Jul 14 at 23:23
• If my computations are correct, $35$ is the least. – Robert Israel Jul 15 at 1:05
• 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. – neha mainali Jul 16 at 4:06
• I believe 35 is the least for which it holds. – neha mainali Jul 16 at 4:07