On the Generating Functions enumerating walks confined to the Non-Negative H\ alf Line With step-sets that are subsets of , {-2, -1, 0, 1, 2} By Shalosh B. Ekhad It is well known, and not too hard to see, that the generating function enumerating walks confined to the non-negative half-line with ANY given step\ -set is always algebraic. This is true for both the total number and for the walk\ s that end-up at a specific location. In this article we will state and sketch proofs, of the algebraic equations \ satisfied by generating functions that enumerate walks where the step-sets are subsets of {-2, -1, 0, 1, 2} that have at least one positive and at least one negative step. ----------------------------------------------------------- Doing the set, {-2, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 3 3 1 - P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, 1}, with n steps and ending at m, and let f(t,\ x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 4 3 P[1](t) - t - 2 t P[1](t) + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) f(t, x) = 1 + --------------------------------- + t x f(t, x) 2 x Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x f(t, x) = ----------------------------- 3 2 t + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 3 3 1 - Q[0](t) + t Q[0](t) = 0 2 2 4 3 Q[1](t) - t - 2 t Q[1](t) + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x g(t, x) = ----------------------------- 3 2 t + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 3 t) R(t) + t (-2 + 3 t) R(t) + t (-1 + 2 t) R(t) = 0 This ends this article that took, 1.681, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, 0, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, 0, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, 0, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 3 3 1 + (-1 + t) P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, 0, 1}, with n steps and ending at m, and let f\ (t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 2 4 3 -t + (-1 + t) P[1](t) + 2 t (-1 + t) P[1](t) + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) f(t, x) = 1 + --------------------------------- + t f(t, x) + t x f(t, x) 2 x Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x f(t, x) = ----------------------------- 2 3 2 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 3 3 1 + (-1 + t) Q[0](t) + t Q[0](t) = 0 2 2 2 4 3 -t + (-1 + t) Q[1](t) + 2 t (-1 + t) Q[1](t) + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x g(t, x) = ----------------------------- 2 3 2 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 4 t) R(t) + t (-2 + 5 t) R(t) + t (-1 + 3 t) R(t) = 0 This ends this article that took, 1.903, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 1 - P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 1}, with n steps and ending at m, and let f(t,\ x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) f(t, x) = 1 + --------------------- + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = -------------- 2 t + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 2 2 1 - Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = -------------- 2 t + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 1 + (-1 + 2 t) R(t) + t (-1 + 2 t) R(t) = 0 This ends this article that took, 0.575, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 0, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 0, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 0, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 1 + (-1 + t) P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 0, 1}, with n steps and ending at m, and let f\ (t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = ------------------ 2 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 2 2 1 + (-1 + t) Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = ------------------ 2 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 1 + (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0 This ends this article that took, 0.199, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, -1, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, -1, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, -1, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 3 1 - P[0](t) + t P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, -1, 1}, with n steps and ending at m, and let \ f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 2 4 3 -t + (1 - 2 t ) P[1](t) - t (2 + t) P[1](t) + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation f(t, x) = t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t)) 1 + --------------------------------- + --------------------- + t x f(t, x) 2 x x Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x + t P[0](t) x f(t, x) = ------------------------------------------- 3 2 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 3 3 1 - Q[0](t) + t Q[0](t) + t Q[0](t) = 0 2 2 2 4 3 -t + (1 - 2 t ) Q[1](t) - t (2 + t) Q[1](t) + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x g(t, x) = ------------------------------------------- 3 2 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 3 t) R(t) + 2 t (-1 + 2 t) R(t) + t (-1 + 3 t) R(t) = 0 This ends this article that took, 1.776, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, -1, 0, 1} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, -1, 0, 1} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, -1, 0, 1} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 3 1 + (-1 + t) P[0](t) + t P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, -1, 0, 1}, with n steps and ending at m, and l\ et f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 2 4 3 -t + (1 - 2 t - t ) P[1](t) + t (-2 + t) P[1](t) + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t)) f(t, x) = 1 + --------------------------------- + --------------------- 2 x x + t f(t, x) + t x f(t, x) Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x + t P[0](t) x f(t, x) = ------------------------------------------- 2 3 2 t + t x + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 3 3 1 + (-1 + t) Q[0](t) + t Q[0](t) + t Q[0](t) = 0 2 2 2 4 3 -t + (1 - 2 t - t ) Q[1](t) + t (-2 + t) Q[1](t) + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x g(t, x) = ------------------------------------------- 2 3 2 t + t x + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 4 t) R(t) + 2 t (-1 + 3 t) R(t) + t (-1 + 4 t) R(t) = 0 This ends this article that took, 2.260, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 3 3 1 - P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 2}, with n steps and ending at m, and let f(t,\ x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) 2 f(t, x) = 1 + --------------------- + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = -------------- 3 t + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 3 3 1 - Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = -------------- 3 t + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 3 t) R(t) + 3 t (-1 + 2 t) R(t) + t (-1 + 2 t) R(t) = 0 This ends this article that took, 0.841, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 0, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 0, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 0, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 3 3 1 + (-1 + t) P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 0, 2}, with n steps and ending at m, and let f\ (t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) 2 f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = ------------------ 3 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 3 3 1 + (-1 + t) Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = ------------------ 3 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 4 t) R(t) + 3 t (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0 This ends this article that took, 1.323, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, -1, 2} ----------------------------------------------------------- Doing the set, {-2, -1, 0, 2} ----------------------------------------------------------- Doing the set, {-2, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 2 3 4 4 4 5 1 - P[0](t) - t P[0](t) + t (2 + t) P[0](t) - t P[0](t) - t P[0](t) 6 6 + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, 1, 2}, with n steps and ending at m, and let f\ (t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 -t - (-1 + 2 t) (2 t + 1) P[1](t) - t (2 t + 4 t - 1) P[1](t) 3 3 4 4 6 5 + t (-4 + t) P[1](t) + t (-2 + 3 t) P[1](t) + 3 t P[1](t) 7 6 + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) 2 f(t, x) = 1 + --------------------------------- + t x f(t, x) + t x f(t, x) 2 x Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x f(t, x) = ----------------------------- 3 4 2 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 2 3 4 4 4 5 1 - Q[0](t) - t Q[0](t) + t (2 + t) Q[0](t) - t Q[0](t) - t Q[0](t) 6 6 + t Q[0](t) = 0 2 2 -t - (-1 + 2 t) (2 t + 1) Q[1](t) - t (2 t + 4 t - 1) Q[1](t) 3 3 4 4 6 5 + t (-4 + t) Q[1](t) + t (-2 + 3 t) Q[1](t) + 3 t Q[1](t) 7 6 + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x g(t, x) = ----------------------------- 3 4 2 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 9 t) R(t) + t (-9 + 32 t) R(t) + t (70 t + 2 - 29 t) R(t) 2 4 2 2 5 + t (-9 + 32 t) (-1 + 3 t) R(t) + t (-1 + 9 t) (-1 + 3 t) R(t) 3 3 6 + t (-1 + 3 t) R(t) = 0 This ends this article that took, 225.883, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, 0, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, 0, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, 0, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 2 3 4 4 1 + (-1 + t) P[0](t) - t P[0](t) - t (-2 + t) P[0](t) - t P[0](t) 4 5 6 6 + t (-1 + t) P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, 0, 1, 2}, with n steps and ending at m, and le\ t f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 -t - (t + 1) (-1 + 3 t) P[1](t) - t (4 t + t - 1) P[1](t) 3 3 4 4 6 5 + t (-4 + 5 t) P[1](t) + t (-2 + 5 t) P[1](t) + 3 t P[1](t) 7 6 + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) f(t, x) = 1 + --------------------------------- + t f(t, x) + t x f(t, x) 2 x 2 + t x f(t, x) Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x f(t, x) = ----------------------------- 2 3 4 2 t + t x + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 2 3 4 4 1 + (-1 + t) Q[0](t) - t Q[0](t) - t (-2 + t) Q[0](t) - t Q[0](t) 4 5 6 6 + t (-1 + t) Q[0](t) + t Q[0](t) = 0 2 2 -t - (t + 1) (-1 + 3 t) Q[1](t) - t (4 t + t - 1) Q[1](t) 3 3 4 4 6 5 + t (-4 + 5 t) Q[1](t) + t (-2 + 5 t) Q[1](t) + 3 t Q[1](t) 7 6 + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x g(t, x) = ----------------------------- 2 3 4 2 t + t x + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (10 t - 1) R(t) + t (-9 + 41 t) R(t) + t (101 t + 2 - 33 t) R(t) 2 4 2 2 5 + t (-9 + 41 t) (-1 + 4 t) R(t) + t (10 t - 1) (-1 + 4 t) R(t) 3 3 6 + t (-1 + 4 t) R(t) = 0 This ends this article that took, 227.023, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 3 1 - P[0](t) + t P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 1, 2}, with n steps and ending at m, and let f\ (t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) 2 f(t, x) = 1 + --------------------- + t x f(t, x) + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = ------------------- 2 3 t + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 2 2 3 3 1 - Q[0](t) + t Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = ------------------- 2 3 t + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 5 t) R(t) + 4 t (-1 + 3 t) R(t) + t (-1 + 3 t) R(t) = 0 This ends this article that took, 1.060, seconds to produce. ----------------------------------------------------------- Doing the set, {-1, 0, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-1, 0, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-1, 0, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 3 1 + (-1 + t) P[0](t) + t P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-1, 0, 1, 2}, with n steps and ending at m, and le\ t f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t)) 2 f(t, x) = 1 + --------------------- + t f(t, x) + t x f(t, x) + t x f(t, x) x Equivalently, solving for f(t,x) -x + t P[0](t) f(t, x) = ------------------------- 2 3 t + t x + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, We will go backwards!, Define Q[0](t) to be the unique formal power series satisfying the algebraic\ equation claimed in the theorem for P[0](t) 2 2 3 3 1 + (-1 + t) Q[0](t) + t Q[0](t) + t Q[0](t) = 0 and define g(t,x) by -x + t Q[0](t) g(t, x) = ------------------------- 2 3 t + t x + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 6 t) R(t) + 4 t (-1 + 4 t) R(t) + t (-1 + 4 t) R(t) = 0 This ends this article that took, 1.275, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, -1, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, -1, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, -1, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 1 + (-1 - 2 t) P[0](t) + t (2 + 3 t) P[0](t) - t (2 t + 1) P[0](t) 4 4 + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, -1, 1, 2}, with n steps and ending at m, and l\ et f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 2 3 3 t + (-1 + 4 t + t) P[1](t) + 2 t (1 + 3 t) P[1](t) + t (1 + 4 t) P[1](t) 5 4 + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t)) f(t, x) = 1 + --------------------------------- + --------------------- 2 x x 2 + t x f(t, x) + t x f(t, x) Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x + t P[0](t) x f(t, x) = ------------------------------------------- 3 4 2 t + t x + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 3 1 + (-1 - 2 t) Q[0](t) + t (2 + 3 t) Q[0](t) - t (2 t + 1) Q[0](t) 4 4 + t Q[0](t) = 0 2 2 2 3 3 t + (-1 + 4 t + t) Q[1](t) + 2 t (1 + 3 t) Q[1](t) + t (1 + 4 t) Q[1](t) 5 4 + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x g(t, x) = ------------------------------------------- 3 4 2 t + t x + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 4 t) R(t) + 3 t (-1 + 4 t) R(t) + t (-1 + 4 t) R(t) 2 2 4 + t (-1 + 4 t) R(t) = 0 This ends this article that took, 11.014, seconds to produce. ----------------------------------------------------------- Doing the set, {-2, -1, 0, 1, 2} On the Number of Walks In the Non-Negative Discrete Line with Steps Drawn fr\ om the Set, {-2, -1, 0, 1, 2} By Shalosh B. Ekhad Theorem: Let a(n) be the number of walks on the non-negative integers starti\ ng at 0, ending at 0, and always staying in the non-negative integers, where a fundamental step is one of the\ members of set , {-2, -1, 0, 1, 2} Let P[0](t) be the ordinary generating function of the sequence a(n) infinity ----- \ n P[0](t) = ) a(n) t / ----- n = 0 Then P[0](t) satisfies the following algebraic equation 2 2 3 4 4 1 + (-1 - t) P[0](t) + t (2 + t) P[0](t) - t (t + 1) P[0](t) + t P[0](t) = 0 Sketch of Proof: We need to consider ALL walks with n steps that stay in the non-negative int\ egers. Let A(n,m) be the number of such walks still using the step-set, {-2, -1, 0, 1, 2}, with n steps and ending at m, an\ d let f(t,x) be the bivariate generating function infinity /infinity \ ----- | ----- | \ | \ n m| f(t, x) = ) | ) A(n, m) t x | / | / | ----- | ----- | m = 0 \ n = 0 / Note that a(n)=A(n,0). In order to prove our theorem, we need to establish at the same time the fol\ lowing results ----------------------------------------------------------------------------\ ------------------- Fact Number, 1 Let , P[1](t), be the ordinary generating function of the sequence , A(n, 1) infinity ----- \ n P[1](t) = ) A(n, 1) t / ----- n = 0 Then , P[1](t), satisfies the following algebraic equation 2 2 2 3 3 t + (3 t + 2 t - 1) P[1](t) + 2 t (2 t + 1) P[1](t) + t (1 + 3 t) P[1](t) 5 4 + t P[1](t) = 0 ----------------------------------------------------------------------------\ ------------------- ---------------------------------------- The bivariate generating functions f(t,x) obviously satisfies the functional\ equation t (f(t, x) - P[0](t) - P[1](t) x) t (f(t, x) - P[0](t)) f(t, x) = 1 + --------------------------------- + --------------------- 2 x x 2 + t f(t, x) + t x f(t, x) + t x f(t, x) Equivalently, solving for f(t,x) 2 -x + t P[0](t) + t P[1](t) x + t P[0](t) x f(t, x) = ------------------------------------------- 2 3 4 2 t + t x + t x + t x + t x - x This functional equation uniquely determines f(t,x) and we have to prove tha\ t P[0](t)=f(t,0) satisfies the algebraic equation of the theorem, and P[i](t), the coefficient of x^i in f(t,x), for i from 1 to, 1, satisfy the algebaric equations in the Facts We will go backwards!, Define Q[i](t) for i from 0 to, 1, to be the unique formal power series satisfying the algebraic equation of the Theorem and the, 1, facts. In other words 2 2 3 4 4 1 + (-1 - t) Q[0](t) + t (2 + t) Q[0](t) - t (t + 1) Q[0](t) + t Q[0](t) = 0 2 2 2 3 3 t + (3 t + 2 t - 1) Q[1](t) + 2 t (2 t + 1) Q[1](t) + t (1 + 3 t) Q[1](t) 5 4 + t Q[1](t) = 0 and define g(t,x) by 2 -x + t Q[0](t) + t Q[1](t) x + t Q[0](t) x g(t, x) = ------------------------------------------- 2 3 4 2 t + t x + t x + t x + t x - x It is purely routine to find an algebraic equation F(t,x,g(t,x))=0 satisfied\ by g(t,x) then it is routine to check that it has a unique formal power series in t wi\ th coefficients that are polynomials in x it is also routine to check that g(t,0) satisfies the same algebraic equatio\ n as in theorem it is also routine to check that the coefficient of x^i of g(t,x), satisfies\ the algebraic equations for P[i](t) and Q[i](t) for i from 1 to, 1 Finally checking the functional equation with f(t,x) replaced by g(t,x) is a\ routine calculation in the Schutzenberger ansatz hence it suffices to check it for sufficiently many initial terms. But we al\ ready did that! It follows by uniqueness that f(t,x)=g(t,x) and hence that P[0](t)=Q[0](t) .\ QED! As a corollary, by plugging-in x=1 in the F(t,x,g(t,x) ) =0, we get that R(t)=f(t,1),(alias g(t,1)), the generating function for all walk\ s that never go negative, regardless of destination satisfies the algebraic equation 2 2 3 1 + (-1 + 5 t) R(t) + 3 t (-1 + 5 t) R(t) + t (-1 + 5 t) R(t) 2 2 4 + t (-1 + 5 t) R(t) = 0 This ends this article that took, 7.657, seconds to produce. This ends this webbook that took, 2315.895, to generate -------------------------------------------------------------