# Zero sum of binomial coefficients

Is there a function $p:\mathbb N\to \{ 1,-1 \}$ and a fixed $N\in \mathbb N$ such that for every $n \geq N$ we get:

$\sum _{i=0} ^{n} p(i)\binom {n}{i}=0$ ?

Obviously $p(i)=(-1)^i$ works for $N=1$, and so does $p(i)=(-1)^{i+1}$, but are there any others?

(my personal guess is that there aren't)

-
Working modulo a prime q≥N one gets $p(kq)=(−1)kp(0)$ for all $k\leq q$. This makes your guess very plausible. – Roland Bacher Aug 30 '11 at 8:58
For general reference, this one is a weaker version of an open problem. Nice to know this version has a relatively simple answer. Thanks guys. The stronger version: mathoverflow.net/questions/74191/… – Shir Sep 1 '11 at 20:01

No, there are no others.

In fact, define a function $q : \mathbb N\to\left\lbrace 1,-1\right\rbrace$ by $q\left(i\right) = \left(-1\right)^i p\left(i\right)$ for every $i\in\mathbb N$. Then, $\sum\limits_{i=0}^n p\left(i\right) \binom{n}{i} = 0$ becomes $\sum\limits_{i=0}^n \left(-1\right)^i q\left(i\right) \binom{n}{i} = 0$. Now, denote, for every $n,x\in\mathbb N$, the number $\sum\limits_{i=0}^n \left(-1\right)^i q\left(x+i\right) \binom{n}{i}$ by $\left(\Delta^n q\right)\left(x\right)$. Then, the function $\Delta^n q$ thus defined is the so-called $n$-th finite difference of the function $q$. (If you don't know about finite differences, this is the right time to google.) Our condition $\sum\limits_{i=0}^n \left(-1\right)^i q\left(i\right) \binom{n}{i} = 0$ rewrites as $\left(\Delta^n q\right)\left(0\right) = 0$.

So we have $\left(\Delta^n q\right)\left(0\right) = 0$ for all $n\geq N$. We will now prove that $\Delta^n q = 0$ (not only at the point $0$, but as functions!) for all $n\geq N$. In fact, let us prove that every $x\in \mathbb N$ satisfies $\left(\Delta^n q\right)\left(x\right) = 0$ for all $n\geq N$. We will prove this by induction over $x$: The induction base ($x=0$) follows from $\left(\Delta^n q\right)\left(0\right) = 0$. For the induction step, assume that some $x\in\mathbb N$ satisfies $\left(\Delta^n q\right)\left(x\right) = 0$ for all $n\geq N$. Then, clearly, $\left(\Delta^{n+1} q\right)\left(x\right) = 0$ for all $n\geq N$ as well (because $n\geq N$ entails $n+1\geq N$). Now, the properties of finite differences yield

$\left(\Delta^{n+1} q\right)\left(x\right) = \left(\Delta\left(\Delta^n q\right)\right)\left(x\right) = \left(\Delta^n q\right)\left(x\right) - \left(\Delta^n q\right)\left(x+1\right)$.

Since $\left(\Delta^{n+1} q\right)\left(x\right) = 0$ and $\left(\Delta^n q\right)\left(x\right) = 0$, we thus obtain $\left(\Delta^n q\right)\left(x+1\right) = 0$. This completes the induction step. Hence, we have shown that every $x\in \mathbb N$ satisfies $\left(\Delta^n q\right)\left(x\right) = 0$ for all $n\geq N$. Thus, $\Delta^n q = 0$ for all $n\geq N$. In particular, $\Delta^N q=0$. Now, by another well-known property of finite differences, a function whose $N$-th finite difference is $0$ must be a polynomial of degree less than $N$. Hence, $q$ is a polynomial of degree less than $N$. Since $q$ only takes values in $\left\lbrace 1,-1\right\rbrace$, this yields that $q$ is either constantly $1$ or constantly $-1$. This means that $p$ is either $\left(-1\right)^i$ or $\left(-1\right)^{i+1}$.

-
Yep, I was about to post the same. :) – Gjergji Zaimi Aug 30 '11 at 9:09
It's an "if and only if". For any polynomial $p$ of degree $N-1$, the sequence $\sum (-1)^i p(i)\binom{n}{i}$ is zero for $n\geq N$. – Gjergji Zaimi Aug 30 '11 at 9:23

For $r<1/2$, consider the following power series: $\sum_{n\geq N} r^n \sum_{i=0}^n p(i) \binom n i$. On the one hand, this power series is identically zero. On the other hand, since $p(i)$ is bounded, one can exchange the sums and get $0 = \sum_{i\geq 0} p(i) r^i \sum_{n\geq i,N} r^{n-i} \binom n i= Q(r) + \sum_{i \geq 0} p(i) r^i (1-r)^{-1-i}$ for some polynomial $Q$ of degree less than $N$.

Making the change of variable $z=r/(1-r)$, one gets that the function $f(z) = \sum_i p(i) z^i$ is therefore a polynomial in $1-r = 1/(1+z)$. Now observe from the power expansion of $1/(1+z)^k$ for $k \in \mathbb N$ that for $p(i)$ to be bounded, it is necessary that this polynomial be of degree at most $1$. It is now not difficult to see that $p$ is either $p(i) = (-1)^i$ for all $i$ or $(-1)^{i+1}$ for all $i$.

Hoping I did not make to many mistakes.

-
Nice argument... – Igor Rivin Aug 30 '11 at 13:50