0
$\begingroup$

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!

UPDATES:

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

$\endgroup$

1 Answer 1

0
$\begingroup$

This is not an answer but it is too long for a comment.

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.

$\endgroup$
3
  • $\begingroup$ Thanks, Leibovici! This could provide some insight. Do you think the Stirling's formula will help? $\endgroup$
    – Mengfan Ma
    Dec 7, 2021 at 9:05
  • $\begingroup$ @MengfanMa. The summand in my writing is a monster. I tried also special functions and nothing came. I am still working it. If anything new, I shall post. Cheers :-) $\endgroup$ Dec 7, 2021 at 9:09
  • $\begingroup$ 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. $\endgroup$
    – Mengfan Ma
    Dec 8, 2021 at 2:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .