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.