I have a recurrence relation defined as :
$A(i, j) = A(i, j-1) + A(i+1, j)$
where both $i$ and $j$ are less than a fixed variable $N$.
Also,
$A(i,1) = 1\:\:$ for all $1 \leq i \leq N$.
$A(N, j) = 1\:\:$ for all $1 \leq j \leq N$.
How do I proceed to solve this equation?
I tried to expand this recurrence relation and got a pattern involving Pascal triangle but then again I got stuck.
For fixed $N$ you have an $N\times N$ matrix $A$. Flip the matrix upside down and index the rows and columns by $0,\ldots,N-1$ instead of $1,\ldots,N$ to get $B$, defined by
$$B(i,j)=A(N-i,j+1)$$
for $0\le i,j<N$. Taking $N=5$ as an example, $A$ is given by the following array:
$$\begin{array}{c|cc} i\backslash j:&1&2&3&4&5\\ \hline 1&1&5&15&35&70\\ 2&1&4&10&20&35\\ 3&1&3&6&10&15\\ 4&1&2&3&4&5\\ 5&1&1&1&1&1\\ \end{array}$$
And $B$ is:
$$\begin{array}{c|cc} i\backslash j:&0&1&2&3&4\\ \hline 0&1&1&1&1&1\\ 1&1&2&3&4&5\\ 2&1&3&6&10&15\\ 3&1&4&10&20&35\\ 4&1&5&15&35&70\\ \end{array}$$
This is clearly just part of Pascal’s triangle in one of its rectangular forms: $B(i,j)=\binom{i+j}j$. Since $A(i,j)=B(N-i,j-1)$ for $1\le i,j\le N$, we conjecture that
$$A(i,j)=\binom{N-i+j-1}{j-1}\tag{1}$$
for $1\le i,j\le N$. You can easily verify that $(1)$ satisfies the boundary conditions on $A$, and the recurrence for $A$ is just Pascal’s recurrence in the form
$$\binom{N-i+j-1}{j-1}=\binom{N-i+j-2}{j-2}+\binom{N-i+j-2}{j-1}\;,$$
so $(1)$ is correct.