I would like to produce an easily-interpretable explicit upper bound (i.e. no unspecified constants) for the function
$$
f(n) := L\_n^{\left(-n-\frac{d}{2}\right)}\left(-\frac{1}{2}\right), \quad n,d \in \mathbb{N}
$$  

with $d$ a fixed parameter. This bound needn't be especially sharp (I only need it to characterize $f(n)$'s growth rate up to exponential factors), but for my application I would like it to hold in the *nonasymptotic* regime.


I haven't been able to find much on nonasymptotic bounds for generalized Laguerre polynomials with negative argument (particularly for the case in which both parameters are negative and co-varying), but by applying the recurrence relation:
$$
L\_n^{(a)}(x) = \frac{\alpha + 1 - x}{n} L\_{n-1}^{(\alpha + 1)}(x) - \frac{x}{n} L\_{n-2}^{(\alpha + 2)}(x)
$$
I have shown that the function $f(n)$ can be described by the following recurrence relation:
$$
f(0) = 1 \\
f(1) = \frac{1 - d}{2} \\
f(n) = \left(\frac{3-d}{2n} - 1\right)f(n-1) + \frac{1}{2n} f(n-2), \quad n \ge 2 \\
$$
I'm hoping it might be possible to use this description of $f(n)$ to recover a closed-form expression for it, or failing that, at the very least use it to control f(n)'s growth rate. Given the simple form of the recurrence relation, I've been trying to solve it using generating functions, but haven't met with much success yet (although I am far from an expert in these techniques, so it's entirely possible that there's a much simpler/better way :-P).


Does anyone know of any uniform bounds for Laguerre polynomials that would be relevant for this application (i.e. with x = -1/2)? Or failing that, does anyone have a recommendation for a technique that could be used to either solve the recurrence or control its growth rate?


Thanks!



Upper-bounding the value of a generalized Laguerre polynomial (using recurrence relation?)
You can obtain good bounds by applying the saddle-point method to the generating function. A good introduction to these techniques is in the book *Analytic Combinatorics* by Flajolet & Sedgewick. In your case, you can avoid going to the complex plane and have simple bounds as follows:


1. The generating series of your sequence $f(n)$ is $$F(z):=e^{z/2}(1+z)^{-d/2}.$$ This can be seen by translating your recurrence for $f(n)$ into a linear differential equation. The equation has order 1 and can be solved by any computer algebra system (or even by hand).
2. From there a sort of closed-form follows: $$f(n)=\sum\_{j=0}^{n}{\frac{1}{2^{j}j!}\binom{-d/2}{n-j}}=(-1)^n\sum\_{j=0}^n{\frac{(-1)^j}{2^jj!}\binom{d/2+n-j-1}{n-j}}.$$ This is also what you would get using the classical closed form of the generalized Laguerre polynomials.
3. The signs of $f(n)$ alternate, or equivalently, $F(-z)$ has a Taylor expansion with only nonnegative coefficients. Indeed, $$F(-z)=e^{-z/2}(1-z)^{-d/2}=\exp\left(\frac{d}{2}\log\frac1{1-z}-\frac{dz}2\right)\exp\left(\frac{(d-1)z}2\right)$$ is a product of series with nonnegative coefficients.
4. If $g(z)=\sum\_{n\ge0}{a\_nz^n}$ has nonnegative coefficients $a\_n$, then for any $x>0$ where the series converges, $$a\_n\le g(x)/x^n$$ since this is one summand among a sum of positive terms. Optimizing the choice of $x$ gives good bounds that are reasonably tight asymptotically, as the optimal value of $x$ corresponds to the saddle-point.
5. In the example of $F(-z)$ above, cancelling the derivative and keeping the positive solution leads to $x$ close to $$r:=\frac{\sqrt{(2n+d-1)^2+4}+1-d-2n}{2}.$$ Thus a good bound is $$|f(n)|\le \frac{e^{-r/2}(1-r)^{-d/2}}{r^{n+1}}.$$
6. If this bound is not very convenient, you get weaker bounds by taking other values of $x$, close to $r$. Since the asymptotic behavior of $r$ when $n\rightarrow\infty$ is $r=1-d/(2n)+O(1/n^2)$, you get for instance a good bound with $x=1-d/(2n)$: $$|f(n)|\le \frac{e^{-\frac12+\frac{d}{4n}}}{\left(1-\frac{d}{2n}\right)^n\left(\frac{d}{2n}\right)^{d/2}}.$$


