Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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: mathoverflow.net/questions/74191/… –  Shir Sep 1 '11 at 20:01

2 Answers 2

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|improve this answer
    
Yep, I was about to post the same. :) –  Gjergji Zaimi Aug 30 '11 at 9:09
3  
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|improve this answer
    
Nice argument... –  Igor Rivin Aug 30 '11 at 13:50

Your Answer

 
discard

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.