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

Define ${f}_{i}(x) = \sum_{j=1}^{i} (-1)^{i-j}{i \choose j}j^x$, where $i=1,2,3,...$ and $x \in \mathbb{R}$.

For integer $x \geq i$, ${f}_{i}(x)$ reduces to ${f}_{i}(x)=i!S(x,i)$, where $S(x,i)$ is Stirling Number of the Second Kind. So in this case, we are able to interpret ${f}_{i}(x)$ using some concrete combinatorial model, say the number of ways one can map a set of $x$ objects onto a set of $i$ objects.

Question one: How can we prove $x=1,2,...,i-1$ are zeros for ${f}_{i}$? Is there a model (as the mapping model for the integer $x \geq i$ case, for example) according to which we can intuitively see that such values must be zeros for ${f}_{i}$? (Those zeros don't seem obvious to me.)

Question two: Are $x=1,2,...,i-1$ the only zeros for ${f}_{i}(x)$, $x \in \mathbb{R}$?

Edit: For motivation of the function see discussions here Explicit expression for recursively defined functions

share|cite|improve this question
up vote 18 down vote accepted

[Edited to add sharper bound (number of sign changes) and connection with "Descartes' Rule of Signs"]

Yes, the zeros at $x=1,2,\ldots,i-1$ are the only real zeros of $f_i$.

We prove that in general an "exponential polynomial" with $d+1$ nonzero terms, i.e. $A(x) = \sum_{j=1}^{d+1} a_j \exp(\lambda_j x)$ with distinct $\lambda_j \in {\bf R}$ and each $a_j \in {\bf R}^*$, can have at most $d$ real roots, counted with multiplicity. We use induction on $d$, the base case $d=0$ being trivial. Suppose we've proved the case $d-1$ for some $d>0$. Now $A_0(x) := e^{-\lambda_1 x} A(x)$ is an exponential polynomial, with the same number of nonzero terms and the same roots as $A$, whose $j=1$ term is constant. Hence $A'_0(x) := \frac{d}{dx}(A_0(x))$ is an exponential polynomial with only $d$ nonzero terms. By the inductive hypothesis, it thus has at most $d-1$ real roots. But by Rolle's theorem (easily generalized to allow multiple roots), there's at least one root of $A'_0(x)$ between each consecutive pair of roots of $A_0$, and thus of $A$. Therefore $A$ can have no more than $d$ roots with multiplicity. This completes the induction step and the proof.

In the case at hand, $d=i-1$, each $\lambda_j = \log j$, and each $a_j = (-1)^{i-j} {i \choose j}$. Having already located $i-1=d$ distinct real roots of $A$, we deduce that there are no others (and that each of the known roots is simple). QED

[added later] It is no accident that in our case, where $A(x)$ actually has $d$ distinct roots, the coefficients $a_j$ alternate in sign when the $\lambda_j$ are listed in increasing order. Indeed if we assume without loss of generality that $\lambda_1 < \lambda_2 < \cdots < \lambda_{d+1}$ then the number of real roots (counted with multiplicity) is at most the number, call it $s$, of sign changes in the coefficient sequence $(a_1,a_2,\ldots,a_{d+1})$; that is, at most the number of $j \in \lbrace 1,2,\ldots,d \rbrace$ such that $a_j a_{j+1} < 0$.

To see this, we argue by induction as above, noting also that $A_0(x) = \sum_{j=1}^{d+1} a_j \exp((\lambda_j - \lambda_1) x)$ has $\lambda_j - \lambda_1 > 0$, so each coefficient $(\lambda_j - \lambda_1) a_j$ of $A'_0(x)$ has the same sign as $a_j$ for $j>1$. Thus if $a_1 a_2 < 0$ then $A'_0(x)$ has $s-1$ sign changes, and we're done as before. If $a_1 a_2 > 0$ then $A'_0(x)$ has $s$ sign changes. But then $A_0$ is monotone on $x \leq x_0$ where $x_0$ is the smallest root of $A'_0(x)$. Since the two leading terms of $A_0$ as $x \rightarrow -\infty$ have the same sign, it follows that $A_0$ does not vanish on $x \leq x_0$, and thus by Rolle that $A_0$ has no more real zeros than its derivative. Therefore in this case too $A_0$ has at most $s$ real zeros. This completes the inductive step and the proof. QED

This argument may feel familiar, most likely because the same technique proves Descartes' "rule of signs", which bounds the number of positive roots of an ordinary real polynomial by its number of sign changes. Indeed this "rule of signs" is equivalent to the special case $\lambda_j \in \lbrace 0, 1, 2, \ldots \rbrace$ of our bound, when $A(x)$ is an ordinary polynomial in $e^x$.

share|cite|improve this answer
There needs to be a nonvanishing condition on the coefficients, since the result isn't true if all coefficients are 0. – KConrad Dec 23 '11 at 18:46
Just noticed your comment. Yes, you're right: I meant $d+1$ nonzero terms (a term with $a_j = 0$ can just be dropped). The argument in the induction step does reduce the number of nonzero terms by exactly $1$. I'll edit to say explicitly that $a_j \neq 0$. – Noam D. Elkies Jan 2 '12 at 4:39
I don't expect that any of this is new, but it's the kind of result for which it's easier, or at least more rewarding, to write out a proof than to hunt it down in the literature... – Noam D. Elkies Jan 11 '12 at 6:47

You should look at:

"The zeros of exponential polynomials" by C. Moreno, which has a fairly lucid introduction to the subject and references to other surveys, and then google "zeros of exponential polynomials" -- there are other references (some much more recent).

share|cite|improve this answer

For $x=0,1,\dots, i-1$ (if we change the lower limit of summation to $j=0$) the sum is zero because it is the $i$th difference of a polynomial of degree less than $i$.

Also, the combinatorial interpretation for $x\geq i$ also holds for $x < i,$ which explains why the sum is $0,$ since for $x < i$ the number of surjections from an $x$-element set to an $i$-element set is $0.$

share|cite|improve this answer
@Ira, your answer seems to be randomly truncated... – Igor Rivin Dec 21 '11 at 14:29
Yes, it was randomly truncated. What I was trying to say (and which is in the source) is "Also, the combinatorial interpretation for $x\ge i$ also holds for $x < i$, which explains why the sum is 0, since for $x<i$ the number of surjections from an $x$-element set to an $i$-element set is 0." – Ira Gessel Dec 21 '11 at 14:32
I fixed it. Your < and \leq confuse mathjax. – Igor Rivin Dec 21 '11 at 14:41
@Ira, what polynomial is it that you meant in the first paragraph? $x=0$ and $j=0$ give rise to $0^0$. As for the interpretation, we have to assume $x \geq i$ when we start to construct ${f}_{i}(x)$ from the combinatorial model. We only know, post hoc, that they are 0 for $x<i$ and thus also hold for the model in that case. In this sense that I say the combinatorial model doesn't explain why ${f}_{i}(x)=0$ for $x<i$ (as it does explain ${f}_{i}(x)$ for $x \geq i$) – user16033 Dec 21 '11 at 15:43
The polynomial is $p(j) = j^x$ where $x$ is a nonnegative integer. If $x=0$ this is $p(j)=1$. The derivation of the formula for the number of surjections from an $x$-element set to an $i$ element set, using either inclusion-exclusion or exponential generating functions, works perfectly well for $x<i$. – Ira Gessel Dec 21 '11 at 16:26

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.