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?
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 (here is the link to the topic):
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.
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.
