A combinatorial proof of the recurrence for rook paths (Q426830)

Summary: Let \(a_n\) count the number of 2-dimensional rook paths \(\mathcal{R}_{n,n}\) from \((0,0)\) to \((2n,0)\). Rook paths \(\mathcal{R}_{m,n}\) are the lattice paths from \((0,0)\) to \((m+n,m-n)\) with allowed steps \((x,x)\) and \((y,-y)\) where \(x,y\in\mathbb{N}^{+}\). In answer to the open question proposed by \textit{M. Erickson}, \textit{S. Fernando} and \textit{K. Tran} [Bull. Inst. Comb. Appl. 60, 37--48 (2010; Zbl 1244.05041)], we present a combinatorial proof for the recurrence of \(a_n\), i.e., \((n+1)a_{n+1}+9(n-1)a_{n-1}=2(5n+2)a_n\) with initial conditions \(a_0=1\) and \(a_1=2\). Furthermore, our proof can be extended to show the recurrence for the number of multiple Dyck paths \(d_n\), i.e., \((n+2)d_{n+1}+9(n-1)d_{n-1}=5(2n+1)d_n\) with \(d_0=1\) and \(d_1=1\), where \(d_n=\mathcal{N}_n(4)\) and \(\mathcal{N}_n(x)\) is Narayana polynomial.