Theorem 1: Let a(n) be the number of lattice walks from (0,0) to (n,n) using the following Fundamental Steps: {[0, 1], [1, 0], [1, 1]} By the way, the first few terms (starting at n=1), are [3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453] a(n) satisfies the following linear recurrence: (1 + n) a(n) 3 (3 + 2 n) a(1 + n) ------------ - -------------------- + a(2 + n) = 0 2 + n 2 + n Skecth of proof: Conjecture a linear rerurrence operator with polynomial coeffs. of the form Q(m,n,MN) annihilating F(m,n), the number of walks from the origin to (m,n) Here M and N are the shift operators in the m- and n- variales: Mf(m,n):=f(m+1,n) ; Nf(m,n):=f(m,n+1). Let P(M,N) be the obvious linear partial recurrence operator with constant coeffs. annihilating F(m,n). Note that conjecturing Q(MN,m,n) takes much longer to do, hence we don't want to bother. Next prove the correctness of Q by taking succesive commutators with P Finally set m=n in Q(MN,m,n) and get an ordinary recurrence for the diagonal a(n):=F(n,n). The recurrence implies, via the Birkhoff-Trijinski-Proincare method that the asymptotics of a(n) is: 1/2 n 0.57268163264710 (3 + 2 2 ) / 1/2 1/2 1/2 \ | 3 2 113 9 2 1545 2 245 | | ------ - 1/4 ---- - ------ --------- - ----| | 32 1024 128 32768 4096| / 1/2 |1 + ------------ + ------------- + ----------------| / n | n 2 3 | / \ n n / n And in pure floating-point, 0.5726816326 5.828427124 / 0.1174174786 0.01091467142 0.00686523295\ / 1/2 |1. - ------------ + ------------- + -------------| / n | n 2 3 | / \ n n / Disclaimer: The asymptotics is fully proved and rigorous, but the constant in front is a non-rigorous estimate. ---------------------------- Theorem 2: Let b(n) be the number of lattice walks from (0,0) to (n,n) using the following Fundamental Steps: {[0, 1], [1, 0], [1, 1]} Staying in the region m>=n>0 (i.e. ballot walks). By the way, the first few terms (starting at n=1), are [2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718] b(n) satisfies the following linear recurrence n b(n) 3 (3 + 2 n) b(1 + n) ------ - -------------------- + b(2 + n) = 0 3 + n 3 + n Skecth of proof: Analogous to the above. This implies, via the Birkhoff-Trijinski-Proincare method, that the the asymptotics of b(n) is: 1/2 n 0.80989413181 (3 + 2 2 ) / 1/2 1/2 1/2 \ | 9 2 665 45 2 12915 2 2415| | - ------ - 3/4 ---- + ------- - ---------- - ----| | 32 1024 128 32768 4096| / 3/2 |1 + -------------- + -------------- + -------------------| / n | n 2 3 | / \ n n / Disclaimer: The asymptotics is fully proved and rigorous, but the constant in front is a non-rigorous estimate. And in floating-point, n / 1.147747564 1.146598518 1.146989995\ 0.8098941318 5.828427124 |1. - ----------- + ----------- - -----------| | n 2 3 | \ n n / ------------------------------------------------------------------------ 3/2 n By dividing the asymptotic expression of b(n) by that of a(n) we get the following Corollary: The asymptotics of the probabibility of a walk that winded up at (n,n) staying in m>=n is: 1.414213562 1.457106781 1.435009694 1 ----------- - ----------- + ----------- + O(----) n 2 3 4 n n n ---------------------------- Just as a check, the last 10 terms of the sequence of ratios of the probabilities to the above asymptotics is before the, 1000 term is: [0.9999999993, 0.9999999993, 0.9999999986, 1.000000000, 0.9999999993, 0.9999999993, 0.9999999993, 0.9999999993, 0.9999999993, 0.9999999993] as you can see, they are pretty close to 1 Disclaimer: The asymptotics is fully proved and rigorous, but the constant in front is a non-rigorous estimate. ---------------------------- The whole thing took , 4.962, seconds of CPU time.