5
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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….

$\endgroup$

You must log in to answer this question.

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