Finding a closed form for a given sequence While studying induction, I came across this question where first I had to find closed form for this sequence:
$$g(i,j) =\cases{0,&$i = j = 0$\\
i, &$j = 0$\\
j,&$i = 0$\\
g(i-1,j) + g(i,j-1)& $i\geq1, j \geq1$}$$
I came to know the answer was$$ \frac{(i+j)!}{(i-1)! (j+1)!} + \frac{(i+j)!}{(i+1)! (j-1)!}$$
I was able to verify this using double induction but how to find a closed form for a sequence like this?
An informal proof would suffice.Please don't ignore.
 A: Consider the following grid graph, where each intersection is has a vertex. Then $g(i, j)$ is the number of ways to travel from the start node (green) to the end node (red) by moving only rightwards or downwards.

Why is this so? If you have learnt dynamic programming before, it is quite easy to see. Otherwise, I will try to explain. Label the green node $(i, j)$. When you move right, the label becomes $(i, j-1)$. When you move down, the label is $(i-1, j)$. Labelling all the nodes in this manner, we have that the missing node (indicated by the black circle) would have been labelled $(0, 0)$ and the red node labelled $(-1, -1)$.
To clear up some potential confusions, note that the indices of the bottommost row and the rightmost column are $-1$.
Let $f(i, j)$ be the number of ways to travel from vertex $(i, j)$ to the red node.
Then we have the recurrence relation $f(i, j) = f(i-1, j) + f(i, j-1)$. Also, it is easy to see the base cases all hold: $f(0, j) = j$ for all $j$, $f(i, 0) = i$ for all $i$, and since vertex $(0, 0)$ doesn't exist, so we just set $f(0, 0) = 0$.
This gives a recurrence for $f(i,j)$ which is precisely the same as your $g(i, j)$.
Now, lets compute a closed form for $f(i, j)$. To do this, imagine you add back the vertex $(0, 0)$ to get a extended grid. Then the number of paths $f(i,j)$ is the number of paths (from green to red) on the extended grid, minus the number of paths passing through $(0, 0)$. This is given by the formulas
\begin{align*}
{i+j+2 \choose i+1} - 2{i+j \choose i} 
&= \frac{(i+j+2)!}{(i+1)!(j+1)!} - 2\frac{(i+j)!}{i! j!} \\
&= \dotsm \\
&= \frac{(i+j)! \left((j(j+1) + i(i+1) \right)}{(i-1)!(j-1)!}
\end{align*}
which you can check equals to the formula you have given.
