MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
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:… – Shir Sep 1 '11 at 20:01
up vote 13 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer
Nice argument... – Igor Rivin Aug 30 '11 at 13:50

A little more can be proven, namely, if we only assume that $p$ is a bounded sequence (say of complex numbers) verifying the given equations for all $n\ge N$, then $p(k)=\lambda(-1)^k$ for all $k\in\mathbb{N}$.

Let $u$ be the linear form on $\mathbb{C}[z]$ (as linear space) defined by $\langle u, z^k\rangle:=p(k)$ for any $k\in\mathbb{N} $. Then, since for any $n$ $$\sum _{i=0} ^{n} p(i)\binom {n}{i}=\big\langle u, \sum _{i=0} ^{n} \binom {n}{i} z^i\big\rangle= \langle u, (z+1)^n\rangle$$ verifying the system of the given equations for all $n\ge N$ may be translated as: $u$ vanishes on the ideal $I$ generated by the polynomial $(z+1)^N$, that is, it belongs to the annichilator $I^{\perp}$ of $I$ as linear subspace. Note that by linear algebra, $\dim I^{\perp}=\dim (\mathbb{C}[z]/I)=N$.

Let $u_j$ be linear form that takes the value of the $j$-th derivative at $-1$ , namely $$\langle u_j, P\rangle:=D^jP(-1), \quad\mathrm{for \; } j=0,\dots,N-1,$$ for any $P\in \mathbb{C}[z].$ Clearly, $\{u_0,u_1,\dots,u_{N-1}\}$ are linearly independent element of $I^\perp$, hence a basis. Note that for all $j$ the sequence $p_j(k), (k=0,1,\dots)$ $$p_j(k):=\langle u_j, z^k\rangle:= (-1)^{k-j} k(k-1)\dots(k-j+1) $$ is $(-1)^k$ times a polynomial in $k$ of degree $j$.

As a conclusion, any $p\in \mathbb{C}^\mathbb{N}$ such that for all $n \geq N$

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

must be a linear combination of $p_j$, thus $(-1)^k$ times a polynomial in $k$,

and if $p$ is bounded, it must be a multiple of $p_0$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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