Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$

How to approach the following two dimensional recurrence relation ?

For $i,j\ge2$, $$a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$$ where $a_{p,\ 1}=1$ (for $p\ge1$) and $a_{1,\ q} = 1$ (for $q\ge1)$.

One way to go about this, and generally about solving recurrence relations, is to use generating functions. In this case this will lead to bivariate generating function.

Let's suppose we have $f(x,y)=\sum_{i,j=0}^{\infty}a_{i,j} x^i y^j$ formal powers series which encodes coefficients of our sequence. To simplify further computation, I have shifted the sequence so that $a_{0,q}=a_{p,0}=1$, but don't worry about that, it is shifted back at the end. Let's play with coefficients a little to see if we can get better form of $f(x,y)$:

\begin{align} f(x,y)&=\sum_{i,j\geq0}a_{i,j} x^i y^j \\ &=a_{0,0}+\sum_{i\geq 1}a_{i,0} x^i+\sum_{j\geq 1}a_{0,j} y^j + \sum_{i,j\geq1}a_{i,j} x^i y^j \\ \end{align}

We have shifted the indices so that we can later apply recurrence relation. But before proceeding, notice $a_{0,0}=1$ and also $$ \sum_{i\geq1}a_{i,0} x^i = x+x^2+x^3+\dots = \frac{x}{1-x} $$ and similarly for the second sum. So overall we have $$ f(x,y) = 1+\frac{x}{1-x}+\frac{y}{1-y}+\sum_{i,j\geq1}a_{i,j} x^i y^j $$ For the rightmost sum, we can apply recurrence relation, lets write \begin{align} \sum_{i,j\geq1}a_{i,j} x^i y^j &= \sum_{i,j\geq1}(a_{i,j-1}+a_{i-1,j-1}) x^i y^j \\ &= \sum_{i,j\geq1}a_{i,j-1} x^i y^j+\sum_{i,j\geq1}a_{i-1,j-1} x^i y^j \\ &= y\sum_{i,j\geq1}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j\geq1}a_{i-1,j-1} x^{i-1} y^{j-1}\\ \end{align} We have moved the $x$,$y$ out of the sum, so that indices match. Let's just re-index the sum \begin{align} \sum_{i,j\geq1}a_{i,j} x^i y^j &= y\sum_{i,j\geq1}a_{i,j-1} x^i y^{j-1}+xy\sum_{i,j\geq1}a_{i-1,j-1} x^{i-1} y^{j-1}\\ &= y\sum_{i\geq1,j\geq0}a_{i,j} x^i y^{j}+xy\sum_{i,j\geq0}a_{i,j} x^{i} y^{j}\\ &= y\left(\sum_{i\geq0,j\geq0}a_{i,j} x^i y^{j}-\sum_{j\geq0}a_{0,j}y^j\right)+xy\sum_{i,j\geq0}a_{i,j} x^{i} y^{j}\\ &= y\left(f(x,y)-\sum_{j\geq0}a_{0,j}y^j\right)+xyf(x,y)\\ &= y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\ \end{align} Here we have just substituted back the definition of $f(x,y)$ itself. Putting back together we have \begin{align} f(x,y)=1+\frac{x}{1-x}+\frac{y}{1-y}+ y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\ \end{align} and after some simple algebraic manipulations we finally get: \begin{align} f(x,y) = \frac{1}{(1-x)(1-y-xy)}\\ \end{align} The $f(x,y)$ encodes all of the coefficients in a compact way. We can try to write it in a way that will allow us to see the coefficients more clearly.

For this notice that $\frac{1}{1-x}=1+x+x^2+x^3+\dots$. Also second expression is well known generating function $$\frac{1}{1-y-yx}=\frac{1}{1-y(x+1)}=\sum_{i,j\geq0}\binom{j}{i} x^i y^j.$$ So we can view our function in this form as a product $$ f(x,y) = (1+x+x^2+x^3+\dots) \left(\sum_{i,j\geq0}\binom{j}{i} x^i y^j\right) $$

Now to ask what is the value of $a_{i,j}$ is same as to ask what coefficient of $x^i y^j$ is in this product. It is not hard to see that it will be $\binom{j}{i}+\binom{j}{i-1}+\dots+\binom{j}{0}$. So overall, also with correcting the original offset from $i$ to $i-1$ and $j$ to $j-1$, we get the following,

$$a_{i,j} = \sum_{k=0}^{i-1}\binom{j-1}{k}.$$