5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Jun 16 '18 at 7:43
  • $\begingroup$ @FedorPetrov Yes, I looked at OEIS but haven't found anything. And I agree, the fact that it is alternating makes this harder. $\endgroup$ – N. Owad Jun 16 '18 at 7:54
  • $\begingroup$ Maybe it makes sense to describe combinatorially which diagrams you count? $\endgroup$ – Fedor Petrov Jun 16 '18 at 8:11
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – N. Owad Jun 21 '18 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.