Theorem: Let F(m,n) be the number of lattice paths from (0,0) to (m,n)

         in the positive quadrant of the two-dimensional square lattice

                        where the Fundamental Steps are

                            {[0, 1], [1, 0], [1, 1]}

   Let M and N be the shift operators in the m and n directions, respectively

                    (M f(m,n):=f(m+1,n), Nf(m,n):=f(m,n+1) )

              Then F(m,n) satisfies the following pure recurrences

            (1 + m) F(m, n)   (1 + 2 n) F(1 + m, n)
          - --------------- - --------------------- + F(2 + m, n) = 0
                 2 + m                2 + m



            (1 + n) F(m, n)   (1 + 2 m) F(m, 1 + n)
          - --------------- - --------------------- + F(m, 2 + n) = 0
                 2 + n                2 + n

                  Proof: We will only do the first recurrence

We have to prove that F(m,n) is annihilated by the operator, let's call it Q\
    :=

                             1 + m   (1 + 2 n) M    2
                           - ----- - ----------- + M
                             2 + m      2 + m

                                 or equivalenty

                                                2      2
                        -1 - m - M - 2 M n + 2 M  + m M

      We know, by the obvious combinatorics, that F(m,n) is annihilated by

                                M N - M - N - 1

                   The sequence of successive commutators is

                         [(M - 1) M (M N - M - N - 1)]

As you can see, the last entry, (M - 1) M (M N - M - N - 1), is a multiple of ,

    M N - M - N - 1

The proof follows by backwards induction, after checking the boundary condit\
    ions

                                      QED .

             ------------------------------------------------------

               The whole thing took , 1.281, seconds of CPU time