Closed form for the recursion $g(i,j) = g(i-1,j) + g(i,j-1)$

100 Views Asked by At

Consider the function $g$ defined by

$$ g(i,j) = \begin{cases} i \, & \text{ if $\,j = 1$} \\ j \, & \text{ if $\,i = 1$} \\ g(i-1,j) + g(i,j-1) \, & \text{ otherwise } \end{cases} $$

I don't know if a "nice" closed form exists, I tried using the following generating function $G(X,Y) = \sum \sum g(i,j)X^iY^j$ which yields the equation $$G(X) = \frac{XY}{1-(X+Y)}\left(\frac{1-XY^2}{(1-X)^2} + \frac{1-X^2Y}{(1-Y)^2} - 1\right)$$

This seems difficult to get anything useful out of. Is there a better approach?

1

There are 1 best solutions below

3
On BEST ANSWER

The generating function is certainly a way to go, but if you want an alternative, here is one.

Sometimes just looking at the values, trying to guess a formula and then proving it - works just fine... It's not exactly a method you would use on a test, but it can get the job done very often.

In this case we write the values $g(i,j)$ in a table

\begin{array}{} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 7 & 11 & 16\\ 3 & 7 & 14 & 25 & 41\\ 4 & 11 & 25 & 50 & 91\\ 5 & 16 & 41 & 91 & 182\\ \end{array} Now first row/column is obvious, perhaps even the second, the others not so much. You could try to find a pattern in them yourself, however we can simply search the elements in rows/columns in the OEIS sequence database, then for the third row we find an interesting match https://oeis.org/A004006 : $$0, 1, 3, 7, 14, 25, 41, 63, 92, 129, 175, 231,\dots$$ and formula $$ \binom{n}{1}+\binom{n}{2}+\binom{n}{3}. $$ And very similar formula for the fourth row $$ \binom{n-1}{2}+\binom{n-1}{3}+\binom{n-1}{4}. $$ Based on this we conjecture that all elements of the sequence will be of such form, and after some playing with the shift on the indices we find that $$ g(i,j)=\sum_{k=0}^{2}\binom{j+i-2}{i-k}=\binom{j+i-2}{i-2}+\binom{j+i-2}{i-1}+\binom{j+i-2}{i}. $$ So now we just need to prove it, but that's the easiest part. The cases $i=1$ or $j=1$ are straight forward, for example $$ g(1,j)=\binom{j-1}{-1}+\binom{j-1}{0}+\binom{j-1}{1}=0+1+j-1=j $$ and $g(i,1)$ similarly. Note that we have used the standard convention $\binom{n}{k}=0$ for $k<0$.

For the recursive part you just use Pascal's formula ${n-1 \choose k}+{n-1 \choose k-1}={n \choose k}$:

\begin{align} g(i-1,j)+g(i,j-1) &=\sum_{k=0}^{2}\binom{j+i-3}{i-k-1}+\sum_{k=0}^{2}\binom{j+i-3}{i-k}\\ &=\sum_{k=0}^{2}\left[\binom{j+i-3}{i-k-1}+\binom{j+i-3}{i-k}\right]\\ &=\sum_{k=0}^{2}\binom{j+i-2}{i-k}\\ &=g(i,j)\\ \end{align}

Note: You can slightly simplify the expression, for example using again the Pascal's formula and $\binom{n}{k}=\binom{n}{n-k}$ we have $$ \boxed{g(i,j)=\binom{j+i-2}{j}+\binom{j+i-1}{i}.} $$