I have been playing around with interesting integer sequences and came across [Schröder number](https://en.wikipedia.org/wiki/Schr%C3%B6der_number) which defines the number of lattice paths of n x n grid.


The recurrence formula to calculate these numbers is as follows:


$$
S\_n = 3S\_{n-1} + \sum\_{k=1}^{n-2}S\_kS\_{n-k-1} \text{ for }n\ge2 \text{ with } S\_0 =1, S\_2=2 
$$
The first few numbers in the sequence are:
$$
1, 2, 6, 22, 90, 394, 1806, 8558
$$
I was curious about the following ratio and its limit:
$$
\lim\_{n\rightarrow\infty}\frac{S\_{n-1}}{S\_{n}} = ? 
$$
So I wrote a small C++ program with mixed-precision to handle the large numbers and surprisingly there appears to be an asymptote that is not zero. So far my little program has reached n = 20,000, but it's slowing down significantly as the numbers are getting truly large but it has given a preliminary result of
$$
\lim\_{n\rightarrow\infty}\frac{S\_{n-1}}{S\_{n}} = 0.17158... 
$$


My question now is, is this simply a ghost limit for not having gone far enough, or does a limit exist that is not zero? My math expertise is lacking somewhat to attempt to find that limit analytically (can it even be done?).


If a limit exists would it imply that, for large n, the number of additional lattice paths of a n x n grid only increases by about 17% by expanding the grid by 1?


Code for anyone who wants to try it for themselves:



```
#include <iostream>
#include <gmp.h>
#include <gmpxx.h>
#include <vector>

void schroder(std::vector<mpz_class>& n_vec);

int main(int argc, char **argv)
{   
    int n=2;
    int n_max;
    std::cout << "Enter n_max: ";
    std::cin >> n_max;
    std::vector<mpz_class> s = {mpz_class(1), mpz_class(2)};
    while (n<n_max){
        mpq_class div (s[s.size()-2],s.back());
        gmp_printf ("%d\t %.*Ff\n", n, 100, mpf_class(div,500));
        schroder(s);
        n++;
    }
    return 0;
}

void schroder(std::vector<mpz_class>& n_vec){
    int n = n_vec.size();
    mpz_class sum = mpz_class(0);
    for(int k = 1; k<=(n-2); k++){
        sum += n_vec[k]*n_vec[n-k-1];
    }
    sum += 3*n_vec[n-1];
    n_vec.push_back(sum);
}

```


Limit of the Schröder numbers ratio
The g.f. of these numbers (see the link) is $\sum\_{n=0}^\infty S\_nx^n=\frac{1-x-\sqrt{1-6x+x^2}}{2x}$. Thus radius of convergence is the same of the radical, that is the modulus of the smaller root of $1-6x+x^2$, which is $3-\sqrt{8}=\lim\_{n\to\infty}\frac{S\_{n-1}}{S\_n}$.


**(edit 12/3/21).** I feel obliged to improve a little this answer. The above argument shows that if the limit of the ratio $S\_{n-1}/S\_{n}$ exists, its value is $3-\sqrt{8}$. However, it is not immediately clear that there should be a limit (e.g. the ratio of coefficients of $\frac {1+ax}{1-x^2}$ alternates between $a $ and $1/a$). Here is an elementary existence argument. From the g.f. one gets the two-term recurrence
$$S\_n=\frac{6n-3}{n+1}S\_{n-1}-\frac{n-2}{n+1}S\_{n-2}$$
So $\rho\_n:=S\_n/S\_{n-1}$ satisfies
$$\cases{\rho\_1=2\\\\\rho\_n=\frac{6n-3}{n+1}-\frac{n-2}{n+1}\frac1{\rho\_{n-1}}.}$$
It follows easily by induction e.g. $1\le \rho\_n\le 6$. Since $x\mapsto-\frac1x$ is increasing we have $ \liminf\_{n\to\infty}(-1/\rho\_{n-1})=-1/{\liminf\_{n\to\infty}\rho\_{n}}$ and $ \limsup\_{n\to\infty}(-1/\rho\_{n-1})=-1/{\limsup\_{n\to\infty}\rho\_{n}}$. Therefore both $\liminf\_{n\to\infty}\rho\_n$ and $\limsup\_{n\to\infty}\rho\_n$ solve the fixed point equation $\lambda=6-\frac1\lambda$; lying in the interval $[1,6]$ they both coincide with $3+\sqrt{8}$, which is therefore the limit. (By a little more computation or more thinking one should be able to prove that $\rho\_n$ in fact increasing).


