# What is the direct proof of the recurrence relation about lattice path enumeration given by Bizley?

Let $$k$$ be a nonnegative integer and let $$m,n$$ be coprime positive integers. Let $$\phi_k$$ be the number of lattice paths from $$(0,0)$$ to $$(km,kn)$$ with steps $$(0,1)$$ and $$(1,0)$$ that are never rising above the line $$my=nx$$. A path having this property will be called a $$\phi$$-path. Then, $$\phi_k$$ satisfies the recurrence relation $$k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j}$$ for all $$k \in \mathbb{Z}^+$$, as shown by Bizley (1954).

Bizley has stated that “these relations can be deduced directly by general reasoning from the geometrical properties of the paths”. However, I could not manage to obtain a combinatorial proof of this theorem.

Question: What is the direct proof of the recurrence relation mentioned above?

My first thought about this relation was that the left-hand side of the equation counts the number of the cyclical permutations of all $$\phi$$-paths from $$(0,0)$$ to $$(km,kn)$$. In his paper, Bizley defines the highest point of a lattice path as “a lattice point $$X$$ on the path such that the line of gradient $$\frac{n}{m}$$ through $$X$$ cuts the y-axis at a value of $$y$$ not less than that corresponding to any other lattice point of the path”. (It is important to note that the first point $$(0,0)$$ is regarded as not belonging to the path.) Thus, the number of the cyclical permutations of all $$\phi$$-paths may be expressed as the sum of $$t$$ times the number of all the lattice paths with exactly $$t$$ highest points for all $$t=1,2,\ldots,k$$. However, apparently the right-hand side of the equation has nothing to do with the number of the lattice paths with a specified number of highest points.

I am afraid I am missing something obvious about the geometrical properties of the $$\phi$$-paths and I would be so glad if anyone can provide a combinatorial proof or trick that I could not manage to see. Thanks for your attention in advance.

The trick is to add $$\phi_k$$ to both sides of the equation, and interpret the left hand side as counting paths with a prepended horizontal step, and one of its steps marked. Then, make the marked step the first step of a path from $$(-1, 0)$$ to $$(km, kn)$$. Let $$j$$ be minimal such that this path hits $$(jm, jn)$$ and stays below $$my = nx$$ after that. Then the steps before the meeting point, excluding the final horizontal step, form an arbitrary path counted by the binomial coefficient in the summand with index $$j$$, and the remaining steps form a path counted by $$\phi_{k-j}$$.