0

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.

JKnecht
  • 6,543
rkabhishek
  • 115
  • 6
  • If you already see a pattern (and Pascal's triangle sounds good): Can you make a conjecture what the general solution is? Where are you stuck? – Martin R Feb 05 '16 at 17:30
  • I am stuck because even my conjecture involving pascal triangle has recurrence in it. I am not able to get a closed-form solution. May I know How to proceed ? – rkabhishek Feb 06 '16 at 06:17

1 Answers1

0

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.

Brian M. Scott
  • 616,228