# Show a sequence of sums involving Catalan Numbers converges

Let $C_n$ be the $n$-th Catalan Number and let $\mathcal{O}_{s,j} = {{2s-j-1}\choose{j}} C_{s-j}^2$. Then we want to consider $\mathcal{E}_s = \sum_{j=0}^{s-1} (-1)^j\mathcal{O}_{s,j}$. We want to show that

$$\frac{\mathcal{E}_s}{C_s^2} \to 0 {\text { as }} s\to \infty.$$

Does anyone have any ideas of how to get this result? We check the first 1000 numerically and I believe it to be true.

For some quick background, $C_s^2$ counts a set of link diagrams and $\mathcal{E}_s$ comes from counting a subset this larger set. So, $\frac{\mathcal{E}_s}{C_s^2}$ is a probability and thus positive for all $s$. I am a topologist, so this kind of question is pretty out of my area and any help would be great.

A few of the things we have tried:

1. Bounding above by some "simple" functions (like $\frac{2}{s}$), but we can't get a handle on comparing them to $\mathcal{E}_s$.

2. Bounding above by more complicated function:$$f(s) = \sum_{j=0}^{s-1} (-1)^j \frac{s^{j}}{j!8^j}$$ It turns out that $f(s) = e^{-s/8} \frac{\Gamma(s+1,-s/8) }{\Gamma(s+1)}$ which is the regualized Gamma function, and we know this goes goes to zero. Again, we can't seem to get a handle on showing $f(s)\geq \frac{\mathcal{E}_s}{C_s^2}$.

3. Ratio test for sequences: We tried to show $$\frac{\frac{\mathcal{E}_{s+1}}{C_{s+1}^2} }{\frac{\mathcal{E}_s}{C_s^2} } <1$$ which reduces to the problem $$\frac{\mathcal{E}_{s+1}}{\mathcal{E}_s} <16$$ Here, we thought we could get somewhere but the bounds we need to use to get anywhere end up giving exactly 16, not a value strictly less. Again, for the first 1000, it seems to be no larger than 14, numerically.

So, if anyone happens to know a better way to bound a sum of lots of factorials, I would love to hear about it. Thanks!

• have you search for the sequence $\mathcal{E}_s$ at OEIS? I am afraid that this specific formula is not most suitable for asymptotics, since specific terms for small $j$ are much larger in absolute value than the total sum. – Fedor Petrov Jun 16 '18 at 7:43
• @FedorPetrov Yes, I looked at OEIS but haven't found anything. And I agree, the fact that it is alternating makes this harder. – N. Owad Jun 16 '18 at 7:54
• Maybe it makes sense to describe combinatorially which diagrams you count? – Fedor Petrov Jun 16 '18 at 8:11

## 1 Answer

By 'magic' and a computer (see the book "A=B" by Petkovsek, Wilf and Zeilberger https://www.math.upenn.edu/~wilf/AeqB.html) the numbers $\mathcal{E}_s$ satisfies the recurrence $\sum_{k=0}^3 P_k(s) \mathcal{E}_{s+k} = 0$, with polynomials $P_k$ given by $P_0(s) = 2 s^3+s^2-8 s+5$, $P_1(s) = -26 s^3-93 s^2-82 s-30$, $P_2(s) = -26 s^3-141 s^2-226 s-81$ and $P_3(s) = 2 s^3+17 s^2+40 s+16$. The claim now follows by a result of Poincare: The characteristic equation $2-26 z-26 z^2+2 z^3=0$ has only the simple roots $z_0=-1$, $z_2=7+4\sqrt{3}$ and $z_3=7-4\sqrt{3}$. Poincare now tells us that either $\mathcal{E}_s$ is eventually $0$ (in which case everything is fine!) or $\mathcal{E}_{s+1}/\mathcal{E}_s$ converges to one of the roots $z_i$, $i=1$, $2$ or $3$. Since these are all less than $16 = \lim_{s\rightarrow \infty} C_{s+1}^2/C_s^2$ the result follows.

• Wow. First, thanks! Second, I will try to understand this and this and get back to you. It is very much out of the area I would have looked. – N. Owad Jun 21 '18 at 13:04