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?

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);
}