Limit of the Schröder numbers ratio

Question

I have been playing around with interesting integer sequences and came across Schröder 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);
}

Answer 1

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

Answer 2

Pietro has given the answer, and the easiest way to derive it. I'd like to add that if you type the decimal approximation you have into Wolfram Alpha, it lists the correct answer, $3-\sqrt{8}=3-2\sqrt{2}$, as a possible closed-form.

With a few more correct digits, the OEIS will also suggest the closed-form, although you have to be a bit careful because the first digit is different.