# A recurrence relation on two variables

How to solve the recurrence relation for $n >=m$:
$$P_{n,m}=\frac{n}{n+m}P_{n-1, m} + \frac{m}{m+n}P_{n,m-1}$$
$$P_{11}=\frac{1}{2}; P_{i,0}=1 \forall i > 0; P_{i,j}=0 \forall i<j$$

#### Solutions Collecting From Web of "A recurrence relation on two variables"

Hint: Have you tried calculating the first few numbers. There is a interesting pattern.
$$\begin{array}{c|cccc} &0&1&2&3\\ \hline 1&\frac{2}{2} & \frac{3}{3} & \frac{4}{4}& \frac{5}{5}\\ 2&\frac{1}{2} & \frac{2}{3} & \frac{3}{4} & \ddots\\ 3&0 & \frac{1}{3} & \frac{2}{4} & \ddots\\ 4&0 & 0 & \frac{1}{4} & \ddots\\ \end{array}$$

It looks like, that your formular for $P_{n,m}$ is
$$P_{n,m} = \left\{\begin{array}{c,l}0\quad &\text{if }m>n\\ \frac{n+1-m}{n+1}\quad &\text{else}\end{array}\right.$$

Try to proof that by using induction over $n$ and over $m$.