5
$\begingroup$

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

$\endgroup$

3 Answers 3

18
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ There needs to be a nonvanishing condition on the coefficients, since the result isn't true if all coefficients are 0. $\endgroup$
    – KConrad
    Dec 23, 2011 at 18:46
  • $\begingroup$ 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$. $\endgroup$ Jan 2, 2012 at 4:39
  • 1
    $\begingroup$ 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... $\endgroup$ Jan 11, 2012 at 6:47
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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$) $\endgroup$
    – Eric
    Dec 21, 2011 at 15:43
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Ira Gessel
    Dec 21, 2011 at 16:26

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.