The Number of Ways a Walker Can Walk 2n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a Walker can walk 2n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 2 (1 + 2 n) f(n) - ---------------- + f(n + 1) = 0 n + 1 subject to the initial conditions f(1) = 2 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112, 7648690600760440, 30067266499541040, 118264581564861424] Theorem 2: Let f(n) be as in Theorem 1 The asymptotics of f(n) to order, 10, is n 1/2 / 1 1 5 21 399 869 C 4 (1/n) |1 - --- + ------ + ------- - -------- - --------- + ---------- | 8 n 2 3 4 5 6 \ 128 n 1024 n 32768 n 262144 n 4194304 n 39325 334477 28717403 59697183 \ + ----------- - ------------- - -------------- + ----------------| 7 8 9 10| 33554432 n 2147483648 n 17179869184 n 274877906944 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.5641895835477562869480794515607726 1 The EXACT value of the constant C is probably, ----- 1/2 Pi The whole thing took, 1.518, seconds. In Maple input format, the recurrence, asymptotics, and the constant are -2*(1+2*n)/(n+1)*f(n)+f(n+1) = 0, 4^n*(1/n)^(1/2)*(1-1/8/n+1/128/n^2+5/1024/n^3 -21/32768/n^4-399/262144/n^5+869/4194304/n^6+39325/33554432/n^7-334477/ 2147483648/n^8-28717403/17179869184/n^9+59697183/274877906944/n^10), .564189583\ 5477562869480794515607726, 1/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [0], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [0], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 3 (n + 1) f(n) (2 n + 3) f(n + 1) - -------------- - ------------------ + f(2 + n) = 0 2 + n 2 + n subject to the initial conditions f(1) = 1, f(2) = 3 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819, 18252025766941] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 3 1 135 6699 26397 C 3 (1/n) |1 - ---- + ------ + ------- + --------- - ---------- | 16 n 2 3 4 5 \ 512 n 8192 n 524288 n 8388608 n 7538971 133575585 34669180403 2387986277391 - ------------ - ------------- + --------------- + ---------------- 6 7 8 9 268435456 n 4294967296 n 549755813888 n 8796093022208 n 25615932219423 \ + -------------------| 10| 281474976710656 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.4886025119029199215863846228383 1/2 3 The EXACT value of the constant C is probably, ------- 1/2 2 Pi The whole thing took, 2.516, seconds. In Maple input format, the liner recurrence, asymptotics, and the constant are -3*(n+1)/(2+n)*f(n)-(2*n+3)/(2+n)*f(n+1)+f(2+n) = 0, 3^n*(1/n)^(1/2)*(1-3/16/n+ 1/512/n^2+135/8192/n^3+6699/524288/n^4-26397/8388608/n^5-7538971/268435456/n^6-\ 133575585/4294967296/n^7+34669180403/549755813888/n^8+2387986277391/ 8796093022208/n^9+25615932219423/281474976710656/n^10), .4886025119029199215863\ 846228383, 1/2*3^(1/2)/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-2], [-1], [1], [2]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-2], [-1], [1], [2]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2]} The sequence f(n) satisfies the following recurrence 2 9 (1 + 2 n) (5 n + 8) (n + 1) f(n) (n + 1) (35 n + 91 n + 54) f(n + 1) - ---------------------------------- - 1/2 ------------------------------------ (2 n + 3) (5 n + 3) (2 + n) (2 n + 3) (5 n + 3) (2 + n) + f(2 + n) = 0 subject to the initial conditions f(1) = 0, f(2) = 4 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 4, 6, 36, 100, 430, 1470, 5796, 21336, 82404, 312180, 1203246, 4617756, 17846686, 68974906, 267498660, 1038555024, 4040525320, 15739195680, 61399048036, 239788778760, 937536139764, 3669179504364, 14373144873774, 56350223472600, 221094286028100, 868099633603800, 3410759865958110, 13409152861537860, 52747600247673930] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 41 29 95801 7788291 C 4 (1/n) |1 - ----- + -------- + ---------- + ------------ | 200 n 2 3 4 \ 16000 n 3200000 n 512000000 n 14108761947 10142220151151 14663445680741 - --------------- - ------------------ + ------------------ 5 6 7 512000000000 n 204800000000000 n 327680000000000 n 643820023410408559 1115783652826743043 + ---------------------- - ------------------------ 8 9 2621440000000000000 n 104857600000000000000 n 368456356379669913924933 \ - ----------------------------| 10| 209715200000000000000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.25231325220201600482471495223657 1/2 5 The EXACT value of the constant C is probably, ------- 1/2 5 Pi The whole thing took, 2.422, seconds. In Maple input format, The Number of Ways a Walker Can Walk 2n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a Walker can walk 2n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 2 (1 + 2 n) f(n) - ---------------- + f(n + 1) = 0 n + 1 subject to the initial conditions f(1) = 2 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112, 7648690600760440, 30067266499541040, 118264581564861424] Theorem 2: Let f(n) be as in Theorem 1 The asymptotics of f(n) to order, 10, is n 1/2 / 1 1 5 21 399 869 C 4 (1/n) |1 - --- + ------ + ------- - -------- - --------- + ---------- | 8 n 2 3 4 5 6 \ 128 n 1024 n 32768 n 262144 n 4194304 n 39325 334477 28717403 59697183 \ + ----------- - ------------- - -------------- + ----------------| 7 8 9 10| 33554432 n 2147483648 n 17179869184 n 274877906944 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.5641895835477562869480794515607726 1 The EXACT value of the constant C is probably, ----- 1/2 Pi The whole thing took, 1.518, seconds. In Maple input format, the recurrence, asymptotics, and the constant are -2*(1+2*n)/(n+1)*f(n)+f(n+1) = 0, 4^n*(1/n)^(1/2)*(1-1/8/n+1/128/n^2+5/1024/n^3 -21/32768/n^4-399/262144/n^5+869/4194304/n^6+39325/33554432/n^7-334477/ 2147483648/n^8-28717403/17179869184/n^9+59697183/274877906944/n^10), .564189583\ 5477562869480794515607726, 1/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [0], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [0], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 3 (n + 1) f(n) (2 n + 3) f(n + 1) - -------------- - ------------------ + f(2 + n) = 0 2 + n 2 + n subject to the initial conditions f(1) = 1, f(2) = 3 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819, 18252025766941] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 3 1 135 6699 26397 C 3 (1/n) |1 - ---- + ------ + ------- + --------- - ---------- | 16 n 2 3 4 5 \ 512 n 8192 n 524288 n 8388608 n 7538971 133575585 34669180403 2387986277391 - ------------ - ------------- + --------------- + ---------------- 6 7 8 9 268435456 n 4294967296 n 549755813888 n 8796093022208 n 25615932219423 \ + -------------------| 10| 281474976710656 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.4886025119029199215863846228383 1/2 3 The EXACT value of the constant C is probably, ------- 1/2 2 Pi The whole thing took, 2.516, seconds. In Maple input format, The Number of Ways a Walker Can Walk 2n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a Walker can walk 2n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 2 (1 + 2 n) f(n) - ---------------- + f(n + 1) = 0 n + 1 subject to the initial conditions f(1) = 2 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600, 40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820, 538257874440, 2104098963720, 8233430727600, 32247603683100, 126410606437752, 495918532948104, 1946939425648112, 7648690600760440, 30067266499541040, 118264581564861424] Theorem 2: Let f(n) be as in Theorem 1 The asymptotics of f(n) to order, 10, is n 1/2 / 1 1 5 21 399 869 C 4 (1/n) |1 - --- + ------ + ------- - -------- - --------- + ---------- | 8 n 2 3 4 5 6 \ 128 n 1024 n 32768 n 262144 n 4194304 n 39325 334477 28717403 59697183 \ + ----------- - ------------- - -------------- + ----------------| 7 8 9 10| 33554432 n 2147483648 n 17179869184 n 274877906944 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.5641895835477562869480794515607726 1 The EXACT value of the constant C is probably, ----- 1/2 Pi The whole thing took, 1.518, seconds. In Maple input format, the recurrence, asymptotics, and the constant are -2*(1+2*n)/(n+1)*f(n)+f(n+1) = 0, 4^n*(1/n)^(1/2)*(1-1/8/n+1/128/n^2+5/1024/n^3 -21/32768/n^4-399/262144/n^5+869/4194304/n^6+39325/33554432/n^7-334477/ 2147483648/n^8-28717403/17179869184/n^9+59697183/274877906944/n^10), .564189583\ 5477562869480794515607726, 1/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-1], [0], [1]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-1], [0], [1]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 1], [n[1] + 1]} The sequence f(n) satisfies the following recurrence 3 (n + 1) f(n) (2 n + 3) f(n + 1) - -------------- - ------------------ + f(2 + n) = 0 2 + n 2 + n subject to the initial conditions f(1) = 1, f(2) = 3 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953, 25653, 73789, 212941, 616227, 1787607, 5196627, 15134931, 44152809, 128996853, 377379369, 1105350729, 3241135527, 9513228123, 27948336381, 82176836301, 241813226151, 712070156203, 2098240353907, 6186675630819, 18252025766941] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 3 1 135 6699 26397 C 3 (1/n) |1 - ---- + ------ + ------- + --------- - ---------- | 16 n 2 3 4 5 \ 512 n 8192 n 524288 n 8388608 n 7538971 133575585 34669180403 2387986277391 - ------------ - ------------- + --------------- + ---------------- 6 7 8 9 268435456 n 4294967296 n 549755813888 n 8796093022208 n 25615932219423 \ + -------------------| 10| 281474976710656 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.4886025119029199215863846228383 1/2 3 The EXACT value of the constant C is probably, ------- 1/2 2 Pi The whole thing took, 2.516, seconds. In Maple input format, linear recurrence, asymptotics, and the constant are -9*(1+2*n)*(5*n+8)*(n+1)/(2*n+3)/(5*n+3)/(2+n)*f(n)-1/2*(n+1)*(35*n^2+91*n+54)/ (2*n+3)/(5*n+3)/(2+n)*f(n+1)+f(2+n) = 0, 4^n*(1/n)^(1/2)*(1-41/200/n+29/16000/n ^2+95801/3200000/n^3+7788291/512000000/n^4-14108761947/512000000000/n^5-\ 10142220151151/204800000000000/n^6+14663445680741/327680000000000/n^7+ 643820023410408559/2621440000000000000/n^8-1115783652826743043/ 104857600000000000000/n^9-368456356379669913924933/209715200000000000000000/n^ 10), .25231325220201600482471495223657, 1/5*5^(1/2)/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-2], [-1], [0], [1], [2]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-2], [-1], [0], [1], [2]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2]} The sequence f(n) satisfies the following recurrence (3 n + 8) (2 + n) (n + 1) f(n) (2 + n) f(n + 1) 25/2 ------------------------------ - 5/2 ---------------- (5 + 2 n) (3 n + 5) (n + 3) n + 3 2 (3 n + 8) (19 n + 76 n + 75) f(2 + n) - 1/2 -------------------------------------- + f(n + 3) = 0 (5 + 2 n) (3 n + 5) (n + 3) subject to the initial conditions f(1) = 1, f(2) = 5, f(3) = 19 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 5, 19, 85, 381, 1751, 8135, 38165, 180325, 856945, 4091495, 19611175, 94309099, 454805755, 2198649549, 10651488789, 51698642405, 251345549849, 1223798004815, 5966636799745, 29125608152345, 142330448514875, 696235630761115, 3408895901222375, 16704680297731631, 81922110160246231, 402047529335628805, 1974442362935339179, 9702466477069722035, 47705925773278538281] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 13 19 2197 181923 25043529 C 5 (1/n) |1 - ---- - ------- + --------- + ----------- + ------------- | 80 n 2 3 4 5 \ 2560 n 204800 n 13107200 n 5242880000 n 15149707199 109051231003 9455429292881 - --------------- - ---------------- - ------------------- 6 7 8 838860800000 n 2684354560000 n 1717986918400000 n 5120124152663377 9761115049233194283 \ + -------------------- + ------------------------| 9 10| 27487790694400000 n 21990232555520000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.28209479177387814347403972578039 1 The EXACT value of the constant C is probably, ------- 1/2 2 Pi The whole thing took, 4.843, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 25/2*(3*n+8)*(2+n)*(n+1)/(5+2*n)/(3*n+5)/(n+3)*f(n)-5/2*(2+n)/(n+3)*f(n+1)-1/2* (3*n+8)*(19*n^2+76*n+75)/(5+2*n)/(3*n+5)/(n+3)*f(2+n)+f(n+3) = 0, 5^n*(1/n)^(1/ 2)*(1-13/80/n-19/2560/n^2+2197/204800/n^3+181923/13107200/n^4+25043529/ 5242880000/n^5-15149707199/838860800000/n^6-109051231003/2684354560000/n^7-\ 9455429292881/1717986918400000/n^8+5120124152663377/27487790694400000/n^9+ 9761115049233194283/21990232555520000000/n^10), .282094791773878143474039725780\ 39, 1/2/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-3], [-2], [-1], [1], [2], [3]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-3], [-2], [-1], [1], [2], [3]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3]} The sequence f(n) satisfies the following recurrence 3 2 32 (n + 3) (2 + n) (n + 1) (2058 n + 20335 n + 66857 n + 73300) f(n) ---------------------------------------------------------------------- - 8/3 (11 + 3 n) (10 + 3 n) %1 (n + 4) (2 + n) (n + 3) 4 3 2 (201684 n + 2295356 n + 9540055 n + 16998380 n + 10742400) f(n + 1)/( (11 + 3 n) (10 + 3 n) %1 (n + 4)) - 4/3 (n + 3) ( 5 4 3 2 310758 n + 4313617 n + 23611469 n + 63712598 n + 84804508 n + 44608800) f(2 + n)/((11 + 3 n) (10 + 3 n) %1 (n + 4)) - 2/3 (n + 3) 5 4 3 2 (41160 n + 591920 n + 3361281 n + 9453847 n + 13262292 n + 7512000) f(n + 3)/((11 + 3 n) (10 + 3 n) %1 (n + 4)) + f(n + 4) = 0 3 2 %1 := 2058 n + 14161 n + 32361 n + 24720 subject to the initial conditions f(1) = 0, f(2) = 6, f(3) = 18, f(4) = 122 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 6, 18, 122, 600, 3450, 18914, 107338, 606816, 3466356, 19852470, 114239642, 659275760, 3815952426, 22138925718, 128718762250, 749773729952, 4374616990332, 25561798008252, 149562047056572, 876140945014640, 5138089929141890, 30162194533001982, 177223560630336586, 1042186208178255600, 6133471065749084700, 36122631294796828470, 212883558015780622890, 1255377938982501685680, 7407274765826838484950] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 3 953 65745 165816813 C 6 (1/n) |1 - ---- - --------- + ---------- + ------------- | 16 n 2 3 4 \ 175616 n 2809856 n 8811708416 n 13129272333 75475515350059 1974845568264855 - --------------- - ------------------- - --------------------- 5 6 7 986911342592 n 1547476985184256 n 173317422340636672 n 28577110441642498307 5269775951386091675673 + ------------------------ + -------------------------- 8 9 155292410417210458112 n 17392749966727571308544 n 22457561119360952731525431 \ - ------------------------------| 10| 27271831947828831811796992 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.18467439092237180171851095047443 1/2 1/2 3 7 The EXACT value of the constant C is probably, --------- 1/2 14 Pi The whole thing took, 12.245, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 32*(n+3)*(2+n)*(n+1)*(2058*n^3+20335*n^2+66857*n+73300)/(11+3*n)/(10+3*n)/(2058 *n^3+14161*n^2+32361*n+24720)/(n+4)*f(n)-8/3*(2+n)*(n+3)*(201684*n^4+2295356*n^ 3+9540055*n^2+16998380*n+10742400)/(11+3*n)/(10+3*n)/(2058*n^3+14161*n^2+32361* n+24720)/(n+4)*f(n+1)-4/3*(n+3)*(310758*n^5+4313617*n^4+23611469*n^3+63712598*n ^2+84804508*n+44608800)/(11+3*n)/(10+3*n)/(2058*n^3+14161*n^2+32361*n+24720)/(n +4)*f(2+n)-2/3*(n+3)*(41160*n^5+591920*n^4+3361281*n^3+9453847*n^2+13262292*n+ 7512000)/(11+3*n)/(10+3*n)/(2058*n^3+14161*n^2+32361*n+24720)/(n+4)*f(n+3)+f(n+ 4) = 0, 6^n*(1/n)^(1/2)*(1-3/16/n-953/175616/n^2+65745/2809856/n^3+165816813/ 8811708416/n^4-13129272333/986911342592/n^5-75475515350059/1547476985184256/n^6 -1974845568264855/173317422340636672/n^7+28577110441642498307/ 155292410417210458112/n^8+5269775951386091675673/17392749966727571308544/n^9-\ 22457561119360952731525431/27271831947828831811796992/n^10), .18467439092237180\ 171851095047443, 1/14*3^(1/2)*7^(1/2)/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-3], [-2], [-1], [0], [1], [2], [3]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-3], [-2], [-1], [0], [1], [2], [3]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3] } The sequence f(n) satisfies the following recurrence (4 n + 15) (n + 3) (2 + n) (n + 1) f(n) 343/3 --------------------------------------- (3 n + 7) (4 n + 7) (11 + 3 n) (n + 4) (4 n + 15) (n + 3) (2 + n) (2 n + 7) f(n + 1) + 98/3 --------------------------------------------- (11 + 3 n) (10 + 3 n) (4 n + 11) (n + 4) 3 2 (n + 3) (92 n + 713 n + 1747 n + 1372) f(2 + n) - 14/3 ------------------------------------------------- (3 n + 7) (4 n + 7) (11 + 3 n) (n + 4) 2 (4 n + 15) (2 n + 7) (37 n + 222 n + 332) f(n + 3) - 2/3 --------------------------------------------------- + f(n + 4) = 0 (11 + 3 n) (10 + 3 n) (4 n + 11) (n + 4) subject to the initial conditions f(1) = 1, f(2) = 7, f(3) = 37, f(4) = 231 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 7, 37, 231, 1451, 9331, 60691, 398567, 2636263, 17538157, 117224317, 786588243, 5295520699, 35751527189, 241958082737, 1641010879207, 11150608945863, 75894449584849, 517331384963959, 3531097638576781, 24131083600660801, 165090433568378523, 1130584690737850817, 7749680444394189779, 53165733245153721451, 365021708551987471901, 2507951805925073224087, 17242917306420550496437, 118624166537551760766121, 816560387530443298977031] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 5 137 625 804813 1643205 C 7 (1/n) |1 - ---- - -------- + -------- + ----------- + ------------ | 32 n 2 3 4 5 \ 14336 n 65536 n 58720256 n 268435456 n 12826560571 1078446172375 122840897615293 - --------------- - ----------------- - ------------------- 6 7 8 841813590016 n 26938034880512 n 6896136929411072 n 34104303550067465 45385385017417560921 \ + --------------------- + ------------------------| 9 10| 220676381741154304 n 98863019020037128192 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.1994711402007163389699730299671909 1/2 2 The EXACT value of the constant C is probably, ------- 1/2 4 Pi The whole thing took, 12.148, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 343/3*(4*n+15)*(n+3)*(2+n)*(n+1)/(3*n+7)/(4*n+7)/(11+3*n)/(n+4)*f(n)+98/3*(4*n+ 15)*(n+3)*(2+n)*(2*n+7)/(11+3*n)/(10+3*n)/(4*n+11)/(n+4)*f(n+1)-14/3*(n+3)*(92* n^3+713*n^2+1747*n+1372)/(3*n+7)/(4*n+7)/(11+3*n)/(n+4)*f(2+n)-2/3*(4*n+15)*(2* n+7)*(37*n^2+222*n+332)/(11+3*n)/(10+3*n)/(4*n+11)/(n+4)*f(n+3)+f(n+4) = 0, 7^n *(1/n)^(1/2)*(1-5/32/n-137/14336/n^2+625/65536/n^3+804813/58720256/n^4+1643205/ 268435456/n^5-12826560571/841813590016/n^6-1078446172375/26938034880512/n^7-\ 122840897615293/6896136929411072/n^8+34104303550067465/220676381741154304/n^9+ 45385385017417560921/98863019020037128192/n^10), .19947114020071633896997302996\ 71909, 1/4*2^(1/2)/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-4], [-3], [-2], [-1], [1], [2], [3], [4]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-4], [-3], [-2], [-1], [1], [2], [3], [4]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4]} The sequence f(n) satisfies the following recurrence 6 5 4 250 (1 + 2 n) (n + 3) (2 + n) (n + 1) (590490 n + 10294209 n + 73841139 n 3 2 + 278492823 n + 581155731 n + 634270728 n + 281620400) f(n)/((2 n + 7) 8 (4 n + 13) (4 n + 15) %1 (n + 4)) - 25/2 (n + 3) (2 + n) (59639490 n 7 6 5 4 + 1158994089 n + 9580884687 n + 43800670782 n + 120380601159 n 3 2 + 201953552937 n + 199458267352 n + 103876375184 n + 20951680000) f(n + 1)/((2 n + 7) (4 n + 13) (4 n + 15) %1 (n + 4)) - 3/4 (n + 3) ( 9 8 7 6 847943640 n + 18598230504 n + 177627099717 n + 967328166564 n 5 4 3 + 3300256419255 n + 7284869470356 n + 10341441698548 n 2 + 9019123532576 n + 4315584119840 n + 836790800000) f(2 + n)/((2 n + 7) 9 (4 n + 13) (4 n + 15) %1 (n + 4)) - 1/8 (n + 3) (484792290 n 8 7 6 5 + 10875507039 n + 106242549291 n + 591929233839 n + 2067126888663 n 4 3 2 + 4674813694170 n + 6809429327836 n + 6108620618552 n + 3018866760320 n + 609545200000) f(n + 3)/((2 n + 7) (4 n + 13) (4 n + 15) %1 (n + 4)) + f(n + 4) = 0 6 5 4 3 2 %1 := 590490 n + 6751269 n + 31227444 n + 74260557 n + 94639356 n + 60001284 n + 14150000 subject to the initial conditions f(1) = 0, f(2) = 8, f(3) = 36, f(4) = 296 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 8, 36, 296, 2030, 15200, 112308, 845320, 6386076, 48582438, 371138460, 2846769992, 21905812786, 169041544568, 1307602672376, 10136307859080, 78721657307320, 612391634798156, 4770987007606224, 37219155177139126, 290702353768374570, 2273036878855399720, 17790932071581562960, 139376267795178244840, 1092810544290005150780, 8575087408892543742250, 67335600891215041025940, 529103953407304881762480, 4160133438992441971225830, 32728449212901218186996100] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 107 131 1700243 263942161 C 8 (1/n) |1 - ----- - -------- + ----------- + -------------- | 600 n 2 3 4 \ 16000 n 86400000 n 13824000000 n 29094297827 711624382419071 12780593619104597 - ---------------- - -------------------- - --------------------- 5 6 7 4608000000000 n 16588800000000000 n 398131200000000000 n 80807775848107882717 246646674357453081126701 + ------------------------ + --------------------------- 8 9 637009920000000000000 n 687970713600000000000000 n 1050222589276797928073266639 \ - --------------------------------| 10| 4127824281600000000000000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.14567312407894387607245142744036 1/2 1/2 3 5 The EXACT value of the constant C is probably, --------- 1/2 15 Pi The whole thing took, 17.597, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 250*(1+2*n)*(n+3)*(2+n)*(n+1)*(590490*n^6+10294209*n^5+73841139*n^4+278492823*n ^3+581155731*n^2+634270728*n+281620400)/(2*n+7)/(4*n+13)/(4*n+15)/(590490*n^6+ 6751269*n^5+31227444*n^4+74260557*n^3+94639356*n^2+60001284*n+14150000)/(n+4)*f (n)-25/2*(n+3)*(2+n)*(59639490*n^8+1158994089*n^7+9580884687*n^6+43800670782*n^ 5+120380601159*n^4+201953552937*n^3+199458267352*n^2+103876375184*n+20951680000 )/(2*n+7)/(4*n+13)/(4*n+15)/(590490*n^6+6751269*n^5+31227444*n^4+74260557*n^3+ 94639356*n^2+60001284*n+14150000)/(n+4)*f(n+1)-3/4*(n+3)*(847943640*n^9+ 18598230504*n^8+177627099717*n^7+967328166564*n^6+3300256419255*n^5+ 7284869470356*n^4+10341441698548*n^3+9019123532576*n^2+4315584119840*n+ 836790800000)/(2*n+7)/(4*n+13)/(4*n+15)/(590490*n^6+6751269*n^5+31227444*n^4+ 74260557*n^3+94639356*n^2+60001284*n+14150000)/(n+4)*f(2+n)-1/8*(n+3)*( 484792290*n^9+10875507039*n^8+106242549291*n^7+591929233839*n^6+2067126888663*n ^5+4674813694170*n^4+6809429327836*n^3+6108620618552*n^2+3018866760320*n+ 609545200000)/(2*n+7)/(4*n+13)/(4*n+15)/(590490*n^6+6751269*n^5+31227444*n^4+ 74260557*n^3+94639356*n^2+60001284*n+14150000)/(n+4)*f(n+3)+f(n+4) = 0, 8^n*(1/ n)^(1/2)*(1-107/600/n-131/16000/n^2+1700243/86400000/n^3+263942161/13824000000/ n^4-29094297827/4608000000000/n^5-711624382419071/16588800000000000/n^6-\ 12780593619104597/398131200000000000/n^7+80807775848107882717/ 637009920000000000000/n^8+246646674357453081126701/687970713600000000000000/n^9 -1050222589276797928073266639/4127824281600000000000000000/n^10), .145673124078\ 94387607245142744036, 1/15*3^(1/2)*5^(1/2)/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-4], [-3], [-2], [-1], [0], [1], [2], [3], [4]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-4], [-3], [-2], [-1], [0], [1], [2], [3], [4]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4]} The sequence f(n) satisfies the following recurrence (5 n + 23) (5 n + 24) (n + 4) (n + 3) (2 + n) (n + 1) f(n) -6561/8 ----------------------------------------------------------- (5 n + 9) (4 n + 9) (5 n + 18) (4 n + 19) (2 n + 9) (n + 5) (5 n + 24) (n + 4) (n + 3) (2 + n) f(n + 1) + 729/4 ------------------------------------------- + 81/4 (n + 3) (n + 4) (4 n + 13) (5 n + 14) (4 n + 19) (n + 5) 4 3 2 (5 n + 24) (5 n + 23) (1020 n + 12291 n + 53378 n + 98617 n + 65610) f(2 + n)/((5 n + 9) (4 n + 9) (5 n + 19) (5 n + 18) (4 n + 17) (2 n + 9) (4 n + 19) (n + 5)) 3 2 (n + 4) (385 n + 4158 n + 14551 n + 16610) f(n + 3) - 9/4 ----------------------------------------------------- - 1/8 (4 n + 13) (5 n + 14) (4 n + 19) (n + 5) 4 3 2 (5 n + 24) (5 n + 23) (2101 n + 33616 n + 201391 n + 535416 n + 532980) f(n + 4)/((5 n + 19) (5 n + 18) (4 n + 17) (2 n + 9) (4 n + 19) (n + 5)) + f(n + 5) = 0 subject to the initial conditions f(1) = 1, f(2) = 9, f(3) = 61, f(4) = 489, f(5) = 3951 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 9, 61, 489, 3951, 32661, 273127, 2306025, 19610233, 167729959, 1441383219, 12434998005, 107632809909, 934263293679, 8129320828911, 70886845397481, 619288973447049, 5419332253680705, 47494787636620701, 416800775902696839, 3662161978416490939, 32212526912248307931, 283627506404162039271, 2499606098574955160949, 22047648502770689947701, 194622024550324520246301, 1719235712363783937083809, 15197425936677897059912911, 134423628499938116929872519, 1189690477065303570011101111] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 123 2659 1860867 1782020163 C 9 (1/n) |1 - ----- - --------- + ------------ + --------------- | 800 n 2 3 4 \ 256000 n 204800000 n 131072000000 n 3458879577279 11841192727616879 1061854906098400557 + ------------------ - --------------------- - ----------------------- 5 6 7 524288000000000 n 838860800000000000 n 26843545600000000000 n 3797244943498426255121 3894357855827688165981207 - --------------------------- + ----------------------------- 8 9 171798691840000000000000 n 27487790694400000000000000 n 100887317398367351944027181883 \ + ----------------------------------| 10| 219902325555200000000000000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.154509680809275832136877094124596 1/2 1/2 1/2 2 3 5 The EXACT value of the constant C is probably, -------------- 1/2 20 Pi The whole thing took, 32.162, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are -6561/8*(5*n+23)*(5*n+24)*(n+4)*(n+3)*(2+n)*(n+1)/(5*n+9)/(4*n+9)/(5*n+18)/(4*n +19)/(2*n+9)/(n+5)*f(n)+729/4*(5*n+24)*(n+4)*(n+3)*(2+n)/(4*n+13)/(5*n+14)/(4*n +19)/(n+5)*f(n+1)+81/4*(n+3)*(n+4)*(5*n+24)*(5*n+23)*(1020*n^4+12291*n^3+53378* n^2+98617*n+65610)/(5*n+9)/(4*n+9)/(5*n+19)/(5*n+18)/(4*n+17)/(2*n+9)/(4*n+19)/ (n+5)*f(2+n)-9/4*(n+4)*(385*n^3+4158*n^2+14551*n+16610)/(4*n+13)/(5*n+14)/(4*n+ 19)/(n+5)*f(n+3)-1/8*(5*n+24)*(5*n+23)*(2101*n^4+33616*n^3+201391*n^2+535416*n+ 532980)/(5*n+19)/(5*n+18)/(4*n+17)/(2*n+9)/(4*n+19)/(n+5)*f(n+4)+f(n+5) = 0, 9^ n*(1/n)^(1/2)*(1-123/800/n-2659/256000/n^2+1860867/204800000/n^3+1782020163/ 131072000000/n^4+3458879577279/524288000000000/n^5-11841192727616879/ 838860800000000000/n^6-1061854906098400557/26843545600000000000/n^7-\ 3797244943498426255121/171798691840000000000000/n^8+3894357855827688165981207/ 27487790694400000000000000/n^9+100887317398367351944027181883/ 219902325555200000000000000000/n^10), .154509680809275832136877094124596, 1/20* 2^(1/2)*3^(1/2)*5^(1/2)/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5]} The sequence f(n) satisfies the following recurrence 10 - 2160 (n + 5) (n + 4) (n + 3) (2 + n) (n + 1) (87538808028375 n 9 8 7 + 4002380410703400 n + 81955873844506200 n + 989608377181885802 n 6 5 + 7802233944425769849 n + 41962911625841325218 n 4 3 + 155902882358890026360 n + 395061358449703688732 n 2 + 653466117095752200768 n + 637166705074404840720 n + 278161692909090520320) f(n)/((n + 6) (5 n + 28) (5 n + 29) (5 n + 26) 11 (5 n + 27) %1) + 72 (2 + n) (n + 3) (n + 4) (n + 5) (63553174628600250 n 10 9 + 3001057940113568775 n + 63858413433045275550 n 8 7 + 807698886949652446452 n + 6741965985707748074862 n 6 5 + 38960039075732000899541 n + 158870341693298245166794 n 4 3 + 456527822341269247338088 n + 904417753345001493510440 n 2 + 1173725728826505469282800 n + 895203480128379305304960 n + 302566182692409086976000) f(n + 1)/((n + 6) (5 n + 28) (5 n + 29) (5 n + 26) (5 n + 27) %1) - 12/5 (n + 3) (n + 4) (n + 5) ( 12 11 1195692578859574125 n + 59451284345236037100 n 10 9 + 1342254028946947162200 n + 18183898942042911748968 n 8 7 + 164503091625962494474773 n + 1046018262938853900142546 n 6 5 + 4788520451157608708358288 n + 15880172528370343158734098 n 4 3 + 37798007931461088678890094 n + 62826940754970842764937128 n 2 + 68999159028174459597381960 n + 44741034408913641009489600 n + 12858290700324839336448000) f(2 + n)/((n + 6) (5 n + 28) (5 n + 29) 13 (5 n + 26) (5 n + 27) %1) - 2/5 (n + 4) (n + 5) (19190782728828537750 n 12 11 + 1021356718383077601525 n + 24892453373469077302500 n 10 9 + 367734384328842602888927 n + 3672613643528501817673176 n 8 7 + 26175475851943744973665359 n + 136916115477983564622575808 n 6 5 + 531943103910595275276094101 n + 1534350584196409025374763094 n 4 3 + 3243505709947963161808194616 n + 4881471536691546228342145272 n 2 + 4949725946789193201392607792 n + 3028443835181378152781934720 n + 843619246243815658208256000) f(n + 3)/((n + 6) (5 n + 28) (5 n + 29) 14 (5 n + 26) (5 n + 27) %1) - 6/5 (n + 5) (2563661531918990250 n 13 12 + 147977651090887655400 n + 3939954235656807714225 n 11 10 + 64121867686995203949622 n + 712460919002216451099637 n 9 8 + 5715702042757107882682256 n + 34133510593314956364782131 n 7 6 + 154105213648276916565159730 n + 528416899353217872602949025 n 5 4 + 1369082829514674275504805984 n + 2637741083274638817230516604 n 3 2 + 3663807675134425957295048288 n + 3467759162188557362835745728 n + 2001910119523167835482117120 n + 531888603381381086733312000) f(n + 4)/( (n + 6) (5 n + 28) (5 n + 29) (5 n + 26) (5 n + 27) %1) - 6/5 (n + 5) ( 14 13 133584221051300250 n + 7777435269874641525 n 12 11 + 208849636239832374600 n + 3427847332808427796652 n 10 9 + 38409465373094896719155 n + 310758728659352779699861 n 8 7 + 1871808961956777873237670 n + 8525614373185671879304990 n 6 5 + 29504396667300602490233065 n + 77200599917666086041135164 n 4 3 + 150361001024243667286384220 n + 211444739380921753829050608 n 2 + 203063757034689011688522240 n + 119326374464386900898304000 n + 32418797141073522880512000) f(n + 5)/((n + 6) (5 n + 28) (5 n + 29) (5 n + 26) (5 n + 27) %1) + f(n + 6) = 0 10 9 8 %1 := 87538808028375 n + 3126992330419650 n + 49873696509452475 n 7 6 5 + 467542424247753602 n + 2851922966985615985 n + 11823995096939438666 n 4 3 + 33736534581756709285 n + 65406725947650774962 n 2 + 82476570906357114520 n + 61114928944236604800 n + 20230383813268608000 subject to the initial conditions f(1) = 0, f(2) = 10, f(3) = 60, f(4) = 590, f(5) = 5150, f(6) = 47812 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 10, 60, 590, 5150, 47812, 442960, 4161710, 39318000, 373790790, 3569522506, 34221892628, 329163295890, 3174973369620, 30698835183380, 297457926825006, 2887628268740160, 28078790548057276, 273438943730755320, 2666381597968444830, 26032064444141609032, 254431764615331779882, 2489251564256002459254, 24376118508719139208916, 238905738723898246924400, 2343292771917764537500510, 23000607339188098776916110, 225913603081906996745947740, 2220320498819103775680183150, 21834390067717940657789005512] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 19 23 36991 2412039 C 10 (1/n) |1 - ----- - ------- + ---------- + ------------ | 110 n 2 3 4 \ 2420 n 2129600 n 128840800 n 128096031 1717193415403 4042470725917 - -------------- - ----------------- - ----------------- 5 6 7 51536320000 n 45351961600000 n 99774315520000 n 21530499274153259 1362970590933090269 + --------------------- + ---------------------- 8 9 241453843558400000 n 3863261496934400000 n 1043265702538733105523 \ + ---------------------------| 10| 23372732056453120000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.12028562337275516340290432680226 The whole thing took, 82.729, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are -2160*(n+5)*(n+4)*(n+3)*(2+n)*(n+1)*(87538808028375*n^10+4002380410703400*n^9+ 81955873844506200*n^8+989608377181885802*n^7+7802233944425769849*n^6+ 41962911625841325218*n^5+155902882358890026360*n^4+395061358449703688732*n^3+ 653466117095752200768*n^2+637166705074404840720*n+278161692909090520320)/(n+6)/ (5*n+28)/(5*n+29)/(5*n+26)/(5*n+27)/(87538808028375*n^10+3126992330419650*n^9+ 49873696509452475*n^8+467542424247753602*n^7+2851922966985615985*n^6+ 11823995096939438666*n^5+33736534581756709285*n^4+65406725947650774962*n^3+ 82476570906357114520*n^2+61114928944236604800*n+20230383813268608000)*f(n)+72*( 2+n)*(n+3)*(n+4)*(n+5)*(63553174628600250*n^11+3001057940113568775*n^10+ 63858413433045275550*n^9+807698886949652446452*n^8+6741965985707748074862*n^7+ 38960039075732000899541*n^6+158870341693298245166794*n^5+ 456527822341269247338088*n^4+904417753345001493510440*n^3+ 1173725728826505469282800*n^2+895203480128379305304960*n+ 302566182692409086976000)/(n+6)/(5*n+28)/(5*n+29)/(5*n+26)/(5*n+27)/( 87538808028375*n^10+3126992330419650*n^9+49873696509452475*n^8+ 467542424247753602*n^7+2851922966985615985*n^6+11823995096939438666*n^5+ 33736534581756709285*n^4+65406725947650774962*n^3+82476570906357114520*n^2+ 61114928944236604800*n+20230383813268608000)*f(n+1)-12/5*(n+3)*(n+4)*(n+5)*( 1195692578859574125*n^12+59451284345236037100*n^11+1342254028946947162200*n^10+ 18183898942042911748968*n^9+164503091625962494474773*n^8+ 1046018262938853900142546*n^7+4788520451157608708358288*n^6+ 15880172528370343158734098*n^5+37798007931461088678890094*n^4+ 62826940754970842764937128*n^3+68999159028174459597381960*n^2+ 44741034408913641009489600*n+12858290700324839336448000)/(n+6)/(5*n+28)/(5*n+29 )/(5*n+26)/(5*n+27)/(87538808028375*n^10+3126992330419650*n^9+49873696509452475 *n^8+467542424247753602*n^7+2851922966985615985*n^6+11823995096939438666*n^5+ 33736534581756709285*n^4+65406725947650774962*n^3+82476570906357114520*n^2+ 61114928944236604800*n+20230383813268608000)*f(2+n)-2/5*(n+4)*(n+5)*( 19190782728828537750*n^13+1021356718383077601525*n^12+24892453373469077302500*n ^11+367734384328842602888927*n^10+3672613643528501817673176*n^9+ 26175475851943744973665359*n^8+136916115477983564622575808*n^7+ 531943103910595275276094101*n^6+1534350584196409025374763094*n^5+ 3243505709947963161808194616*n^4+4881471536691546228342145272*n^3+ 4949725946789193201392607792*n^2+3028443835181378152781934720*n+ 843619246243815658208256000)/(n+6)/(5*n+28)/(5*n+29)/(5*n+26)/(5*n+27)/( 87538808028375*n^10+3126992330419650*n^9+49873696509452475*n^8+ 467542424247753602*n^7+2851922966985615985*n^6+11823995096939438666*n^5+ 33736534581756709285*n^4+65406725947650774962*n^3+82476570906357114520*n^2+ 61114928944236604800*n+20230383813268608000)*f(n+3)-6/5*(n+5)*( 2563661531918990250*n^14+147977651090887655400*n^13+3939954235656807714225*n^12 +64121867686995203949622*n^11+712460919002216451099637*n^10+ 5715702042757107882682256*n^9+34133510593314956364782131*n^8+ 154105213648276916565159730*n^7+528416899353217872602949025*n^6+ 1369082829514674275504805984*n^5+2637741083274638817230516604*n^4+ 3663807675134425957295048288*n^3+3467759162188557362835745728*n^2+ 2001910119523167835482117120*n+531888603381381086733312000)/(n+6)/(5*n+28)/(5*n +29)/(5*n+26)/(5*n+27)/(87538808028375*n^10+3126992330419650*n^9+ 49873696509452475*n^8+467542424247753602*n^7+2851922966985615985*n^6+ 11823995096939438666*n^5+33736534581756709285*n^4+65406725947650774962*n^3+ 82476570906357114520*n^2+61114928944236604800*n+20230383813268608000)*f(n+4)-6/ 5*(n+5)*(133584221051300250*n^14+7777435269874641525*n^13+208849636239832374600 *n^12+3427847332808427796652*n^11+38409465373094896719155*n^10+ 310758728659352779699861*n^9+1871808961956777873237670*n^8+ 8525614373185671879304990*n^7+29504396667300602490233065*n^6+ 77200599917666086041135164*n^5+150361001024243667286384220*n^4+ 211444739380921753829050608*n^3+203063757034689011688522240*n^2+ 119326374464386900898304000*n+32418797141073522880512000)/(n+6)/(5*n+28)/(5*n+ 29)/(5*n+26)/(5*n+27)/(87538808028375*n^10+3126992330419650*n^9+ 49873696509452475*n^8+467542424247753602*n^7+2851922966985615985*n^6+ 11823995096939438666*n^5+33736534581756709285*n^4+65406725947650774962*n^3+ 82476570906357114520*n^2+61114928944236604800*n+20230383813268608000)*f(n+5)+f( n+6) = 0, 10^n*(1/n)^(1/2)*(1-19/110/n-23/2420/n^2+36991/2129600/n^3+2412039/ 128840800/n^4-128096031/51536320000/n^5-1717193415403/45351961600000/n^6-\ 4042470725917/99774315520000/n^7+21530499274153259/241453843558400000/n^8+ 1362970590933090269/3863261496934400000/n^9+1043265702538733105523/ 23372732056453120000000/n^10), .12028562337275516340290432680226, .120285623372\ 75516340290432680226 ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5]} The sequence f(n) satisfies the following recurrence -161051/5 (6 n + 35) (3 n + 17) (n + 5) (n + 4) (n + 3) (2 + n) (n + 1) f(n) ------------------------------------------------------------------------- (6 n + 11) (5 n + 11) (11 + 3 n) (5 n + 22) (5 n + 29) (5 n + 28) (n + 6) - 43923/5 (3 n + 17) (2 n + 11) (n + 5) (n + 4) (n + 3) (2 + n) (6 n + 35) f(n + 1) ------------------------------------------------------------------------- (6 n + 17) (5 n + 16) (3 n + 14) (5 n + 28) (5 n + 29) (5 n + 27) (n + 6) + 3993/5 (6 n + 35) (n + 5) (n + 4) (n + 3) 5 4 3 2 (5310 n + 93987 n + 639414 n + 2083769 n + 3243964 n + 1932612) f(2 + n)/((6 n + 11) (5 n + 11) (6 n + 23) (11 + 3 n) (5 n + 22) (5 n + 21) (5 n + 29) (5 n + 28) (n + 6)) + 726/5 (3 n + 17) (2 n + 11) (n + 5) 4 3 2 (n + 4) (6 n + 35) (2280 n + 36556 n + 215051 n + 549471 n + 515106) f(n + 3)/((6 n + 17) (5 n + 16) (6 n + 29) (3 n + 14) (5 n + 28) (5 n + 29) 6 5 (5 n + 26) (5 n + 27) (n + 6)) - 33/5 (n + 5) (45306 n + 1245915 n 4 3 2 + 14180051 n + 85511395 n + 288246449 n + 515106660 n + 381363444) f(n + 4)/((6 n + 23) (11 + 3 n) (5 n + 22) (5 n + 21) (5 n + 29) (5 n + 28) (n + 6)) - 3/5 (2 n + 11) (6 n + 35) (3 n + 17) 4 3 2 (4651 n + 93020 n + 697195 n + 2320950 n + 2895504) f(n + 5)/((6 n + 29) (3 n + 14) (5 n + 28) (5 n + 29) (5 n + 26) (5 n + 27) (n + 6)) + f(n + 6) = 0 subject to the initial conditions f(1) = 1, f(2) = 11, f(3) = 91, f(4) = 891, f(5) = 8801, f(6) = 88913 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 11, 91, 891, 8801, 88913, 908755, 9377467, 97464799, 1018872811, 10701243741, 112835748609, 1193692544825, 12663809507129, 134678108144591, 1435345208419771, 15326122342137035, 163920458145421109, 1755827928017942009, 18832730699014127291, 202241945258525688901, 2174240094816618130071, 23398077407041190525419, 252030215173274181382849, 2717018502236839434316301, 29313768793598293742720851, 316493291684554275734062111, 3419389614573083876443358761, 36966104147456328795085870751, 399863362252518237789973723213] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 61 691 226981 1219443393 C 11 (1/n) |1 - ----- - -------- + ----------- + -------------- | 400 n 2 3 4 \ 64000 n 25600000 n 90112000000 n 111779436153 177722299344671 8236001659307851 + ----------------- - -------------------- - --------------------- 5 6 7 16384000000000 n 13107200000000000 n 209715200000000000 n 177992404385367380731 79873597786284713867339 - ------------------------- + --------------------------- 8 9 7381975040000000000000 n 590558003200000000000000 n 1080520455496505503040916537 \ + --------------------------------| 10| 2362232012800000000000000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.126156626101008002412357476118284 1/2 5 The EXACT value of the constant C is probably, -------- 1/2 10 Pi The whole thing took, 86.395, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are -161051/5*(6*n+35)*(3*n+17)*(n+5)*(n+4)*(n+3)*(2+n)*(n+1)/(6*n+11)/(5*n+11)/(11 +3*n)/(5*n+22)/(5*n+29)/(5*n+28)/(n+6)*f(n)-43923/5*(3*n+17)*(2*n+11)*(n+5)*(n+ 4)*(n+3)*(2+n)*(6*n+35)/(6*n+17)/(5*n+16)/(3*n+14)/(5*n+28)/(5*n+29)/(5*n+27)/( n+6)*f(n+1)+3993/5*(6*n+35)*(n+5)*(n+4)*(n+3)*(5310*n^5+93987*n^4+639414*n^3+ 2083769*n^2+3243964*n+1932612)/(6*n+11)/(5*n+11)/(6*n+23)/(11+3*n)/(5*n+22)/(5* n+21)/(5*n+29)/(5*n+28)/(n+6)*f(2+n)+726/5*(3*n+17)*(2*n+11)*(n+5)*(n+4)*(6*n+ 35)*(2280*n^4+36556*n^3+215051*n^2+549471*n+515106)/(6*n+17)/(5*n+16)/(6*n+29)/ (3*n+14)/(5*n+28)/(5*n+29)/(5*n+26)/(5*n+27)/(n+6)*f(n+3)-33/5*(n+5)*(45306*n^6 +1245915*n^5+14180051*n^4+85511395*n^3+288246449*n^2+515106660*n+381363444)/(6* n+23)/(11+3*n)/(5*n+22)/(5*n+21)/(5*n+29)/(5*n+28)/(n+6)*f(n+4)-3/5*(2*n+11)*(6 *n+35)*(3*n+17)*(4651*n^4+93020*n^3+697195*n^2+2320950*n+2895504)/(6*n+29)/(3*n +14)/(5*n+28)/(5*n+29)/(5*n+26)/(5*n+27)/(n+6)*f(n+5)+f(n+6) = 0, 11^n*(1/n)^(1 /2)*(1-61/400/n-691/64000/n^2+226981/25600000/n^3+1219443393/90112000000/n^4+ 111779436153/16384000000000/n^5-177722299344671/13107200000000000/n^6-\ 8236001659307851/209715200000000000/n^7-177992404385367380731/ 7381975040000000000000/n^8+79873597786284713867339/590558003200000000000000/n^9 +1080520455496505503040916537/2362232012800000000000000000/n^10), .126156626101\ 008002412357476118284, 1/10*5^(1/2)/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-6], [-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5], [6]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-6], [-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5], [6]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 6], [n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5], [n[1] + 6]} The sequence f(n) satisfies the following recurrence - 7203 (2 n + 1) (n + 5) (n + 4) (n + 3) (2 + n) (n + 1) ( 15 14 474032555203494500577 n + 29990806935804970747128 n 13 12 + 880035660332566420022340 n + 15883433335321259718129236 n 11 10 + 197136873624906917566429383 n + 1781694545071855438287922048 n 9 8 + 12109083624307220545159358895 n + 62994219211921044547485935274 n 7 6 + 252795711312140895717434113836 n + 782169723956892922603092736492 n 5 4 + 1849631049668931288482157812325 n + 3280658964696467348762669367830 n 3 2 + 4221419961025345716129204682164 n + 3716694303634508818493298058632 n + 1999693279339972603489896786720 n + 494886312284081187129276153600) f(n) /((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) %1) + 17 343/6 (n + 5) (n + 4) (n + 3) (2 + n) (940954622078936583645345 n 16 15 + 61413661011730740100339770 n + 1866633304994001692193216990 n 14 13 + 35066572160375192693219049736 n + 455671162374757135863796184471 n 12 + 4342708261720654097256500840948 n 11 + 31400416444276647707227998492757 n 10 + 175742680937651126065394474429778 n 9 + 769736077239286561250383581493800 n 8 + 2649077658892797240312369999223286 n 7 + 7149510259550636756885708717192233 n 6 + 15008903383835588968697638008415738 n 5 + 24133160663176269982616354355878564 n 4 + 28980210226721535166579209450322056 n 3 + 24960911072795703531774306090845280 n 2 + 14415732314762543016493992951187008 n + 4923460673840322668884144845761280 n + 732939107160952648703444831078400 ) f(n + 1)/((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) 49 18 %1) - -- (n + 3) (n + 4) (n + 5) (2405241185102531095927698 n 36 17 16 + 162996939725235811502602113 n + 5156561424962735761696568664 n 15 14 + 101089421683255118493994686410 n + 1374562489612390921188764335164 n 13 + 13747654122210041198039206192601 n 12 + 104634318211942088823022765851804 n 11 + 618376738164019449560831271867221 n 10 + 2869120075048857689468130933347604 n 9 + 10493215583691357485057941047631942 n 8 + 30183409599273952865258536966844688 n 7 + 67688298602072915730850033243704361 n 6 + 116362520445243705667548456839384826 n 5 + 149023668483552466359444906098897704 n 4 + 135441198399111703522588725019003584 n 3 + 79755557734936492792743933527899248 n 2 + 24328579728926812497712980929905248 n + 446727856794543594371244119518080 n - 1234348678514937167340365325081600 ) f(2 + n)/((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) 19 %1) - 1/12 (n + 4) (n + 5) (636645631005611661043935234 n 18 17 + 45372078376722272810515765248 n + 1517981277877548737595037283133 n 16 + 31676698689184303792113176791080 n 15 + 462008133154872122705136320451680 n 14 + 5001435988182873604308029862152234 n 13 + 41649710781324479388605566263291115 n 12 + 272849537561564344595497128508727194 n 11 + 1425847020361230661535579789020756689 n 10 + 5990856607224978045980576494777490652 n 9 + 20300664393673377626444311543063670344 n 8 + 55411293099483782315987509497149507530 n 7 + 121145699736402053038910919287956061669 n 6 + 209900987895478809349318823731636436750 n 5 + 283338571758556199712071260004735054088 n 4 + 290273689839826905011830031909471804736 n 3 + 216702257836149760908387856652778361968 n 2 + 110271262234453821686038945227983665056 n + 33793223963115234178770270198997023360 n + 4617446782861554489810335396428876800) f(n + 3)/((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) %1) - 1/12 (n + 5) ( 20 19 272093738621695436342196846 n + 20615834932309374553187438319 n 18 + 736096464092306913966284285826 n 17 + 16462570381535206551597173935866 n 16 + 258540031307808479119457130258630 n 15 + 3029413044726006739900491698346209 n 14 + 27466747028464234622179851632810084 n 13 + 197213635794016998417742021565324287 n 12 + 1138185704221770114858691447951187356 n 11 + 5328341697672012901835267039407024434 n 10 + 20327756169592300154693020151116706610 n 9 + 63248916571514937977235533165007840103 n 8 + 160041147264050480946775105964944486684 n 7 + 327086269425868664553137435375062144214 n 6 + 533761253079825672837444799848282812204 n 5 + 683307165151711845768028706070993640584 n 4 + 668248735647407883881691424280941583184 n 3 + 479292576393702306118124528938661125824 n 2 + 235862982587005188042523056593894251776 n + 70404026467270989201947016904181468160 n + 9451351086602422171071003661152460800) f(n + 4)/((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) %1) - 1/72 (n + 5) ( 20 19 102872174967486359042717655 n + 7845793241751038394243312435 n 18 17 + 281961509301967126357689386514 n + 6346540860291535695346287872984 n 16 + 100304453238372018286405964703065 n 15 + 1182706985696992237506359085876125 n 14 + 10790251509515373284159798482429949 n 13 + 77956885280583394766567803155691439 n 12 + 452712045368746381719987009446515814 n 11 + 2132575814416630782601016673748191424 n 10 + 8187202273872130982557305464465856205 n 9 + 25638128933411694589675001158948921045 n 8 + 65303343613683684754348333365409102582 n 7 + 134387219339321811869314330670296702612 n 6 + 220904195796331879779302917005462460312 n 5 + 285012473475077972335052143884087263232 n 4 + 281113989425154402986714593122216393984 n 3 + 203536760857541896400694713011163704704 n 2 + 101234084664735437185978491694477777920 n + 30591007382818835237979388223956224000 n + 4166941462323074638869940855547904000) f(n + 5)/((n + 6) (6 n + 35) (3 n + 17) (2 n + 11) (3 n + 16) (31 + 6 n) %1) + f(n + 6) = 0 15 14 %1 := 474032555203494500577 n + 22880318607752553238473 n 13 12 + 509937781527663752123133 n + 6956448369538558598064929 n 11 10 + 64908855820211742351954084 n + 438402614453433172059981568 n 9 8 + 2211867323778966419300933289 n + 8477842573151411383494981813 n 7 6 + 24851374921074407273161652721 n + 55607318183267609082018551389 n 5 4 + 93975423151814652256078527348 n + 117413621868058210741438137668 n 3 2 + 104507636925749545325312328048 n + 62140830992628953647119111360 n + 21835565734711641921076723200 n + 3354029399069914987465344000 subject to the initial conditions f(1) = 0, f(2) = 12, f(3) = 90, f(4) = 1036, f(5) = 10950, f(6) = 121542 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 12, 90, 1036, 10950, 121542, 1352918, 15244684, 172852524, 1971729462, 22594672430, 259935190438, 3000162154158, 34725238776618, 402903230082990, 4684667892145036, 54571995741812264, 636770401971278172, 7441171721232895272, 87072340917583122086, 1020102692543571476300, 11964218342686241225342, 140462311764530265138970, 1650569692739169093012646, 19412185034557002330224700, 228482597969669404637594070, 2691192723410389395336147450, 31719546131436095386176293130, 374092917264349498589172180270, 4414527744049356507435244281042] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 123 75857 12207375 287015428893 C 12 (1/n) |1 - ----- - ---------- + ------------ + ----------------- | 728 n 2 3 4 \ 7419776 n 771656704 n 15729450254336 n 3561043421601 3969153033916995331 - -------------------- - ------------------------ 5 6 21266216743862272 n 116708997490316148736 n 3753839193007256700105 31793014560809668241987747 - -------------------------- + ------------------------------ 7 8 84964150172950156279808 n 494831210607261710173601792 n 120184062642758899307652424119 + --------------------------------- 9 360237121322086525006382104576 n 9984927211902648575196870782258253 \ + ---------------------------------------| 10| 47729977626691176217245603327901696 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.10243892088241431012484898056956 The whole thing took, 130.379, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are -7203*(2*n+1)*(n+5)*(n+4)*(n+3)*(2+n)*(n+1)*(474032555203494500577*n^15+ 29990806935804970747128*n^14+880035660332566420022340*n^13+ 15883433335321259718129236*n^12+197136873624906917566429383*n^11+ 1781694545071855438287922048*n^10+12109083624307220545159358895*n^9+ 62994219211921044547485935274*n^8+252795711312140895717434113836*n^7+ 782169723956892922603092736492*n^6+1849631049668931288482157812325*n^5+ 3280658964696467348762669367830*n^4+4221419961025345716129204682164*n^3+ 3716694303634508818493298058632*n^2+1999693279339972603489896786720*n+ 494886312284081187129276153600)/(n+6)/(6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6 *n)/(474032555203494500577*n^15+22880318607752553238473*n^14+ 509937781527663752123133*n^13+6956448369538558598064929*n^12+ 64908855820211742351954084*n^11+438402614453433172059981568*n^10+ 2211867323778966419300933289*n^9+8477842573151411383494981813*n^8+ 24851374921074407273161652721*n^7+55607318183267609082018551389*n^6+ 93975423151814652256078527348*n^5+117413621868058210741438137668*n^4+ 104507636925749545325312328048*n^3+62140830992628953647119111360*n^2+ 21835565734711641921076723200*n+3354029399069914987465344000)*f(n)+343/6*(n+5)* (n+4)*(n+3)*(2+n)*(940954622078936583645345*n^17+61413661011730740100339770*n^ 16+1866633304994001692193216990*n^15+35066572160375192693219049736*n^14+ 455671162374757135863796184471*n^13+4342708261720654097256500840948*n^12+ 31400416444276647707227998492757*n^11+175742680937651126065394474429778*n^10+ 769736077239286561250383581493800*n^9+2649077658892797240312369999223286*n^8+ 7149510259550636756885708717192233*n^7+15008903383835588968697638008415738*n^6+ 24133160663176269982616354355878564*n^5+28980210226721535166579209450322056*n^4 +24960911072795703531774306090845280*n^3+14415732314762543016493992951187008*n^ 2+4923460673840322668884144845761280*n+732939107160952648703444831078400)/(n+6) /(6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6*n)/(474032555203494500577*n^15+ 22880318607752553238473*n^14+509937781527663752123133*n^13+ 6956448369538558598064929*n^12+64908855820211742351954084*n^11+ 438402614453433172059981568*n^10+2211867323778966419300933289*n^9+ 8477842573151411383494981813*n^8+24851374921074407273161652721*n^7+ 55607318183267609082018551389*n^6+93975423151814652256078527348*n^5+ 117413621868058210741438137668*n^4+104507636925749545325312328048*n^3+ 62140830992628953647119111360*n^2+21835565734711641921076723200*n+ 3354029399069914987465344000)*f(n+1)-49/36*(n+3)*(n+4)*(n+5)*( 2405241185102531095927698*n^18+162996939725235811502602113*n^17+ 5156561424962735761696568664*n^16+101089421683255118493994686410*n^15+ 1374562489612390921188764335164*n^14+13747654122210041198039206192601*n^13+ 104634318211942088823022765851804*n^12+618376738164019449560831271867221*n^11+ 2869120075048857689468130933347604*n^10+10493215583691357485057941047631942*n^9 +30183409599273952865258536966844688*n^8+67688298602072915730850033243704361*n^ 7+116362520445243705667548456839384826*n^6+149023668483552466359444906098897704 *n^5+135441198399111703522588725019003584*n^4+ 79755557734936492792743933527899248*n^3+24328579728926812497712980929905248*n^2 +446727856794543594371244119518080*n-1234348678514937167340365325081600)/(n+6)/ (6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6*n)/(474032555203494500577*n^15+ 22880318607752553238473*n^14+509937781527663752123133*n^13+ 6956448369538558598064929*n^12+64908855820211742351954084*n^11+ 438402614453433172059981568*n^10+2211867323778966419300933289*n^9+ 8477842573151411383494981813*n^8+24851374921074407273161652721*n^7+ 55607318183267609082018551389*n^6+93975423151814652256078527348*n^5+ 117413621868058210741438137668*n^4+104507636925749545325312328048*n^3+ 62140830992628953647119111360*n^2+21835565734711641921076723200*n+ 3354029399069914987465344000)*f(2+n)-1/12*(n+4)*(n+5)*( 636645631005611661043935234*n^19+45372078376722272810515765248*n^18+ 1517981277877548737595037283133*n^17+31676698689184303792113176791080*n^16+ 462008133154872122705136320451680*n^15+5001435988182873604308029862152234*n^14+ 41649710781324479388605566263291115*n^13+272849537561564344595497128508727194*n ^12+1425847020361230661535579789020756689*n^11+ 5990856607224978045980576494777490652*n^10+ 20300664393673377626444311543063670344*n^9+ 55411293099483782315987509497149507530*n^8+ 121145699736402053038910919287956061669*n^7+ 209900987895478809349318823731636436750*n^6+ 283338571758556199712071260004735054088*n^5+ 290273689839826905011830031909471804736*n^4+ 216702257836149760908387856652778361968*n^3+ 110271262234453821686038945227983665056*n^2+ 33793223963115234178770270198997023360*n+4617446782861554489810335396428876800) /(n+6)/(6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6*n)/(474032555203494500577*n^15 +22880318607752553238473*n^14+509937781527663752123133*n^13+ 6956448369538558598064929*n^12+64908855820211742351954084*n^11+ 438402614453433172059981568*n^10+2211867323778966419300933289*n^9+ 8477842573151411383494981813*n^8+24851374921074407273161652721*n^7+ 55607318183267609082018551389*n^6+93975423151814652256078527348*n^5+ 117413621868058210741438137668*n^4+104507636925749545325312328048*n^3+ 62140830992628953647119111360*n^2+21835565734711641921076723200*n+ 3354029399069914987465344000)*f(n+3)-1/12*(n+5)*(272093738621695436342196846*n^ 20+20615834932309374553187438319*n^19+736096464092306913966284285826*n^18+ 16462570381535206551597173935866*n^17+258540031307808479119457130258630*n^16+ 3029413044726006739900491698346209*n^15+27466747028464234622179851632810084*n^ 14+197213635794016998417742021565324287*n^13+ 1138185704221770114858691447951187356*n^12+ 5328341697672012901835267039407024434*n^11+ 20327756169592300154693020151116706610*n^10+ 63248916571514937977235533165007840103*n^9+ 160041147264050480946775105964944486684*n^8+ 327086269425868664553137435375062144214*n^7+ 533761253079825672837444799848282812204*n^6+ 683307165151711845768028706070993640584*n^5+ 668248735647407883881691424280941583184*n^4+ 479292576393702306118124528938661125824*n^3+ 235862982587005188042523056593894251776*n^2+ 70404026467270989201947016904181468160*n+9451351086602422171071003661152460800) /(n+6)/(6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6*n)/(474032555203494500577*n^15 +22880318607752553238473*n^14+509937781527663752123133*n^13+ 6956448369538558598064929*n^12+64908855820211742351954084*n^11+ 438402614453433172059981568*n^10+2211867323778966419300933289*n^9+ 8477842573151411383494981813*n^8+24851374921074407273161652721*n^7+ 55607318183267609082018551389*n^6+93975423151814652256078527348*n^5+ 117413621868058210741438137668*n^4+104507636925749545325312328048*n^3+ 62140830992628953647119111360*n^2+21835565734711641921076723200*n+ 3354029399069914987465344000)*f(n+4)-1/72*(n+5)*(102872174967486359042717655*n^ 20+7845793241751038394243312435*n^19+281961509301967126357689386514*n^18+ 6346540860291535695346287872984*n^17+100304453238372018286405964703065*n^16+ 1182706985696992237506359085876125*n^15+10790251509515373284159798482429949*n^ 14+77956885280583394766567803155691439*n^13+ 452712045368746381719987009446515814*n^12+2132575814416630782601016673748191424 *n^11+8187202273872130982557305464465856205*n^10+ 25638128933411694589675001158948921045*n^9+ 65303343613683684754348333365409102582*n^8+ 134387219339321811869314330670296702612*n^7+ 220904195796331879779302917005462460312*n^6+ 285012473475077972335052143884087263232*n^5+ 281113989425154402986714593122216393984*n^4+ 203536760857541896400694713011163704704*n^3+ 101234084664735437185978491694477777920*n^2+ 30591007382818835237979388223956224000*n+4166941462323074638869940855547904000) /(n+6)/(6*n+35)/(3*n+17)/(2*n+11)/(3*n+16)/(31+6*n)/(474032555203494500577*n^15 +22880318607752553238473*n^14+509937781527663752123133*n^13+ 6956448369538558598064929*n^12+64908855820211742351954084*n^11+ 438402614453433172059981568*n^10+2211867323778966419300933289*n^9+ 8477842573151411383494981813*n^8+24851374921074407273161652721*n^7+ 55607318183267609082018551389*n^6+93975423151814652256078527348*n^5+ 117413621868058210741438137668*n^4+104507636925749545325312328048*n^3+ 62140830992628953647119111360*n^2+21835565734711641921076723200*n+ 3354029399069914987465344000)*f(n+5)+f(n+6) = 0, 12^n*(1/n)^(1/2)*(1-123/728/n-\ 75857/7419776/n^2+12207375/771656704/n^3+287015428893/15729450254336/n^4-\ 3561043421601/21266216743862272/n^5-3969153033916995331/116708997490316148736/n ^6-3753839193007256700105/84964150172950156279808/n^7+ 31793014560809668241987747/494831210607261710173601792/n^8+ 120184062642758899307652424119/360237121322086525006382104576/n^9+ 9984927211902648575196870782258253/47729977626691176217245603327901696/n^10), .\ 10243892088241431012484898056956, .10243892088241431012484898056956 ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-6], [-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5], [6]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-6], [-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5], [6]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 6], [n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5], [n[1] + 6]} The sequence f(n) satisfies the following recurrence 4826809 ------- (7 n + 46) (7 n + 47) (7 n + 48) (n + 6) (n + 5) (n + 4) (n + 3) 72 (2 + n) (n + 1) f(n)/((7 n + 13) (6 n + 13) (7 n + 26) (3 n + 13) 371293 (7 n + 39) (3 n + 20) (2 n + 13) (6 n + 41) (n + 7)) - ------ 24 (7 n + 47) (7 n + 48) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) f(n + 1) ------------------------------------------------------------------------- (7 n + 20) (6 n + 19) (7 n + 33) (3 n + 16) (6 n + 41) (3 n + 20) (n + 7) 28561 - ----- (n + 3) (n + 4) (n + 5) (n + 6) (7 n + 48) (7 n + 47) (7 n + 46) ( 24 6 5 4 3 2 87318 n + 2101869 n + 20363078 n + 101276356 n + 271761718 n + 371897147 n + 202725978) f(2 + n)/((7 n + 13) (6 n + 13) (7 n + 27) (7 n + 26) (3 n + 13) (6 n + 25) (7 n + 40) (7 n + 39) (3 n + 20) 2197 (2 n + 13) (3 n + 19) (6 n + 41) (n + 7)) + ---- (7 n + 48) (n + 6) (n + 5) 12 (n + 4) 5 4 3 2 (36456 n + 828940 n + 7357669 n + 31842488 n + 67154153 n + 55243398) f(n + 3)/((7 n + 20) (6 n + 19) (7 n + 34) (7 n + 33) (3 n + 16) (31 + 6 n) 169 (6 n + 41) (3 n + 20) (n + 7)) + --- (7 n + 48) (n + 6) (n + 5) (7 n + 47) 24 8 7 6 5 (7 n + 46) (7434378 n + 297906147 n + 5190990078 n + 51368969294 n 4 3 2 + 315735061658 n + 1234252797583 n + 2996734969822 n + 4131957473856 n + 2477277863424) f(n + 4)/((7 n + 27) (7 n + 26) (3 n + 13) (6 n + 25) (7 n + 40) (7 n + 41) (7 n + 39) (3 n + 20) (2 n + 13) (3 n + 19) 13 6 5 (6 n + 37) (6 n + 41) (n + 7)) - -- (n + 6) (730051 n + 24508855 n 24 4 3 2 + 341240311 n + 2522547817 n + 10443817246 n + 22965526936 n + 20958612864) f(n + 5)/((7 n + 34) (7 n + 33) (3 n + 16) (31 + 6 n) (6 n + 41) (3 n + 20) (n + 7)) - 1/72 (7 n + 48) (7 n + 47) (7 n + 46) ( 6 5 4 3 2 543607 n + 19569852 n + 293421346 n + 2345347824 n + 10540416559 n + 25253363892 n + 25198893720) f(n + 6)/((7 n + 40) (7 n + 41) (7 n + 39) (3 n + 20) (2 n + 13) (3 n + 19) (6 n + 37) (6 n + 41) (n + 7)) + f(n + 7) = 0 subject to the initial conditions f(1) = 1, f(2) = 13, f(3) = 127, f(4) = 1469, f(5) = 17151, f(6) = 204763, f(7) = 2473325 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 13, 127, 1469, 17151, 204763, 2473325, 30162301, 370487485, 4577127763, 56813989827, 707972099627, 8851373201919, 110976634957761, 1394804756117877, 17567994350713469, 221690794842728445, 2802194053806820153, 35472906914814159895, 449653511692687417219, 5706710865770808986261, 72505698882922448164463, 922135794855928016638287, 11738630472138500287398379, 149557285853195186723362151, 1906939146026187989992668691, 24332118153597388614696496813, 310680687881441706619756773457, 3969352264437746100745606059619, 50743204294527314086915307835913] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 17 1937 24565 118905693 C 13 (1/n) |1 - ----- - --------- + ---------- + ------------- | 112 n 2 3 4 \ 175616 n 2809856 n 8811708416 n 12733453101 20492376749251 6776083585211875 + ---------------- - ------------------- - --------------------- 5 6 7 1832835350528 n 1547476985184256 n 173317422340636672 n 3916336254538303453 2288682639777142417061 - ------------------------ + -------------------------- 8 9 155292410417210458112 n 17392749966727571308544 n 161769266674558845146656653 \ + -------------------------------| 10| 354533815321774813553360896 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.106621809311461540404113118056856 1/2 7 The EXACT value of the constant C is probably, -------- 1/2 14 Pi The whole thing took, 235.760, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 4826809/72*(7*n+46)*(7*n+47)*(7*n+48)*(n+6)*(n+5)*(n+4)*(n+3)*(2+n)*(n+1)/(7*n+ 13)/(6*n+13)/(7*n+26)/(3*n+13)/(7*n+39)/(3*n+20)/(2*n+13)/(6*n+41)/(n+7)*f(n)-\ 371293/24*(7*n+47)*(7*n+48)*(n+6)*(n+5)*(n+4)*(n+3)*(2+n)/(7*n+20)/(6*n+19)/(7* n+33)/(3*n+16)/(6*n+41)/(3*n+20)/(n+7)*f(n+1)-28561/24*(n+3)*(n+4)*(n+5)*(n+6)* (7*n+48)*(7*n+47)*(7*n+46)*(87318*n^6+2101869*n^5+20363078*n^4+101276356*n^3+ 271761718*n^2+371897147*n+202725978)/(7*n+13)/(6*n+13)/(7*n+27)/(7*n+26)/(3*n+ 13)/(6*n+25)/(7*n+40)/(7*n+39)/(3*n+20)/(2*n+13)/(3*n+19)/(6*n+41)/(n+7)*f(2+n) +2197/12*(7*n+48)*(n+6)*(n+5)*(n+4)*(36456*n^5+828940*n^4+7357669*n^3+31842488* n^2+67154153*n+55243398)/(7*n+20)/(6*n+19)/(7*n+34)/(7*n+33)/(3*n+16)/(31+6*n)/ (6*n+41)/(3*n+20)/(n+7)*f(n+3)+169/24*(7*n+48)*(n+6)*(n+5)*(7*n+47)*(7*n+46)*( 7434378*n^8+297906147*n^7+5190990078*n^6+51368969294*n^5+315735061658*n^4+ 1234252797583*n^3+2996734969822*n^2+4131957473856*n+2477277863424)/(7*n+27)/(7* n+26)/(3*n+13)/(6*n+25)/(7*n+40)/(7*n+41)/(7*n+39)/(3*n+20)/(2*n+13)/(3*n+19)/( 6*n+37)/(6*n+41)/(n+7)*f(n+4)-13/24*(n+6)*(730051*n^6+24508855*n^5+341240311*n^ 4+2522547817*n^3+10443817246*n^2+22965526936*n+20958612864)/(7*n+34)/(7*n+33)/( 3*n+16)/(31+6*n)/(6*n+41)/(3*n+20)/(n+7)*f(n+5)-1/72*(7*n+48)*(7*n+47)*(7*n+46) *(543607*n^6+19569852*n^5+293421346*n^4+2345347824*n^3+10540416559*n^2+ 25253363892*n+25198893720)/(7*n+40)/(7*n+41)/(7*n+39)/(3*n+20)/(2*n+13)/(3*n+19 )/(6*n+37)/(6*n+41)/(n+7)*f(n+6)+f(n+7) = 0, 13^n*(1/n)^(1/2)*(1-17/112/n-1937/ 175616/n^2+24565/2809856/n^3+118905693/8811708416/n^4+12733453101/1832835350528 /n^5-20492376749251/1547476985184256/n^6-6776083585211875/173317422340636672/n^ 7-3916336254538303453/155292410417210458112/n^8+2288682639777142417061/ 17392749966727571308544/n^9+161769266674558845146656653/ 354533815321774813553360896/n^10), .106621809311461540404113118056856, 1/14*7^( 1/2)/Pi^(1/2) The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, { [-7], [-6], [-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5], [6], [7] } By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-7], [-6], [-5], [-4], [-3], [-2], [-1], [1], [2], [3], [4], [5], [6], [7]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1] - 7], [n[1] - 6], [n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5], [n[1] + 6], [n[1] + 7]} The sequence f(n) satisfies the following recurrence 401408 (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) (n + 1) ( 21 20 439618374907031250000000000 n + 54317990351013046875000000000 n 19 + 3186000292892110312500000000000 n 18 + 117978933342939260299804687500000 n 17 + 3094120017405281355933647460937500 n 16 + 61108106209589900878207198242187500 n 15 + 943366858113619835879566774658203125 n 14 + 11662293180966132894936335666894531250 n 13 + 117326198480191330690014708229031250000 n 12 + 970725913240296436916906467710478125000 n 11 + 6647686471925241010248606211301336718750 n 10 + 37793617475748424470796112640461719687500 n 9 + 178362400931372263129917220437525679950000 n 8 + 696545259452111342670650808605459032702500 n 7 + 2236153768113052022577366216399958827063125 n 6 + 5838558096333078403685387696433009422223250 n 5 + 12198469110629946028269930046344697789669820 n 4 + 19903650960291887933691634260423590339719864 n 3 + 24430604881985343057237137911422214361145152 n 2 + 21212797991393050587110062198852161757129216 n + 11613340152832964872990948808443480689881088 n + 3014048105062900509821486245313771030446080) f(n)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) - 14336 (2 + n) 22 (n + 3) (n + 4) (n + 5) (n + 6) (n + 7) (593484806124492187500000000000 n 21 + 74219514183054351562500000000000 n 20 + 4411093622475750490546875000000000 n 19 + 165723122695657875322939453125000000 n 18 + 4415964165395540039519553955078125000 n 17 + 88761343007056131695179147719726562500 n 16 + 1397284093345929893714695359089355468750 n 15 + 17654313525326891477454113956496337890625 n 14 + 182004973398389908706103202228707568359375 n 13 + 1548046684275738070830526420686043435546875 n 12 + 10939909462255388933967084898830235744921875 n 11 + 64481425741237789486233405993079524659765625 n 10 + 317311116426658146471473313323318075549765625 n 9 + 1301463589944117890622254870886338769809878125 n 8 + 4429055042750137689013398793085136526047511875 n 7 + 12409306680709554398664475192701178083560851250 n 6 + 28288109699250901830954165013346321954042411500 n 5 + 51564791192866279897851416431881060895118051240 n 4 + 73272885293061718544700405895525206231872097376 n 3 + 78090252270607408394872105409183446657437924608 n 2 + 58614723894036826612371197851817700893093791744 n + 27573713037066954152467846293814302758153306112 n + 6099721693698711465822178982191381638933381120) f(n + 1)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) + 128 (n + 3) (n + 4) (n + 5) (n + 6) (n + 7) ( 23 220579398846352743750000000000000 n 22 + 28136477889986909270625000000000000 n 21 + 1708413789889596071293593750000000000 n 20 + 65691193961091106504176117187500000000 n 19 + 1795171236064386887335875855820312500000 n 18 + 37089696056048365600788524567296875000000 n 17 + 601714379565403251047621364553901367187500 n 16 + 7858147028994641378962460512992165820312500 n 15 + 84022622093538115638972151433009963677734375 n 14 + 744140308469408712450380793805781874686718750 n 13 + 5501034671512669656626491101508879558582031250 n 12 + 34102500980032648207706047261632762808869843750 n 11 + 177653450253054805609385126077124701810698337500 n 10 + 777427482719262454461335540101995525665686511250 n 9 + 2850071969852219753306710927363146640263440863750 n 8 + 8706366826494592148828391736957914340747599032750 n 7 + 21975508981555880592597906466002680267361970286765 n 6 + 45267909178569492046025709132156226703249787901768 n 5 + 74761045050425287108465387493997614327474359810988 n 4 + 96469637185394603415564696338595314736783167517376 n 3 + 93549851933501160214150506625821746205568895561728 n 2 + 64009543987955812708479451428323873141446154571776 n + 27496477558688018002777859712143241383244548358144 n + 5564163031370829253573157517190185136309414133760) f(2 + n)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) + 32/7 (n + 4) (n + 5) (n + 6) (n + 7) ( 12 7132711764108708849495647387335988306387848612500 n 13 + 1278968043901782290095840764407088777602376796875 n 4 + 10796769673792543020186828687879688698949611675083136 n 6 + 5737863828285255694010230257087051191274666308214040 n + 522687161159117181930884905865222195638243153674240 14 + 194002117195634689589163246043267194521840625000 n 9 + 452480446055326840844535469676087409604464752443625 n 2 + 6470190190950967988440358858610509468683566879842304 n 11 + 33678799677882023583292254278277870679337855188125 n 18 + 17447954492066189631731852561863207031250000 n 8 + 1275687961314589742486829687095632440771391097490130 n 7 + 2987252941859511985756313708950894894501530566012156 n 20 + 48265167450257163248962977779414062500000 n 10 + 134471211656757060837982890382096591401286669720000 n 19 + 1034052714066444853731137171860394531250000 n 17 + 237795744103251767600093886692224638281250000 n 5 + 8881111867063307788440845744839724407066454476420544 n 15 + 24819490492564346362391829810368639988019921875 n 22 + 43050045830716315586435625000000000000 n 24 + 5255103096069671643750000000000000 n 23 + 688718797190616680853750000000000000 n + 2668289908519461368941844307200032031393915004715008 n 16 + 2663580364488424238536781367959191347316406250 n 3 + 9919497234529163955114834578695644403177525435671552 n 21 + 1707805955892846405920106726562500000000 n ) f(n + 3)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) - 16/7 (n + 5) (n + 6) (n + 7) ( 12 92613414235360163261864922412020150506419253259375 n 13 + 18178683151633193253384253365272889546608594578125 n 4 + 79232292287366262381596049491930240073175086210671488 n 6 + 47764696103480520315712908828417667726759391070452400 n 14 + 3039755489365027169428725849274160160523597265625 n 9 + 4625849165679042357999594166822374623371644451150950 n 2 + 41979738745826796276332657183475644595274256959660032 n + 2985761553837925689869890419428058411997398816522240 11 + 401857697100359727835662047611548864137426679506250 n 18 + 448351460031221918671164641343909962402343750 n 8 + 12142807675744527245388764819012114672428836327422040 n 7 + 26557164518895896492756427167993491278895195436035080 n 20 + 1774990239045902394290354989892416992187500 n 10 + 1481979119393934611613571801378282507996251582648125 n 19 + 31341418739569566714003246551464464111328125 n 17 + 5289087404166687249743961183314134050908203125 n 5 + 69365300104899721739377536214236524357760593981982720 n 15 + 432304873307110901943362624671102160024173828125 n 22 + 2698608524889266873837485444335937500000 n 24 + 1011126467330131798233984375000000000 n 23 + 65500757228631719881244531250000000000 n + 16262277447847763150104756291591510260462291012550656 n 16 + 52099398846423000331660858916550360544400390625 n 3 + 68447884926035603259151313186321469090469322091485184 n 25 + 7459042334609466316406250000000000 n 21 + 79389786026225221674148131513354492187500 n ) f(n + 4)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) - 8/7 12 (n + 6) (n + 7) (2162675741147788274135742194456891115448358817861250 n 13 + 456367136416531910571734701943819824157346709582500 n 4 + 1235322858117898465250560107633135368085150070599759744 n 6 + 803151081343723507492553192110549374223029759035718464 n 14 + 82580227856105930678095890882242386759332601443750 n 9 + 89822080747438033739461478741403245497697446276543677 n 2 + 617477253260573891727219847176714887925941901438590976 n + 42311852717136256989539243947654276637228403114639360 11 + 8779661545117127581276682869093924582629829594162250 n 18 + 18287915407238164540183299208507429205472656250 n 8 + 223804741833315261472171835651746290561688619078275896 n 7 + 466571210387640960985188457665761490494980594968588648 n 20 + 96842263469915253758074481049850872070312500 n 10 + 30451159470245642220308373323111404617757281976802760 n 19 + 1463056731115604471512762996057159225781250000 n 17 + 191582232540761965018749878999834153332112109375 n 26 + 17558607597023775318750000000000000 n 5 + 1120822794978094487871804097381785659347305370021606672 n 15 + 12805311289511151274718011051426743516564825468750 n 22 + 221892453601609806378327118617421875000000 n 24 + 167288048182890836918802421875000000000 n 23 + 7201652753086805237684758101562500000000 n + 234083417047529406875153849836613904512096621760086016 n 16 + 1697580912276874956359316126802543670716291406250 n 3 + 1034150497390265101743993592124047497846466074174876672 n 25 + 2476767020185896535676250000000000000 n 21 + 5209052253147767882729894949444656250000000 n ) f(n + 5)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) - 4/7 12 (n + 7) (12478698583340624013402311198990420897828117400823750 n 13 + 2800692722516452177807801056965347963875441027338750 n 4 + 5015674719543931707956365803301981639116265169198168576 n 6 + 3491655331574403366458364063217773310709025053253038048 n 14 + 541974512380965196271641248898584518095941198300000 n 9 + 442591825024906380048178042262716182726391260489035568 n 2 + 2368128864659100597874571832046529667924098393740050432 n + 155090316136685516236728471030389615032585847612375040 11 + 47861246610389489430661937920983115547581274750440325 n 18 + 169143822070817765163837639953662528683925781250 n 8 + 1054267968253291657796515681450568456328218256133148784 n 7 + 2108146108150173360577031738760983503590129148889249872 n 20 + 1139515791634650259505079909102180590332031250 n 10 + 157513361877925418710077771343541023660927427836124710 n 19 + 15140989716836496885117205742310803217509765625 n 17 + 1603861152361372835100900595890229756653435937500 n 26 + 1410080383249322919208593750000000000 n 5 + 4702266541146675572555926757843179977299324073596042368 n 15 + 90442102964676402567005453566324998865994827781250 n 22 + 3620912403202765510780463571372392578125000 n 27 + 9556164858887850164062500000000000 n 24 + 4511589178026647342845303505859375000000 n 23 + 146262571063907646787144243813037109375000 n + 876304842144183506390384811463629521598474605574488064 n 16 + 12997406560635658766793157341534976062832678125000 n 3 + 4075069122674791743047429747262024778442890761755639808 n 25 + 99809701454140969763779453125000000000 n 21 + 71162215237341947348201945624946042480468750 n ) f(n + 6)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) - 8/7 12 (n + 7) (271215980897565175814170396236259254797695539480125 n 13 + 60669843274466515721460970120398780252552195789375 n 4 + 112772505118035809045655393012661304243489314513981184 n 6 + 77674803617366407377360340027603294021758161597584144 n 14 + 11702431909313517120284551279074903008759493315000 n 9 + 9722140541241805571129393658032739492111301098313836 n 2 + 53986722334971597772713385900888908678246813091479552 n 11 + 1043777931546892829199927542180265522605978951687370 n 18 + 3606138907818076656850545525268819256101171875 n + 3603784808003285530575000451338521910665403338588160 8 + 23249076989128438581293168378734541352420168363615336 n 7 + 46684576816255655648002403592903675100947523928444832 n 20 + 24141086937773887275288916144235844873046875 n 10 + 3447252888848348269258464901318695071725230763339429 n 19 + 321786875387662439789208502906824328171875000 n 17 + 34302295785686717004490636055694059937426562500 n 26 + 29294184091581282155625000000000000 n 5 + 105132401356083105304297294898912550219923984941217088 n 15 + 1946602428884088935719677038135799375518678418750 n 22 + 76220737712279557754404788686900390625000 n 27 + 197857283520907926562500000000000 n 24 + 94352958749363907866504396484375000000 n 23 + 3068884483742218404737822737675781250000 n + 20152207135835365131788605349592044929612219053244416 n 16 + 278859198022359524422735287211916759644168125000 n 3 + 92213325090385430632648490908454969701996097147363328 n 25 + 2080474998228515914562988281250000000 n 21 + 1502797117614494282211200858119144775390625 n ) f(n + 7)/((51 + 7 n) (52 + 7 n) (53 + 7 n) (54 + 7 n) (55 + 7 n) (50 + 7 n) %1 (n + 8)) + f(n + 8) = 0 21 20 %1 := 439618374907031250000000000 n + 45086004477965390625000000000 n 19 + 2191960344602325937500000000000 n 18 + 67180653506055291706054687500000 n 17 + 1456013874290589242568413085937500 n 16 + 23725833300297044793595933593750000 n 15 + 301697317983804918266837032470703125 n 14 + 3066784413682047893999594906396484375 n 13 + 25322557999045322518731906110525390625 n 12 + 171628768613815602092137469732241796875 n 11 + 960889933872152378329623724978562109375 n 10 + 4456765947099768409184288068517226328125 n 9 + 17121843815961035114704287274454129559375 n 8 + 54306151651360640118121509393834121355625 n 7 + 141260473037717326368081393755262941690000 n 6 + 298108295067937217942574220225486761167000 n 5 + 502137362642263302609745265224664852250320 n 4 + 658835303176471908729603972956495216813264 n 3 + 648600963379653918988566086872017317808896 n 2 + 450536788733871546144958372502698056479744 n + 196842716802992174718652323463675073888256 n + 40680205814089677460397239814128769433600 subject to the initial conditions f(1) = 0, f(2) = 14, f(3) = 126, f(4) = 1666, f(5) = 20650, f(6) = 266882, f(7) = 3467926, f(8) = 45576722 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [0, 14, 126, 1666, 20650, 266882, 3467926, 45576722, 602928648, 8023416114, 107265098094, 1439640256978, 19385340387322, 261766547083314, 3543324522082726, 48065214247194898, 653227412882089248, 8892428716086813716, 121233380195178045690, 1655025965934688655266, 22621035574824951982186, 309526024427056147157362, 4239524236138326249642990, 58121369746325425690215698, 797482625881393790011269400, 10950776618331385870112215970, 150481013987708615850113303010, 2069231639008305588171893462610, 28471278869367938657800731018810, 391973927007916336762676111315682] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 133 19093 3013597 16330884117 C 14 (1/n) |1 - ----- - ---------- + ------------ + --------------- | 800 n 2 3 4 \ 1792000 n 204800000 n 917504000000 n 4947069773703 1276965089773528991 12047800999029321383 + ------------------- - ----------------------- - ------------------------ 5 6 7 3670016000000000 n 41104179200000000000 n 263066746880000000000 n 396482109833031018965311 421879590571190591646484249 + ---------------------------- + ------------------------------- 8 9 8418135900160000000000000 n 1346901744025600000000000000 n 23028886248180185261773271125869 \ + ------------------------------------| 10| 75426497665433600000000000000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.089206205807638555726948318628254 1/2 1/2 2 5 The EXACT value of the constant C is probably, --------- 1/2 20 Pi The whole thing took, 549.618, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 401408*(n+7)*(n+6)*(n+5)*(n+4)*(n+3)*(2+n)*(n+1)*(439618374907031250000000000*n ^21+54317990351013046875000000000*n^20+3186000292892110312500000000000*n^19+ 117978933342939260299804687500000*n^18+3094120017405281355933647460937500*n^17+ 61108106209589900878207198242187500*n^16+943366858113619835879566774658203125*n ^15+11662293180966132894936335666894531250*n^14+ 117326198480191330690014708229031250000*n^13+ 970725913240296436916906467710478125000*n^12+ 6647686471925241010248606211301336718750*n^11+ 37793617475748424470796112640461719687500*n^10+ 178362400931372263129917220437525679950000*n^9+ 696545259452111342670650808605459032702500*n^8+ 2236153768113052022577366216399958827063125*n^7+ 5838558096333078403685387696433009422223250*n^6+ 12198469110629946028269930046344697789669820*n^5+ 19903650960291887933691634260423590339719864*n^4+ 24430604881985343057237137911422214361145152*n^3+ 21212797991393050587110062198852161757129216*n^2+ 11613340152832964872990948808443480689881088*n+ 3014048105062900509821486245313771030446080)/(51+7*n)/(52+7*n)/(53+7*n)/(54+7*n )/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n)-14336*(2+n)*(n+3)*(n+4)*( n+5)*(n+6)*(n+7)*(593484806124492187500000000000*n^22+ 74219514183054351562500000000000*n^21+4411093622475750490546875000000000*n^20+ 165723122695657875322939453125000000*n^19+4415964165395540039519553955078125000 *n^18+88761343007056131695179147719726562500*n^17+ 1397284093345929893714695359089355468750*n^16+ 17654313525326891477454113956496337890625*n^15+ 182004973398389908706103202228707568359375*n^14+ 1548046684275738070830526420686043435546875*n^13+ 10939909462255388933967084898830235744921875*n^12+ 64481425741237789486233405993079524659765625*n^11+ 317311116426658146471473313323318075549765625*n^10+ 1301463589944117890622254870886338769809878125*n^9+ 4429055042750137689013398793085136526047511875*n^8+ 12409306680709554398664475192701178083560851250*n^7+ 28288109699250901830954165013346321954042411500*n^6+ 51564791192866279897851416431881060895118051240*n^5+ 73272885293061718544700405895525206231872097376*n^4+ 78090252270607408394872105409183446657437924608*n^3+ 58614723894036826612371197851817700893093791744*n^2+ 27573713037066954152467846293814302758153306112*n+ 6099721693698711465822178982191381638933381120)/(51+7*n)/(52+7*n)/(53+7*n)/(54+ 7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+1)+128*(n+3)*(n+4)*(n+5)*( n+6)*(n+7)*(220579398846352743750000000000000*n^23+ 28136477889986909270625000000000000*n^22+1708413789889596071293593750000000000* n^21+65691193961091106504176117187500000000*n^20+ 1795171236064386887335875855820312500000*n^19+ 37089696056048365600788524567296875000000*n^18+ 601714379565403251047621364553901367187500*n^17+ 7858147028994641378962460512992165820312500*n^16+ 84022622093538115638972151433009963677734375*n^15+ 744140308469408712450380793805781874686718750*n^14+ 5501034671512669656626491101508879558582031250*n^13+ 34102500980032648207706047261632762808869843750*n^12+ 177653450253054805609385126077124701810698337500*n^11+ 777427482719262454461335540101995525665686511250*n^10+ 2850071969852219753306710927363146640263440863750*n^9+ 8706366826494592148828391736957914340747599032750*n^8+ 21975508981555880592597906466002680267361970286765*n^7+ 45267909178569492046025709132156226703249787901768*n^6+ 74761045050425287108465387493997614327474359810988*n^5+ 96469637185394603415564696338595314736783167517376*n^4+ 93549851933501160214150506625821746205568895561728*n^3+ 64009543987955812708479451428323873141446154571776*n^2+ 27496477558688018002777859712143241383244548358144*n+ 5564163031370829253573157517190185136309414133760)/(51+7*n)/(52+7*n)/(53+7*n)/( 54+7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(2+n)+32/7*(n+4)*(n+5)*(n+6)* (n+7)*(7132711764108708849495647387335988306387848612500*n^12+ 1278968043901782290095840764407088777602376796875*n^13+ 10796769673792543020186828687879688698949611675083136*n^4+ 5737863828285255694010230257087051191274666308214040*n^6+ 522687161159117181930884905865222195638243153674240+ 194002117195634689589163246043267194521840625000*n^14+ 452480446055326840844535469676087409604464752443625*n^9+ 6470190190950967988440358858610509468683566879842304*n^2+ 33678799677882023583292254278277870679337855188125*n^11+ 17447954492066189631731852561863207031250000*n^18+ 1275687961314589742486829687095632440771391097490130*n^8+ 2987252941859511985756313708950894894501530566012156*n^7+ 48265167450257163248962977779414062500000*n^20+ 134471211656757060837982890382096591401286669720000*n^10+ 1034052714066444853731137171860394531250000*n^19+ 237795744103251767600093886692224638281250000*n^17+ 8881111867063307788440845744839724407066454476420544*n^5+ 24819490492564346362391829810368639988019921875*n^15+ 43050045830716315586435625000000000000*n^22+5255103096069671643750000000000000* n^24+688718797190616680853750000000000000*n^23+ 2668289908519461368941844307200032031393915004715008*n+ 2663580364488424238536781367959191347316406250*n^16+ 9919497234529163955114834578695644403177525435671552*n^3+ 1707805955892846405920106726562500000000*n^21)/(51+7*n)/(52+7*n)/(53+7*n)/(54+7 *n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+3)-16/7*(n+5)*(n+6)*(n+7)* (92613414235360163261864922412020150506419253259375*n^12+ 18178683151633193253384253365272889546608594578125*n^13+ 79232292287366262381596049491930240073175086210671488*n^4+ 47764696103480520315712908828417667726759391070452400*n^6+ 3039755489365027169428725849274160160523597265625*n^14+ 4625849165679042357999594166822374623371644451150950*n^9+ 41979738745826796276332657183475644595274256959660032*n^2+ 2985761553837925689869890419428058411997398816522240+ 401857697100359727835662047611548864137426679506250*n^11+ 448351460031221918671164641343909962402343750*n^18+ 12142807675744527245388764819012114672428836327422040*n^8+ 26557164518895896492756427167993491278895195436035080*n^7+ 1774990239045902394290354989892416992187500*n^20+ 1481979119393934611613571801378282507996251582648125*n^10+ 31341418739569566714003246551464464111328125*n^19+ 5289087404166687249743961183314134050908203125*n^17+ 69365300104899721739377536214236524357760593981982720*n^5+ 432304873307110901943362624671102160024173828125*n^15+ 2698608524889266873837485444335937500000*n^22+ 1011126467330131798233984375000000000*n^24+ 65500757228631719881244531250000000000*n^23+ 16262277447847763150104756291591510260462291012550656*n+ 52099398846423000331660858916550360544400390625*n^16+ 68447884926035603259151313186321469090469322091485184*n^3+ 7459042334609466316406250000000000*n^25+ 79389786026225221674148131513354492187500*n^21)/(51+7*n)/(52+7*n)/(53+7*n)/(54+ 7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+4)-8/7*(n+6)*(n+7)*( 2162675741147788274135742194456891115448358817861250*n^12+ 456367136416531910571734701943819824157346709582500*n^13+ 1235322858117898465250560107633135368085150070599759744*n^4+ 803151081343723507492553192110549374223029759035718464*n^6+ 82580227856105930678095890882242386759332601443750*n^14+ 89822080747438033739461478741403245497697446276543677*n^9+ 617477253260573891727219847176714887925941901438590976*n^2+ 42311852717136256989539243947654276637228403114639360+ 8779661545117127581276682869093924582629829594162250*n^11+ 18287915407238164540183299208507429205472656250*n^18+ 223804741833315261472171835651746290561688619078275896*n^8+ 466571210387640960985188457665761490494980594968588648*n^7+ 96842263469915253758074481049850872070312500*n^20+ 30451159470245642220308373323111404617757281976802760*n^10+ 1463056731115604471512762996057159225781250000*n^19+ 191582232540761965018749878999834153332112109375*n^17+ 17558607597023775318750000000000000*n^26+ 1120822794978094487871804097381785659347305370021606672*n^5+ 12805311289511151274718011051426743516564825468750*n^15+ 221892453601609806378327118617421875000000*n^22+ 167288048182890836918802421875000000000*n^24+ 7201652753086805237684758101562500000000*n^23+ 234083417047529406875153849836613904512096621760086016*n+ 1697580912276874956359316126802543670716291406250*n^16+ 1034150497390265101743993592124047497846466074174876672*n^3+ 2476767020185896535676250000000000000*n^25+ 5209052253147767882729894949444656250000000*n^21)/(51+7*n)/(52+7*n)/(53+7*n)/( 54+7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+5)-4/7*(n+7)*( 12478698583340624013402311198990420897828117400823750*n^12+ 2800692722516452177807801056965347963875441027338750*n^13+ 5015674719543931707956365803301981639116265169198168576*n^4+ 3491655331574403366458364063217773310709025053253038048*n^6+ 541974512380965196271641248898584518095941198300000*n^14+ 442591825024906380048178042262716182726391260489035568*n^9+ 2368128864659100597874571832046529667924098393740050432*n^2+ 155090316136685516236728471030389615032585847612375040+ 47861246610389489430661937920983115547581274750440325*n^11+ 169143822070817765163837639953662528683925781250*n^18+ 1054267968253291657796515681450568456328218256133148784*n^8+ 2108146108150173360577031738760983503590129148889249872*n^7+ 1139515791634650259505079909102180590332031250*n^20+ 157513361877925418710077771343541023660927427836124710*n^10+ 15140989716836496885117205742310803217509765625*n^19+ 1603861152361372835100900595890229756653435937500*n^17+ 1410080383249322919208593750000000000*n^26+ 4702266541146675572555926757843179977299324073596042368*n^5+ 90442102964676402567005453566324998865994827781250*n^15+ 3620912403202765510780463571372392578125000*n^22+ 9556164858887850164062500000000000*n^27+ 4511589178026647342845303505859375000000*n^24+ 146262571063907646787144243813037109375000*n^23+ 876304842144183506390384811463629521598474605574488064*n+ 12997406560635658766793157341534976062832678125000*n^16+ 4075069122674791743047429747262024778442890761755639808*n^3+ 99809701454140969763779453125000000000*n^25+ 71162215237341947348201945624946042480468750*n^21)/(51+7*n)/(52+7*n)/(53+7*n)/( 54+7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+6)-8/7*(n+7)*( 271215980897565175814170396236259254797695539480125*n^12+ 60669843274466515721460970120398780252552195789375*n^13+ 112772505118035809045655393012661304243489314513981184*n^4+ 77674803617366407377360340027603294021758161597584144*n^6+ 11702431909313517120284551279074903008759493315000*n^14+ 9722140541241805571129393658032739492111301098313836*n^9+ 53986722334971597772713385900888908678246813091479552*n^2+ 1043777931546892829199927542180265522605978951687370*n^11+ 3606138907818076656850545525268819256101171875*n^18+ 3603784808003285530575000451338521910665403338588160+ 23249076989128438581293168378734541352420168363615336*n^8+ 46684576816255655648002403592903675100947523928444832*n^7+ 24141086937773887275288916144235844873046875*n^20+ 3447252888848348269258464901318695071725230763339429*n^10+ 321786875387662439789208502906824328171875000*n^19+ 34302295785686717004490636055694059937426562500*n^17+ 29294184091581282155625000000000000*n^26+ 105132401356083105304297294898912550219923984941217088*n^5+ 1946602428884088935719677038135799375518678418750*n^15+ 76220737712279557754404788686900390625000*n^22+ 197857283520907926562500000000000*n^27+94352958749363907866504396484375000000*n ^24+3068884483742218404737822737675781250000*n^23+ 20152207135835365131788605349592044929612219053244416*n+ 278859198022359524422735287211916759644168125000*n^16+ 92213325090385430632648490908454969701996097147363328*n^3+ 2080474998228515914562988281250000000*n^25+ 1502797117614494282211200858119144775390625*n^21)/(51+7*n)/(52+7*n)/(53+7*n)/( 54+7*n)/(55+7*n)/(50+7*n)/(439618374907031250000000000*n^21+ 45086004477965390625000000000*n^20+2191960344602325937500000000000*n^19+ 67180653506055291706054687500000*n^18+1456013874290589242568413085937500*n^17+ 23725833300297044793595933593750000*n^16+301697317983804918266837032470703125*n ^15+3066784413682047893999594906396484375*n^14+ 25322557999045322518731906110525390625*n^13+ 171628768613815602092137469732241796875*n^12+ 960889933872152378329623724978562109375*n^11+ 4456765947099768409184288068517226328125*n^10+ 17121843815961035114704287274454129559375*n^9+ 54306151651360640118121509393834121355625*n^8+ 141260473037717326368081393755262941690000*n^7+ 298108295067937217942574220225486761167000*n^6+ 502137362642263302609745265224664852250320*n^5+ 658835303176471908729603972956495216813264*n^4+ 648600963379653918988566086872017317808896*n^3+ 450536788733871546144958372502698056479744*n^2+ 196842716802992174718652323463675073888256*n+ 40680205814089677460397239814128769433600)/(n+8)*f(n+7)+f(n+8) = 0, 14^n*(1/n)^ (1/2)*(1-133/800/n-19093/1792000/n^2+3013597/204800000/n^3+16330884117/ 917504000000/n^4+4947069773703/3670016000000000/n^5-1276965089773528991/ 41104179200000000000/n^6-12047800999029321383/263066746880000000000/n^7+ 396482109833031018965311/8418135900160000000000000/n^8+ 421879590571190591646484249/1346901744025600000000000000/n^9+ 23028886248180185261773271125869/75426497665433600000000000000000/n^10), .\ 89206205807638555726948318628254e-1, 1/20*2^(1/2)*5^(1/2)/Pi^(1/2) ----------------------------------------------------- The Number of Ways a Walker Can Walk n steps on the Discrete Line and End-Up Where it Started Using The set of Steps, {[-7], [-6], [-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5], [6], [7]} By Shalosh B. Ekhad Theorem 1: Let f(n) be the number of ways a walker can walk n steps in the , 1, dimensional lattice and return to the starting point, using the following set of steps: {[-7], [-6], [-5], [-4], [-3], [-2], [-1], [0], [1], [2], [3], [4], [5], [6], [7]} In other words, if today the walker is located at location [n[1]] then tomorrow it is at one of the following locations {[n[1]], [n[1] - 7], [n[1] - 6], [n[1] - 5], [n[1] - 4], [n[1] - 3], [n[1] - 2], [n[1] - 1], [n[1] + 1], [n[1] + 2], [n[1] + 3], [n[1] + 4], [n[1] + 5], [n[1] + 6], [n[1] + 7]} The sequence f(n) satisfies the following recurrence 170859375/7 (8 n + 61) (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) (n + 1) f(n)/((8 n + 15) (7 n + 15) (7 n + 30) (4 n + 15) (7 n + 45) (8 n + 45) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) + 45562500/7 (2 n + 15) (8 n + 61) (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) f(n + 1)/((8 n + 23) (7 n + 22) (4 n + 19) (7 n + 37) (55 + 7 n) (53 + 7 n) (54 + 7 n) (52 + 7 n) (8 n + 53) (n + 8)) - 3037500/7 (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) 7 6 5 4 3 (1392384 n + 44108736 n + 579672820 n + 4085051015 n + 16618944948 n 2 + 38898790027 n + 48355007942 n + 24603750000) f(2 + n)/((8 n + 15) (7 n + 15) (7 n + 30) (7 n + 29) (4 n + 15) (8 n + 31) (7 n + 45) (7 n + 44) (4 n + 23) (8 n + 45) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) - 202500/7 (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) 6 5 4 (8 n + 61) (2 n + 15) (619360 n + 18613980 n + 228030995 n 3 2 + 1455521335 n + 5099100174 n + 9286879696 n + 6868483232) f(n + 3)/( (8 n + 23) (7 n + 22) (8 n + 39) (4 n + 19) (7 n + 37) (7 n + 36) (55 + 7 n) (53 + 7 n) (51 + 7 n) (54 + 7 n) (52 + 7 n) (4 n + 27) (8 n + 53) (n + 8)) + 6750/7 (8 n + 63) (n + 7) (n + 6) (n + 5) ( 10 9 8 7 1528110080 n + 84700958720 n + 2097498913040 n + 30556800492040 n 6 5 4 + 289996995433053 n + 1873318415586649 n + 8341465326247805 n 3 2 + 25280482098449175 n + 49907974035792422 n + 57955727815299096 n + 30063861001800000) f(n + 4)/((7 n + 30) (7 n + 29) (4 n + 15) (8 n + 31) (7 n + 45) (7 n + 44) (8 n + 45) (7 n + 43) (4 n + 23) (8 n + 47) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) + 900/7 (4 n + 31) (8 n + 63) 8 7 (n + 7) (n + 6) (8 n + 61) (2 n + 15) (70075488 n + 3367377468 n 6 5 4 3 + 70499823299 n + 839884979235 n + 6227205463725 n + 29424121458649 n 2 + 86527425085816 n + 144789270171344 n + 105556440058368) f(n + 5)/( (8 n + 39) (4 n + 19) (7 n + 37) (7 n + 36) (55 + 7 n) (52 + 7 n) (53 + 7 n) (50 + 7 n) (54 + 7 n) (51 + 7 n) (8 n + 55) (4 n + 27) 9 8 (8 n + 53) (n + 8)) - 60/7 (n + 7) (165063424 n + 9780007872 n 7 6 5 + 257008395908 n + 3931756342511 n + 38589389864823 n 4 3 2 + 251999442338203 n + 1094955218856561 n + 3052665913581258 n + 4955258819948040 n + 3568405328856000) f(n + 6)/((7 n + 45) (7 n + 44) (8 n + 45) (7 n + 43) (4 n + 23) (8 n + 47) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) - 4/7 (4 n + 31) (8 n + 63) (8 n + 61) (2 n + 15) ( 6 5 4 3 2 1273609 n + 53491578 n + 935879161 n + 8730701028 n + 45803340940 n + 128126815824 n + 149302717920) f(n + 7)/((55 + 7 n) (52 + 7 n) (53 + 7 n) (50 + 7 n) (54 + 7 n) (51 + 7 n) (8 n + 55) (4 n + 27) (8 n + 53) (n + 8)) + f(n + 8) = 0 subject to the initial conditions f(1) = 1, f(2) = 15, f(3) = 169, f(4) = 2255, f(5) = 30381, f(6) = 418503, f(7) = 5832765, f(8) = 82073295 Proof: available upon request, for a $30 donation. For the sake of the OEIS, the first, 30, terms are [1, 15, 169, 2255, 30381, 418503, 5832765, 82073295, 1163205475, 16581420835, 237481736823, 3414582082055, 49258226347903, 712601187601395, 10334165623697259, 150186639579545295, 2186774434431445455, 31893473567409732813, 465851764737061437765, 6813595723342146913635, 99777287907003998125395, 1462734359875651631856025, 21465239104900094010239385, 315286839060080581760557575, 4634934216618907133333180631, 68189961694906266062379979761, 1003947871818461350372097539165, 14790850878997102285050287114419, 218045041061658214650515172707595, 3216267382950968110757474585877733] Theorem 2: Let f(n) be as in Theorem 1. The asymptotics of f(n) to order, 10, is n 1/2 / 339 156997 38958219 759592113141 C 15 (1/n) |1 - ------ - ----------- + ------------- + ----------------- | 2240 n 2 3 4 \ 14049280 n 4495769600 n 56394933862400 n 633799615777047 258393059099566835279 + -------------------- - -------------------------- 5 6 90231894179840000 n 19807705410358476800000 n 69183557460554822331189 823601575480563954358350209 - ---------------------------- - -------------------------------- 7 8 1774770404768119521280000 n 31803885653444701821337600000 n 1842332598136486664445633297759 + ----------------------------------- 9 14248140772743226415959244800000 n 1017543307897855778278348831454412381 \ + -----------------------------------------| 10| 2234108473166137902022409584640000000 n / for some constant C So far everything is rigorous The constant C is estimated to be approximately C = 0.0923371954611859008592554752372168 1/2 1/2 3 7 The EXACT value of the constant C is probably, --------- 1/2 28 Pi The whole thing took, 720.401, seconds. In Maple input format, the linear recurrence, asymptotics, and the constant are 170859375/7*(8*n+61)*(4*n+31)*(8*n+63)*(n+7)*(n+6)*(n+5)*(n+4)*(n+3)*(2+n)*(n+1 )/(8*n+15)/(7*n+15)/(7*n+30)/(4*n+15)/(7*n+45)/(8*n+45)/(55+7*n)/(53+7*n)/(54+7 *n)/(n+8)*f(n)+45562500/7*(2*n+15)*(8*n+61)*(4*n+31)*(8*n+63)*(n+7)*(n+6)*(n+5) *(n+4)*(n+3)*(2+n)/(8*n+23)/(7*n+22)/(4*n+19)/(7*n+37)/(55+7*n)/(53+7*n)/(54+7* n)/(52+7*n)/(8*n+53)/(n+8)*f(n+1)-3037500/7*(4*n+31)*(8*n+63)*(n+7)*(n+6)*(n+5) *(n+4)*(n+3)*(1392384*n^7+44108736*n^6+579672820*n^5+4085051015*n^4+16618944948 *n^3+38898790027*n^2+48355007942*n+24603750000)/(8*n+15)/(7*n+15)/(7*n+30)/(7*n +29)/(4*n+15)/(8*n+31)/(7*n+45)/(7*n+44)/(4*n+23)/(8*n+45)/(55+7*n)/(53+7*n)/( 54+7*n)/(n+8)*f(2+n)-202500/7*(4*n+31)*(8*n+63)*(n+7)*(n+6)*(n+5)*(n+4)*(8*n+61 )*(2*n+15)*(619360*n^6+18613980*n^5+228030995*n^4+1455521335*n^3+5099100174*n^2 +9286879696*n+6868483232)/(8*n+23)/(7*n+22)/(8*n+39)/(4*n+19)/(7*n+37)/(7*n+36) /(55+7*n)/(53+7*n)/(51+7*n)/(54+7*n)/(52+7*n)/(4*n+27)/(8*n+53)/(n+8)*f(n+3)+ 6750/7*(8*n+63)*(n+7)*(n+6)*(n+5)*(1528110080*n^10+84700958720*n^9+ 2097498913040*n^8+30556800492040*n^7+289996995433053*n^6+1873318415586649*n^5+ 8341465326247805*n^4+25280482098449175*n^3+49907974035792422*n^2+ 57955727815299096*n+30063861001800000)/(7*n+30)/(7*n+29)/(4*n+15)/(8*n+31)/(7*n +45)/(7*n+44)/(8*n+45)/(7*n+43)/(4*n+23)/(8*n+47)/(55+7*n)/(53+7*n)/(54+7*n)/(n +8)*f(n+4)+900/7*(4*n+31)*(8*n+63)*(n+7)*(n+6)*(8*n+61)*(2*n+15)*(70075488*n^8+ 3367377468*n^7+70499823299*n^6+839884979235*n^5+6227205463725*n^4+ 29424121458649*n^3+86527425085816*n^2+144789270171344*n+105556440058368)/(8*n+ 39)/(4*n+19)/(7*n+37)/(7*n+36)/(55+7*n)/(52+7*n)/(53+7*n)/(50+7*n)/(54+7*n)/(51 +7*n)/(8*n+55)/(4*n+27)/(8*n+53)/(n+8)*f(n+5)-60/7*(n+7)*(165063424*n^9+ 9780007872*n^8+257008395908*n^7+3931756342511*n^6+38589389864823*n^5+ 251999442338203*n^4+1094955218856561*n^3+3052665913581258*n^2+4955258819948040* n+3568405328856000)/(7*n+45)/(7*n+44)/(8*n+45)/(7*n+43)/(4*n+23)/(8*n+47)/(55+7 *n)/(53+7*n)/(54+7*n)/(n+8)*f(n+6)-4/7*(4*n+31)*(8*n+63)*(8*n+61)*(2*n+15)*( 1273609*n^6+53491578*n^5+935879161*n^4+8730701028*n^3+45803340940*n^2+ 128126815824*n+149302717920)/(55+7*n)/(52+7*n)/(53+7*n)/(50+7*n)/(54+7*n)/(51+7 *n)/(8*n+55)/(4*n+27)/(8*n+53)/(n+8)*f(n+7)+f(n+8) = 0, 15^n*(1/n)^(1/2)*(1-339 /2240/n-156997/14049280/n^2+38958219/4495769600/n^3+759592113141/56394933862400 /n^4+633799615777047/90231894179840000/n^5-258393059099566835279/ 19807705410358476800000/n^6-69183557460554822331189/1774770404768119521280000/n ^7-823601575480563954358350209/31803885653444701821337600000/n^8+ 1842332598136486664445633297759/14248140772743226415959244800000/n^9+ 1017543307897855778278348831454412381/2234108473166137902022409584640000000/n^ 10), .923371954611859008592554752372168e-1, 1/28*3^(1/2)*7^(1/2)/Pi^(1/2) 170859375 (8 n + 61) (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) (n + 1)/(7 (8 n + 15) (7 n + 15) (7 n + 30) (4 n + 15) (7 n + 45) (8 n + 45) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) + 45562500 (2 n + 15) (8 n + 61) (4 n + 31) (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (2 + n) N/(7 (8 n + 23) (7 n + 22) (4 n + 19) (7 n + 37) (55 + 7 n) (53 + 7 n) (54 + 7 n) (52 + 7 n) (8 n + 53) (n + 8)) - 3037500 (4 n + 31) 7 (8 n + 63) (n + 7) (n + 6) (n + 5) (n + 4) (n + 3) (1392384 n 6 5 4 3 + 44108736 n + 579672820 n + 4085051015 n + 16618944948 n 2 2 + 38898790027 n + 48355007942 n + 24603750000) N /(7 (8 n + 15) (7 n + 15) (7 n + 30) (7 n + 29) (4 n + 15) (8 n + 31) (7 n + 45) (7 n + 44) (4 n + 23) (8 n + 45) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) - 202500 (n + 4) (n + 5) (n + 6) (n + 7) (8 n + 63) (4 n + 31) (8 n + 61) 6 5 4 3 (2 n + 15) (619360 n + 18613980 n + 228030995 n + 1455521335 n 2 3 + 5099100174 n + 9286879696 n + 6868483232) N /(7 (8 n + 23) (7 n + 22) (8 n + 39) (4 n + 19) (7 n + 37) (7 n + 36) (55 + 7 n) (53 + 7 n) (51 + 7 n) (54 + 7 n) (52 + 7 n) (4 n + 27) (8 n + 53) (n + 8)) + 6750 10 9 (8 n + 63) (n + 7) (n + 6) (n + 5) (1528110080 n + 84700958720 n 8 7 6 + 2097498913040 n + 30556800492040 n + 289996995433053 n 5 4 3 + 1873318415586649 n + 8341465326247805 n + 25280482098449175 n 2 4 + 49907974035792422 n + 57955727815299096 n + 30063861001800000) N /(7 (7 n + 30) (7 n + 29) (4 n + 15) (8 n + 31) (7 n + 45) (7 n + 44) (8 n + 45) (7 n + 43) (4 n + 23) (8 n + 47) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) + 900 (n + 6) (n + 7) (8 n + 63) (4 n + 31) (8 n + 61) 8 7 6 5 (2 n + 15) (70075488 n + 3367377468 n + 70499823299 n + 839884979235 n 4 3 2 + 6227205463725 n + 29424121458649 n + 86527425085816 n 5 + 144789270171344 n + 105556440058368) N /(7 (8 n + 39) (4 n + 19) (7 n + 37) (7 n + 36) (55 + 7 n) (52 + 7 n) (53 + 7 n) (50 + 7 n) (54 + 7 n) (51 + 7 n) (8 n + 55) (4 n + 27) (8 n + 53) (n + 8)) - 60 9 8 7 6 (n + 7) (165063424 n + 9780007872 n + 257008395908 n + 3931756342511 n 5 4 3 + 38589389864823 n + 251999442338203 n + 1094955218856561 n 2 6 + 3052665913581258 n + 4955258819948040 n + 3568405328856000) N /(7 (7 n + 45) (7 n + 44) (8 n + 45) (7 n + 43) (4 n + 23) (8 n + 47) (55 + 7 n) (53 + 7 n) (54 + 7 n) (n + 8)) - 4 (8 n + 63) (4 n + 31) 6 5 4 (8 n + 61) (2 n + 15) (1273609 n + 53491578 n + 935879161 n 3 2 7 + 8730701028 n + 45803340940 n + 128126815824 n + 149302717920) N /(7 (55 + 7 n) (52 + 7 n) (53 + 7 n) (50 + 7 n) (54 + 7 n) (51 + 7 n) 8 n 1/2 / 339 (8 n + 55) (4 n + 27) (8 n + 53) (n + 8)) + N , 15 (1/n) |1 - ------ | 2240 n \ 156997 38958219 759592113141 633799615777047 - ----------- + ------------- + ----------------- + -------------------- 2 3 4 5 14049280 n 4495769600 n 56394933862400 n 90231894179840000 n 258393059099566835279 69183557460554822331189 - -------------------------- - ---------------------------- 6 7 19807705410358476800000 n 1774770404768119521280000 n 823601575480563954358350209 1842332598136486664445633297759 - -------------------------------- + ----------------------------------- 8 9 31803885653444701821337600000 n 14248140772743226415959244800000 n 1017543307897855778278348831454412381 \ + -----------------------------------------|, 10| 2234108473166137902022409584640000000 n / 1/2 1/2 3 7 0.0923371954611859008592554752372168, --------- 1/2 28 Pi the whole thing took, 1890.878, seconds