How to solve this 2-D recurrence relation?

55 Views Asked by At

I am trying to solve this recurrence relation:-

$$F(A,B)=\frac{F(A,B-1)F(A-1,B-1)}{F(A,B-1)-F(A-1,B-1)} ;\ F(A,1)=A$$

Please help in finding the general term of it.

1

There are 1 best solutions below

0
On BEST ANSWER

Write down the first few rows, notice the general formula, and prove it by induction. $$\begin{array}{c|ccccc} B\backslash A & 1& 2& 3& 4& 5 \\ \hline 1& 1& 2& 3& 4& 5 \\ 2& 0& 2& 6& 12& 20 \\ 3& 0& 0& 3& 12& 30 \\ 4& 0& 0& 0& 4& 20 \\ 5& 0& 0& 0& 0& 5 \end{array}$$

Looks like $F(A,B)=A\cdot C_{A-1}^{B-1}$, or $A!\over(A-B)!(B-1)!$.