Theorem 1: Let a(n) be the number of lattice walks from (0,0) to (n,n) using the following Fundamental Steps: {[2, 2], [0, 1], [1, 0], [1, 1]} By the way, the first few terms (starting at n=1), are [3, 14, 71, 379, 2082, 11651, 66051, 378064, 2180037, 12644861] a(n) satisfies the following linear recurrence: (2 + n) a(n) (5 + 2 n) a(n + 1) (3 + n) a(2 + n) 3 (7 + 2 n) a(3 + n) ------------ + ------------------ - ---------------- - -------------------- 4 + n 4 + n 4 + n 4 + n + a(4 + n) = 0 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: / 747 2 1433 269 235 3 | ----- %1 - ---- + ---- %1 + ---- %1 n | 1424 2848 1424 2848 0.5621994221694 %1 |1 + ------------------------------------- | n \ 5171 25419 2 2409 1011 3 ----- + ----- %1 - ----- %1 - ---- %1 45568 22784 11392 5696 + --------------------------------------- 2 n 22167635 8331675 2 6672575 12258965 3\ --------- - -------- %1 - -------- %1 + --------- %1 | 129777664 16222208 16222208 129777664 | / 1/2 + ------------------------------------------------------| / n 3 | / n / 2 3 4 %1 := RootOf(1 + 2 _Z - _Z - 6 _Z + _Z , index = 2) And in pure floating-point, n / 0.12404363 0.01251868 0.01395337\ 0.5621994222 6.105739096 |1. - ---------- + ---------- + ----------| | n 2 3 | \ n n / --------------------------------------------------------------------- 1/2 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: {[2, 2], [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, 7, 27, 116, 532, 2554, 12675, 64507, 334836, 1765833] b(n) satisfies the following linear recurrence (-1 + n) b(n) (1 + 2 n) b(n + 1) (2 + n) b(2 + n) 3 (7 + 2 n) b(3 + n) ------------- + ------------------ - ---------------- - -------------------- 5 + n 5 + n 5 + n 5 + n + b(4 + n) = 0 Skecth of proof: Analogous to the above. This implies, via the Birkhoff-Trijinski-Proincare method, that the the asymptotics of b(n) is: / 2241 2 807 705 3 27 | ---- %1 - ---- %1 - ---- %1 + ---- n | 1424 1424 2848 2848 0.86424720479 %1 |1 + ------------------------------------ | n \ 34115 18075 2 9765 75 3 ----- + ----- %1 - ----- %1 - --- %1 45568 22784 11392 712 + -------------------------------------- 2 n 111836655 5717355 2 651315 6481545 3\ --------- - -------- %1 - -------- %1 + --------- %1 | 129777664 16222208 16222208 129777664 | / 3/2 + ------------------------------------------------------| / n 3 | / n / 2 3 4 %1 := RootOf(1 + 2 _Z - _Z - 6 _Z + _Z , index = 2) Disclaimer: The asymptotics is fully proved and rigorous, but the constant in front is a non-rigorous estimate. And in floating-point, n / 1.127869103 1.11288174 1.15412579\ 0.8642472048 6.105739096 |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.537260927 1.543141677 1.500128267 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.9999999994, 0.9999999981, 0.9999999994, 0.9999999987, 0.9999999994, 0.9999999987, 0.9999999981, 0.9999999994, 0.9999999987, 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 , 38.389, seconds of CPU time.