I have the following recurrence relation and boundary condition?
$$
f(n,m) = \frac{\alpha n}{n+m} f(n-1,m) + \frac{\beta m}{n+m} f(n,m-1) + 1
$$


$$
f(n,0) = \frac{1-\alpha^{n+1}}{1-\alpha}, f(0,m) = \frac{1-\beta^{m+1}}{1-\beta}
$$
Is it possible to get a exact solution for this recurrence relation?



How to solve recurrence relation with 2 variables？
Let
$$g(n,m)=\sum\limits\_{i=0}^{n}\sum\limits\_{j=0}^{m}\binom{i+j}{j}\binom{n-i+m-j}{m-j}\alpha^i\beta^j$$
I conjecture that
$$g(n,m)=\binom{n+m}{m}f(n,m)$$
Here is the PARI prog to verify this conjecture:



```
f(n, m) = if(n==0 || m==0, (m==0)*(1 - a^(n+1))/(1-a)+(n==0)*(1 - b^(m+1))/(1-b)-(n==0 && m==0), a*n/(n+m)*f(n-1, m)+b*m/(n+m)*f(n, m-1)+1)
g(n, m) = sum(i=0, n, sum(j=0, m, binomial(i+j,j)*binomial(n-i+m-j,m-j)*a^i*b^j))
test(n, m) = g(n, m)==binomial(n+m, m)*f(n, m)
n=6; x=sum(i=0, n, sum(j=0, n, test(i, j)))

```

Here is the proof of a user with the nickname **svv** on a scientific forum [dxdy.ru](https://dxdy.ru/) (here is the [link to the topic](https://dxdy.ru/topic154023.html)):


Let
$$g(n,m)=\binom{n+m}{m}f(n,m)$$
Then we have
$$g(n,m)=\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}$$
If we make a little change
$$g(n,m)=[n\geqslant 0]\cdot[m\geqslant 0]\cdot\left(\alpha\,g(n-1,m)+\beta\,g(n,m-1)+\binom{n+m}{m}\right)$$
where square brackets denote Iverson brackets, then the basic conditions given for $f(n,0)$ and $f(0,m)$ holds.


From the recurrence relation and $g(0,0)=1$ it follows that $g(n,m)$ as a polynomial of $\alpha,\beta$ for $n,m\geqslant 0$ has degree $n$ by $\alpha$ and degree $m$ by $\beta$:
$$g(n,m)=\sum\limits\_{i=0}^n \sum\limits\_{j=0}^m c\_{n,m}^{i,j} \alpha^i \beta^j$$


Substitute this into a recurrence relation and equate the coefficients at the same degrees of $\alpha$ and $\beta$. Then we have
$$c\_{n,m}^{i,j}=\begin{cases}\binom{n+m}{m}&\text{if}\;i=j=0\\c\_{n-1,m}^{i-1,j}+c\_{n,m-1}^{i,j-1}&\text{otherwise}\end{cases}$$


Note that the differences between the first lower and first upper indices are the same in all terms: $n-i=(n-1)-(i-1)$. Similarly, the differences between the second lower and second upper indices are the same. This suggests using (maybe temporarily) other coefficients, more invariant, so to speak, instead of $c$:
$$d\_{p,q}^{i,j}=c\_{p+i,q+j}^{i,j},\quad c\_{n,m}^{i,j}=d\_{n-i,m-j}^{i,j}$$


Then we have
$$d\_{p,q}^{i,j}=\begin{cases}\binom{p+q}{q}&\text{if}\;i=j=0\\d\_{p,q}^{i-1,j}+d\_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$


If the conditions had the form
$$d\_{p,q}^{i,j}=\begin{cases}1&\text{if}\;i=j=0\\d\_{p,q}^{i-1,j}+d\_{p,q}^{i,j-1}&\text{otherwise}\end{cases}$$
then the solution would be
$$d\_{p,q}^{i,j}=\binom{i+j}{j}$$
For the proof, see [this answer](https://math.stackexchange.com/a/698182/929945).


Due to the linearity of the recurrence relation, if now $d\_{p,q}^{0,0}$ is multiplied by the coefficient $\binom{p+q}{q}$, that is, take $d\_{p,q}^{0,0}=\binom{p+q}{q}$, all other $d\_{p,q}^{i,j}$ will be multiplied by the same coefficient, so we get
$$d\_{p,q}^{i,j}=\binom{i+j}{j}\binom{p+q}{q}$$
Returning to $c\_{n,m}^{i,j}$, we get the explicit form
$$c\_{n,m}^{i,j}=\binom{i+j}{j}\binom{n-i+m-j}{m-j}$$
and the desired formula.


