9
$\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$ 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
    Sep 1, 2011 at 20:01

3 Answers 3

16
$\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$ 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$ 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
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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