# Upper bounds for a sequence of integers defined recursively

Given $$\alpha\geq0$$ we consider the sequence $$C_k=k^\alpha\sum_{j=0}^{k-1}C_jC_{k-1-j}$$ with $$C_0=1$$. I'm interested in upper bounds (in terms of $$\alpha$$) for such a sequence. I know that when $$\alpha=0$$ the previous sequence reduces to the Catalan numbers where the bound is

$$O(4^k/k^{3/2}),$$ but I wonder whether something is known for positive $$\alpha$$.

There are three cases.

• If $$\alpha=0$$, then we have the standard Catalan numbers, which you know are $$O\left(k^{-\frac{3}{2}}4^k\right)$$.
• If $$\alpha=1$$, then $${\log(k)}2^{k-2}k!^{\alpha}\leq C_k\leq O(\sqrt{k})\cdot2^kk^{\alpha!}$$.
• If $$\alpha>1$$, then $$C_k=\Theta(2^kk!^{\alpha})$$ and there are explicit and simple bounds.

To see this, first let $$U_k=\frac{C_k}{2^kk!^{\alpha}}$$. This sequence satisfies the recurrence $$U_0=1$$, \begin{align*} U_{k+1}&=\frac{(k+1)^{\alpha}\sum_{j=0}^k{C_jC_k}}{2^{k+1}(k+1)!^{\alpha}} \\ &=\frac{1}{2}\sum_{j=0}^k{\frac{C_j}{2^jj!^{\alpha}}\frac{C_{k-j}}{2^{k-j}(k-j)!^{\alpha}}\cdot\frac{j!^{\alpha}(k-j)!^{\alpha}}{k!^{\alpha}}} \\ &=\frac{1}{2}\sum_{j=0}^k{\binom{k}{j}^{-\alpha}U_jU_{k-j}} \end{align*} These binomial coefficients grow very rapidly. For $$\alpha>0$$, this sum is dominated by its outermost terms. Our goal will be to expand out the first few terms and use them to control the growth of $$U_k$$.

First, an elementary property. Note that $$U_0=1$$ and $$U_1=\frac{1}{2}$$ and apply the recursion: $$U_{k+1}\geq\frac{1}{2}\left(\binom{k}{0}^{-1}U_0U_k+\binom{k}{k}^{-1}U_kU_0\right)=U_k$$ Thus $$\{U_k\}_k$$ is increasing after $$U_0>U_1$$. In particular, $$U_k\geq U_1=\frac{1}{2}$$ for all $$k$$.

Second, estimating the recursion. Since $$\{U_k\}_k$$ is increasing, for $$k\geq6$$, we have \begin{align*} U_kU_0+\frac{1}{k^{\alpha}}\cdot U_{k-1}U_1&\leq U_{k+1} \\ &\leq U_kU_0+\left(\frac{1}{k}\right)^{\alpha}\cdot U_{k-1}U_1+\left(\frac{2}{k(k-1)}\right)^{\alpha}U_{k-2}U_2+{} \\ &\phantom{\leq}\quad\quad\frac{1}{2}\sum_{j=3}^{k-3}{\binom{k}{j}^{-\alpha}U_{k-3}^2} \end{align*} What is this sum of binomial coefficients? Well, for $$k\geq6$$, \begin{align*} \sum_{j=3}^{k-3}{\binom{k}{j}^{-\alpha}}&\leq\sum_{j=3}^{k-3}{\binom{k}{j}^{-1}} \\ &\leq(k-6)\cdot\frac{6}{k(k-1)(k-2)} \\ &\leq\frac{6}{k(k-1)} \end{align*}

Also, $$U_2=\frac{1}{2}$$. Thus for $$k\geq6$$, $$\frac{U_{k-1}}{2k^{\alpha}}\leq U_{k+1}-U_k\leq\frac{U_{k-1}}{2k^{\alpha}}+\frac{2^{\alpha-1}U_{k-2}}{(k(k-1))^{\alpha}}+\frac{3U_{k-3}^2}{k(k-1)}\quad\quad\quad(1)$$

This is where we must split off the $$\alpha=1$$ case. Suppose $$\alpha>1$$. The right-hand-side of (1) is decreasing in $$\alpha$$, so we can reduce it to $$\frac{U_{k-1}}{2k^{\alpha}}\leq U_{k+1}-U_k\leq\frac{U_{k-1}}{2k^2}+\frac{U_{k-2}}{2k(k-1)}+\frac{3U_{k-3}^2}{k(k-1)}\quad\quad\quad(2)$$ (Yes, this is not sharp. I only need $$\omega(k^2)$$ denominators and higher orders make for more complicated algebra.)

Now, $$\{U_k\}_k$$ is increasing, so it suffices to estimate the supremum and show it finite. Suppose there exists $$S$$ such that $$U_k\leq S$$ for all $$1\leq k\leq K$$. Then, equation (2) simplifies to $$\frac{1}{4k^{\alpha}}\leq U_{k+1}-U_k\leq\frac{S}{2k^2}+\frac{S+6S^2}{2k(k-1)}$$ Iterating, \begin{align*} \sum_{j=6}^K{\frac{1}{4j^{\alpha}}}\leq U_{K+1}-U_6&\leq\sum_{j=6}^K{\frac{S}{2j^2}+\frac{S+6S^2}{j(j-1)}}\\ &\leq\sum_{j=6}^{\infty}{\frac{S}{2j^2}+\frac{S+6S^2}{j(j-1)}} \\ &=S\left(\frac{\pi^2}{12}-\frac{5269}{3600}\right)+\frac{S+6S^2}{5} \\ &=S\left(\frac{\pi^2}{12}-\frac{4549}{3600}+\frac{6}{5}S\right) \end{align*} In particular, if $$\alpha=2$$, we can verify that, for all $$1\leq k\leq6$$, we have $$U_k\leq\frac{136613}{230400}\approx0.593$$ The $$\{U_k\}_k$$ are decreasing in $$\alpha$$, so this in fact shows that we may take $$S=\frac{136613}{230400}$$ for any $$\alpha$$. But, for that value, $$\frac{\pi^2}{12}-\frac{4549}{3600}+\frac{6}{5}S\leq1$$ So we can substitute and observe a closed recursion: $$\frac{\zeta(\alpha)-\sum_{j=1}^5{j^{-\alpha}}}{4}+O(k^{1-\alpha})\leq U_{K+1}-U_6\leq S\cdot1$$

Thus $$U_{K+1}$$ has a finite supremum between $$U_6+\frac{\zeta(\alpha)-\sum_{j=1}^5{j^{-\alpha}}}{4}$$ and $$\frac{613271740721}{398131200000}-\frac{136613\pi^2}{3317760}+U_6$$. But we already have estimates on $$U_6$$. Putting it all together, there is some $$\lim_{k\to\infty}{U_k}\in\left[\frac{1}{2}+\frac{\zeta(\alpha)-\sum_{j=1}^5{j^{-\alpha}}}{4},\frac{849339004721}{398131200000}-\frac{136613\pi^2}{3317760}\right]$$ where the upper bound is $$\approx1.73$$ (Numerically, it appears the limit is $$\approx0.5$$.)

If $$\alpha=1$$, then our argument is a little trickier, to the point that I haven't tried to work out all the details. First, suppose $$U_k\leq f(k)$$, for some increasing but slowly-varying $$f$$ (we will end up with $$f(j)=\Theta(\sqrt{j})$$). Let $$H_n=\sum_{j=1}^n{\frac{1}{j}}=\log{(n)}-\gamma+o(1)$$. Then equation (1) shows that $$\frac{H_K-H_5}{4}\leq U_{K+1}-U_6\leq\sum_{j=6}^K{\left(\frac{f(j)}{2j}+\frac{f(j)+3f(j)^2}{2j(j-1)}\right)}$$ The left-hand side shows that we must have at least logarithmic growth: the claimed lower bound. To close this recursion on the right, we need $$U_6+\sum_{j=6}^K{\frac{f(j)}{2j}\left(1+\frac{1+3f(j)}{j-1}\right)}\leq f(j)$$ If $$f$$ is sharp, there will be equality.

This looks awful, but since $$f$$ is slowly-varying, we can apply a quantitative form of the integral test (see exercise 30(a)): $$\sum_{j=6}^K{\frac{f(j)}{2j}\left(1+\frac{1+3f(j)}{j-1}\right)}\approx\int_{j=6}^K{\frac{f(j)}{2j}\left(1+\frac{1+3f(j)}{j-1}\right)\,dj}$$ Here the error term is proportional to the largest value of the integrand. We will see that $$f(j)=(1+o(1))C\sqrt{j}$$, so $$\frac{f(j)}{j}=(1+o(1))Cj^{-\frac{1}{2}}\to0$$ as $$j\to\infty$$.

If we apply this integral approximation and differentiate, then we have a differential equation that we can solve for $$f$$: \begin{align*} f'(j)&=\frac{f(j)}{2j}\left(1+\frac{1+3f(j)}{j-1}\right) \\ f(6)&=U_6 \end{align*} Here I have neglected the error term, because this has an exact solution (according to Mathematica). A naive inclusion of the derivative of the error term does not, and is the finicky details that I have skipped for this part.Fn. 1 In any case, the exact solution is $$f(j)=\frac{\sqrt{j-1}}{\frac{640\sqrt{5}}{531}-3\left(\tan^{-1}{(\sqrt{j-1})}-\tan^{-1}{(\sqrt{5})}\right)}\leq.698\sqrt{j-1}$$ Thus $$U_k=O(\sqrt{j})$$, the claimed upper bound.

Fn. 1: If you want to make this rigorous, a good place to start is to approximate the derivative of the error term with $$\frac{f(j)}{2j^2}$$. Then there is another exact solution, albeit not exactly in closed form….