# Determining when combinatorial sums are zero

To keep things simple with a specific example, we ask:

Prove that $\displaystyle\ a_n:=\frac{1}{n!}\sum_{k=0}^n \binom{n}{k} \frac{1}{k!} (-1)^{n-k}$ is zero if and only if $n=1$. (Or find a counter-example).

In fact, determining when said sequence is positive and negative is even more challenging. We list the first few calculations, to show that it does not alternate in sign:

$\{a_n\}_{n=0}^\infty=\{1, 0, -\frac{1}{4}, \frac{1}{9}, -\frac{5}{192}, \frac{7}{1800}, -\frac{37}{103680}, \frac{17}{2116800}, \frac{887}{232243200}, \ldots\}$

Posted a related question: https://mathoverflow.net/questions/211767/determing-signs-of-taylor-coefficients-in-entire-functions

• Your numbers seem to be not $a_n$ as you defined it but $a_n/n!$. Of course that doesn't affect the signs. – Robert Israel Jul 17 '15 at 4:46
• Yes, just realized that. Although the questions and analysis are don't change. – Bobby Ocean Jul 17 '15 at 4:47

According to Maple, $a_n$ (with the revised definition) is $(-1)^n \text{LaguerreL}(n,1)/n!$.
I don't know asymptotics of this as $n \to \infty$, but maybe something can be obtained from an integral representation of LaguerreL. The plot is quite suggestive. • The generating function of $(-1)^n \text{Laguerre}(n,1)$ is $e^{\frac{t}{1+t}}/(1+t)=e^{-t^2/2 + 2t^3/3 + O(t^4)}$ (see en.wikipedia.org/wiki/Laguerre_polynomials). That should be enough to derive asymptotics and in particular, the sign. – Ofir Gorodetsky Jul 17 '15 at 5:55
• This should settle the vanishing question, at any rate: according to this paper math.berkeley.edu/~lam/html/fila.ps Schur showed in 1929 that the Laguerre polynomials are always irreducible, so in particular cannot have a rational root once $n>1$. – Noam D. Elkies Jul 17 '15 at 6:08
• And the asymptotics were also studied: Theorem 8.22.1 (due to Fejér) in Szegő's "Orthogonal Polynomials" implies that $\text{Laguerre}(n,1) = \sqrt{e/\pi} n^{-1/4} \cos(2\sqrt{n}-\frac{\pi}{4}) + O(n^{-3/4})$. So the sign is related to $2\sqrt{n} \mod {2\pi}$. If you're worried about the error term being large compared to the $\cos$, Perron also provided an asymptotic expansion. – Ofir Gorodetsky Jul 17 '15 at 6:30
• Good graph and comments. Very good stuff. I thought this might turn into another dead post, so I am going to post the problem I have been wondering in another thread. – Bobby Ocean Jul 17 '15 at 9:29
• Non-vanishing can be established by simpler means, after multiplying by $n!^2$ we get an integer which is 1 modulo $n$. – Ofir Gorodetsky Jul 17 '15 at 10:05

(Non-vanishing is established by multiplying by $n!^2$ and getting an expression which is 1 modulo $n$.)

Robert Israel's answer and the comments following it settle your problem completely, but here's a general strategy that often works:

Suppose you have a sum of the form $S(n) = \sum_{k=0}^{n} f(n,k)$, where $f$ is "hyper-geometric" in the sense that $f(n+1,k)/f(n,k), f(n,k+1)/f(n,k)$ are rational functions.

1. Find the maximum of $|f(n,k)|$ as a function of $k$ ($n$ fixed). This is rather easy because $|f(n,k+1)|/|f(n,k)|$ is the absolute value of a rational function. In your specific problem, it is $\frac{n-k}{(k+1)^2}$, so $|f(n,k)|$ increases for $k \lesssim \sqrt{n}$ and then it decreases. The sign of the largest term is usually the resulting sign of the sum.
2. Suppose the maximum is attained at $k=M(n)$. Focus on estimating the sum around $k=M(n)$ (the rest of the terms should be easier to bound, as we know they are smaller, the decay is exponential usually). Specifically, Stirling's approximation is usually enough for estimating $\sum_{k=-\Delta}^{\Delta} f(n,M(n)+k)$ - plugging Stirling and using some Taylor series estimates ($\Delta$ is chosen so that the Taylor series estimates are valid), we get a sum that can sometimes be evaluated even by comparing to a Riemann's integral.

This is a rather elementary approach; Asymptotic methods such as steepest descent can yield much better results if you can express your sum as the coefficient of some analytic function. This can be done in your case as we have the relevant generating function: $e^{\frac{t}{1+t}-\ln(1+t)}$. See de Bruijn' "Asymptotic Methods in Analysis" (the example in section 4.7 is solved twice in the text - Laplace' method and Steepest descent, and it is reminiscent of your sum as it contains a sign-changing term).

The sign-changing property of your sum makes other nice methods obsolete. Hayman's method, for example, works in extracting the coefficients of $e^{P(t)}$ where $P$ is a function satisfying some positivity conditions ($\frac{t}{1+t}-\ln(1+t)$ is not admissible as its coefficients are sign-changing, but the method should succeed in approximating your sum if we remove the sign-changing term).

• It is interesting that mention, analytic, since in particular, – Bobby Ocean Jul 17 '15 at 9:12
• Oh, I can't edit if I bump the post button on my phone. – Bobby Ocean Jul 17 '15 at 9:13
• All I was trying to say was, $\sum_{n=0}^\infty a_n x^n = e^{-x} J_0(-2\sqrt{x})$, where $J_0$ is the Bessel function. – Bobby Ocean Jul 17 '15 at 9:24