10
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ Working modulo a prime q≥N one gets $p(kq)=(−1)kp(0)$ for all $k\leq q$. This makes your guess very plausible. $\endgroup$ Commented Aug 30, 2011 at 8:58
  • $\begingroup$ 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/… $\endgroup$
    – Shir
    Commented Sep 1, 2011 at 20:01

3 Answers 3

17
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yep, I was about to post the same. :) $\endgroup$ Commented Aug 30, 2011 at 9:09
  • 4
    $\begingroup$ 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$. $\endgroup$ Commented Aug 30, 2011 at 9:23
12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice argument... $\endgroup$
    – Igor Rivin
    Commented Aug 30, 2011 at 13:50
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .