# Constant lower bound of this summation involving factorial?

Given

$$f(n)=\frac{n}{(2 n) !} \sum_{i=0}^{n-1}\left((n+i-1) ! \sum_{k=0}^{i} \frac{(n-k-1) !}{(i-k) !}\right)$$

where $$n$$ is natural.

Is there a constant lower bound for $$f(n)$$, i.e., is there a constant $$c>0$$ such that $$f(n)\ge c$$ for each natural $$n$$?

This complicated formula basically means some probability, and I (strongly) believe that it can be lower bounded by a constant since I've calculate several points via wolframalpha:

n 1 2 3 4 5 15 20 30 40 100 200 300 400
f(n) 0.5 0.4167 0.3917 0.3798 0.3710 0.3550 0.3529 0.3508 0.3497 0.3478 0.3472 0.3470 0.3469

But I have no idea what math tools or techniques can be used to lower bound $$f(n)$$. Can anyone give a (tight) constant lower bound or prove that $$f(n)$$ has no constant lower bound? Thanks in advance!

If we only consider the term where $$i=n-1$$ in the summation, a lower bound of $$1/4$$ can be easily obtained:

\begin{align} f(n) &\ge \frac{n}{(2 n) !}\cdot (n+i-1) ! \cdot\sum_{k=0}^{i} \frac{(n-k-1) !}{(i-k) !} \\ &= \frac{n^2\cdot(2n-2)!}{(2n)!} \\ &\ge 1/4 \end{align} Then the question is: can we get a bound larger than $$1/4$$?

We can compute the inner sum $$\sum_{k=0}^i\frac{(n-k-1)!}{(i-k)!}=\frac{n !}{i! \,(n-i)}$$ and this makes $$f_n=\frac{n \,n!}{(2 n)!}\sum_{i=0}^{n-1}\frac{(i+n-1)!}{i! \,(n-i)}$$ I did not find any expression for the remaining summation and, as you did, I computed the value for $$n=10^k$$ $$\left( \begin{array}{ccc} k & f_{10^k} &f_{10^k}-f_{10^{k-1}} \\ 1 & 0.3593857 & \\ 2 & 0.3478267 & -0.011559 \\ 3 & 0.3466986 & -0.001128 \\ 4 & 0.3465861 & -0.000113 \end{array} \right)$$ It seems that is slowly converging.
• It seems that in your simplified summation, only the term where $i=n-1$ is $\Theta(1/4)$, other terms with $i<n-1$ is $o(1)$, thus $1/4$ is indeed the tight bound. Dec 8, 2021 at 2:37