Estimating the sum of first $\sqrt{n}$ coefficients of $\frac{1}{n!}x \prod_{i=1}^{n-1} (x+i)$

50 Views Asked by At

So I want to estimate the sum of first $\sqrt{n}$ coefficients of $\frac{1}{n!}x \prod_{i=1}^{n-1} (x+i)$. That is, letting $f=\frac{1}{n!}x \prod_{i=1}^{n-1} (x+i)=\sum_i a_i x^i$, I want to estimate $\sum_{i< \sqrt{n}} a_i$. More important, I think (after some mathematica computations) the sum goes to $1$ as $n\rightarrow \infty$.

Since $f(1)=1$, it suffices to show only the lower bound. That is, show that $\sum_{i< \sqrt{n}} a_i > 1-\frac{1}{n}$ for large enough $n$.

I think this makes sense, since $$a_i \sum\limits_{1\leq j_1 < \dots < j_{n-i} \leq n-1} j_1 \dots j_{n-i}.$$ If $i$ is large, it is only the sum of product of very few terms.

I have tried to lower bound $a_i$ by ${{n-1}\choose {i-1} }(i-1)!$, but the bound is too rough to have the result.

1

There are 1 best solutions below

0
On BEST ANSWER

It seems that considering it as a probability question and solve it with markov inequality makes things simple. Define $a_i=P[X=i]$

Since sum of coefficients is $1$, we can calculated the expected value by differentiating it and putting $x=1$. By some product rule we can see that the expected value is $f'(1)= \frac{n!}{1}+\dots +\frac{n!}{n}$, so it is bounded above by $\log(n)+1$.

Then by Markov inequality, $P[X\geq \sqrt{n}]\leq \frac{\log(n)+1}{\sqrt{n}}$, completing the proof.