Solve a recursive equation about chess

Question

If we know that the King stands in the square on the left side at the bottom and has each time 3 possible moves:

he goes 1 square to right
he goes 1 square up
he moves diagonally to the right

so if he start from the square f(1,1) then to know how many possibilities there are to get to square f(m,n) then we can use this equation : $$ f(m,n)=f(m-1,n-1)+f(m-1,n)+f(m,n-1) $$ The question is how to prove that this equation down is a solution of equation for $f(n,n)$ : $$ f(n, n) =\sum_{i=0}^{n-1} {n-1\choose i} {n-1+i \choose i} $$

Answer 1

We start for convenience only with $f(0,0)=1$ instead of $f(1,1)=1$ and with boundary conditions $f(m,0)=f(0,n)=1$ with integral $m,n\geq 0$. Since each step of length $1$ can be encoded with $$x+xy+y$$ we obtain the generating function \begin{align*} F(x,y)&=\sum_{m=0}^\infty\sum_{n=0}^\infty f(m,n)x^my^n\tag{0}\\ &=\sum_{j=0}^\infty(x+xy+y)^j\\ &=\frac{1}{1-(x+xy+y)} \end{align*}

We calculate $f(n,n)=[x^ny^n]F(x,y)$ with $n\geq 0$ by noting that we can take $n$ up to $2n$ steps in order to go from $(0,0)$ to $(n,n)$. We obtain \begin{align*} \color{blue}{f(n,n)}&=\sum_{j=n}^{2n}[x^ny^n](x+xy+y)^j\\ &=\sum_{j=n}^{2n}[x^ny^n]\sum_{l=0}^j\binom{j}{l}x^l(1+y)^ly^{j-l}\tag{1}\\ &=\sum_{j=n}^{2n}[y^n]\binom{j}{n}(1+y)^ny^{j-n}\tag{2}\\ &=\sum_{j=n}^{2n}\binom{j}{n}[y^{2n-j}](1+y)^n\tag{3}\\ &=\sum_{j=0}^n\binom{n+j}{n}[y^{n-j}](1+y)^n\tag{4}\\ &=\sum_{j=0}^n\binom{n}{n-j}\binom{n+j}{n}\tag{5}\\ &\,\,\color{blue}{=\sum_{j=0}^n\binom{n}{j}\binom{n+j}{j}}\tag{6} \end{align*} and the claim follows since starting with $f(1,1)=1$ means reducing the path length by one which is replacing $n$ with $n-1$ in (6).

Comment:

• In (1) we apply the binomial theroem to $(x(1+y)+y)^j$.

• In (2) we select the coefficient of $x^n$.

• In (3) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (4) we shift the index to start with $j=0$.

• In (5) we select the coefficient of $y^{n-j}$.

• In (6) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

Note: The numbers $f(n,n)$ are the Central Delannoy numbers archived in OEIS.

Add-on: We can derive the generating function $F(x,y)$ from the recurrence relation in a somewhat more detailed manner as follows.

We obtain \begin{align*} \sum_{m=1}^\infty\sum_{n=1}^\infty f(m,n)x^my^n&=\sum_{m=1}^\infty\sum_{n=1}^\infty f(m-1,n-1)x^my^n +\sum_{m=1}^\infty\sum_{n=1}^\infty f(m-1,n)x^my^n\\ &\qquad+\sum_{m=1}^\infty\sum_{n=1}^\infty f(m,n-1)x^my^n\\ &=xy\sum_{m=0}^\infty\sum_{n=0}^\infty f(m,n)x^my^n+x\sum_{m=0}^\infty \sum_{n=1}^\infty f(m,n)x^my^n\\ &\qquad+y\sum_{m=1}^\infty\sum_{n=0}^\infty f(m,n)x^my^n\\ F(x,y)-\frac{1}{1-x}-\frac{1}{1-y}+1&=xyF(x,y)+x\left(F(x,y)-\frac{1}{1-x}\right)\\ &\qquad+y\left(F(x,y)-\frac{1}{1-y}\right)\\ F(x,y)&=\frac{1}{1-x-y-xy} \end{align*}