# 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)$.

• Generating functions might be perhaps of use, this one has a nice g.f. $\frac{1}{(x-1)(xy+y-1)}$. – Sil Dec 19 '16 at 21:08

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)$:
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}\right)+xy\sum_{i,j\geq0}a_{i,j} x^{i} y^{j}\\ &= y\left(f(x,y)-\sum_{j\geq0}a_{0,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 $$a_{i,j} = \sum_{k=0}^{i-1}\binom{j-1}{k}.$$