Sum of Catalan numbers

Question

What is $C_1 +C_2 + C_3 +... + C_n$, where each $C_i$ is Catalan number? I want to know if we can bound this sum by some function of $n$. I am looking for an upper bound. For sure it is less than $2^{2n}$. Can we say it is less than $2^{\log_2(2n)}=2n$?

Answer 1

By exploiting the integral representation of Catalan numbers: $$ C_n = \frac{1}{2\pi}\int_{0}^{4}x^n\sqrt{\frac{4-x}{x}}\,dx = \frac{2}{\pi}\int_{0}^{1}4^n x^n\sqrt{\frac{1-x}{x}}\,dx$$ we have: $$\begin{eqnarray*}S_N=\sum_{n=1}^{N}C_n &=& \frac{8}{\pi}\int_{0}^{1}\frac{1-4^N x^N}{1-4x}\sqrt{x(1-x)}\,dx.\end{eqnarray*}$$ By computing the derivative of the integrand function it is straightforward to check that $f_N(x)=\frac{1-4^N x^N}{1-4x}\sqrt{x(1-x)}$ attains its maximum near: $$ x = \frac{5N-1+\sqrt{9N^2-18N+1}}{8N}=1-\frac{1}{2N}-\frac{1}{6N^2}+O\left(\frac{1}{N^3}\right)$$ hence it is possible to approximate $S_N$ by computing the values of $f_N(x)$ and $f_N''(x)$ in the stationary point $x_N$, just like it is usual in the saddle point method. We have: $$ f_N(x)\leq\frac{4^N}{\sqrt{eN}} $$ $$ f_N''(x_N)=-\frac{4^{N+1}\sqrt{2}}{3\sqrt{e}}N^{3/2}\left(1+O\left(\frac{1}{\sqrt{N}}\right)\right)$$ hence:

$$\color{blue}{ S_N \leq \frac{20\cdot 4^N}{9\sqrt{e\pi}\,N^{3/2}}.}$$