# Proof for an Inequality

Let $e^{e^x}=\sum\limits_{n\geq0}a_nx^n$, prove that

$$a_n\geq e(\gamma\log n)^{-n}$$

for $n\geq2$, where $\gamma$ is some constant great than $e$.

-
Can I ask which topics have recently been covered in your course or book? –  bgins Apr 5 '12 at 21:42

I present three different approaches below, which may or may not appeal to you in helping you to formulate your own answer.

I think you can get this from the Taylor series at $0$ just by differentiating. If $y=y^{(0)}$ is your function and $y^{(n)}=yf_n(e^x)$, then $f_0(t)=1$, $y'=ye^x\implies f_1(t)=t$ and $y^{(n+1)}=y'f_n(e^x)+y\,e^xf_n'(e^x)$ $\implies$ $f_{n+1}(t)=f_1f_n+t\,f_n'$. Now $a_n=\frac{e\,f_n(1)}{n!}$ and $f_n(1)=\href{http://en.wikipedia.org/wiki/Bell_number}{B_n}$ (as @Autolatry points out) and it shouldn't be hard to show that this sequence is increasing and has (more than) the desired growth.

Upon further reflection, we want to show that for $n\ge2$, $$a_n \ge e \left( \gamma \, \log n \right)^{-n}$$ $$\left( \gamma \, \log n \right)^{-n} \le \frac{a_n}{e} = \frac{B_n}{n!}$$ $$\gamma \, \log n \ge \left( \frac{a_n}{e} \right)^{-1/n} = \left( \frac{n!}{B_n} \right)^{1/n}$$ $$\gamma \ge \sup \gamma_n \qquad\text{for}\qquad \gamma_n = \frac1{\log n} \left( \frac{a_n}{e} \right)^{-1/n} = \frac1{\log n}\left( \frac{n!}{B_n} \right)^{1/n}$$

Experiment suggests that $\gamma_n$ has a global minimum at $\gamma_{37}=0.56352\,15372\,44847$, lies below its pseudonym, the Euler-Mascheroni constant, $0.57721\,56649\,01532\cdots$, for $17\le n\le 114$, and may have its global maximum at $\gamma_2=1.44269\,50408\,88963$, depending on its asymptotic value. Using a recent bound (Berend-Tassa 2010) for $B_n$ and Stirling's formula for the factorial, $$\gamma_n \ge \frac{\log(n+1)}{0.792\,n\,\log n}\Bigl( n! \Bigr)^{1/n} \approx \frac{\log(n+1)}{0.792\,\,n\log n}\cdot\frac{n}{e}\cdot\left(2\pi n\right)^{1/2n} \rightarrow\frac1{0.792\,e}\approx0.46449\,,$$ so that $\gamma=\gamma_2=\sup_{n\ge2}\gamma_n$ is in fact the best constant we can choose.

If we start from $y=e^{e^x}=\sum_{n=0}^{\infty}a_n\,x^n$ and differentiate to get $\sum_{n=0}^{\infty}(n+1)a_{n+1}\,x^n=y'=e^x\cdot e^{e^x}=\left(\sum_{n=0}^{\infty}\frac{x^n}{n!}\right)\left(\sum_{n=0}^{\infty}a_n\,x^n\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n\frac{a_k}{(n-k)!}\right)x^n$, then we need to show (perhaps inductively) that the recursion $(n+1)a_{n+1}=\sum_{k=0}^n\frac{a_k}{(n-k)!}$ implies the desired inequality. Now $a_0=a_1=e\cdot1$ and the first few values we care about are $a_2=e\cdot\frac22$, $a_3=e\cdot\frac56$, $a_4=e\cdot\frac{15}{24}$, which as we already know satisfy our inequality for $\gamma\ge\gamma_1$ for our inductive base ($n=2$). As inductive hypothesis (with cumulative induction), we assume the inequality for $k\le n$: $$a_k \ge e \left( \gamma \, \log k \right)^{-k}$$ from which it follows by induction (and from the recursion) that \eqalign{ \frac{a_{n+1}}{e}\,\left(\gamma\log(n+1)\right)^{n+1} &\ge \frac{\left(\gamma\log(n+1)\right)^{n+1}}{n+1} \sum_{k=0}^n \frac{(\gamma\log k)^{-k}}{(n-k)!} \\ & > \frac{\left(\gamma\log(n+1)\right)^{n+1}}{n+1} \sum_{k=0}^n \frac{(\gamma\log n)^{-k}}{(n-k)!} \\ & > \frac{\gamma\log(n+1)}{n+1} \sum_{k=0}^n \frac{(\gamma\log n)^{n-k}}{(n-k)!} \\ & > \frac{\gamma\log(n+1)}{n+1} \sum_{k=0}^n \frac{(\gamma\log n)^k}{k!} \\ & \color{red}{>} \frac{\gamma\log(n+1)}{n+1} \left(e^{\gamma\log n} - \frac{(\gamma\log n)^{n+1}}{(n+1)!} \right) \\ & = \frac{\gamma\log(n+1)}{n+1} \left(n^\gamma - \frac{(\gamma\log n)^{n+1}}{(n+1)!} \right) \\ & \color{blue}{\ge 1 \qquad\text{(what we want!)}} } where the last inequality (in red) follows from the error theorem for Taylor series. On the subsequent line, the two terms in parentheses exhibit opposite asymptotic behavior: the former grows toward $\infty$ for all $\gamma > 1$, while the latter decays toward $0$. We need only show that the last expression is $\color{blue}{\ge1}$ for some fixed $\gamma$ and all $n\ge2$. Clearly, this is true asymptotically for all $\gamma > 1$ by the relative asymptotic growth of $\log n$ versus $n^{\gamma-1}$ (e.g. using L'Hopital's rule). I suspect a slight modification of this argument would yield the result more elegantly.

-
Due to the expansion of the function $e^{e^x}$, we know that $a_n=\frac{eB_n}{n!}$. –  Riemann Apr 5 '12 at 13:51
Yes, of course. Thanks! –  bgins Apr 5 '12 at 14:41

Hint:

$$e^{e^{x}} = e \sum_{k=0}^{\infty} \frac{x^{k}B_{k}}{k!}$$

Where $B_{k}$ is the $k$-th Bell number which is the number of partitions of a set with k entries, or the number of equivalence relations on it. Starting with $B_{0} = B_{1} = 1$, the first few Bell numbers are: $$1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975 \ldots$$

-