How to proceed with this multi-variable recurrence?

Question

I am trying to solve the following recurrence:

$$a_{0,j}=a_{i,0}=1$$ $$a_{i+1,j+1}=a_{i+1,j}+a_{i,j+1}+a_{i,j}$$

Following the method outlined in Concrete Mathematics, I ended up with the following closed form:

$$\sum_{0\le i,j}x^iy^ja_{i,j}={1\over1-x-y-xy}.$$

However, I was not able to find terms for the coefficients. I see two ways to proceed; one leads to an ugly trinomial that doesn't seem to yield anything nice:

$${1\over1-(x+y+xy)}=\sum_{0\le n}(x+y+xy)^n$$

while the other idea works out somewhat nicer:

$${1\over2-(x+1)(y+1)}=\sum_{0\le n}{1\over2^{n+1}}(x+1)^n(y+1)^n.$$

giving me the following infinite sum as an almost-closed form:

$$a_{i,j}=\sum_{0\le n}{1\over2^{n+1}}{n\choose i}{n\choose j}$$

where I have no idea to eliminate the infinite sum.

Proceeding by first solving for $x^i$ and then solving the resulting closed form for $y^j$, we first get

$$\sum_{0\le j}y^ja_{i,j}={(1+y)^n\over(1-y)^{n+1}}$$

and then, extracting the coefficients for $y^j$:

$$a_{i,j}=\sum_{k=0}^j{k+i\choose i}{i\choose j-k}$$

which too looks nice, but I don't quite see a way to get rid of the sum.

What's the best way to proceed here? Just a hint would be nice so I can work out the details myself.

Answer 1

Hint: The numbers $a_{i,j}$ form a sequence \begin{align*} \{1\},\{1,1\},\{1,3,1\},\{1,5,5,1\},\{1,7,13,7,1\},\{1,9,25,25,9,1\},\ldots \end{align*} which is stored as A008288 in OEIS and called the Square array of Delannoy numbers $D(n,k)$ read by antidiagonals.

We find there \begin{align*} \sum_{n \geq 0, k\geq 0} D(n, k)x^ny^k = \frac{1}{1-x-y-xy} \end{align*}

We also find the identities \begin{align*} D(n, k) = \sum_{d} \binom{k}{d}\binom{n+k-d}{k} = \sum_{d} 2^d\binom{n}{d}\binom{k}{d} \end{align*} but regrettably there is no closed formula given, which strongly indicates that no one is available.