This recurrence relation was inferred from the function $f(n, m) = f(n – 1, m) + f(n, m-1) + c$.
After expanding the latter, I ended up with the following:
$$f(n,m)=\begin{cases}
0,&\text{if }n,m <0\\
1,&\text{if }n,m = 0\\
\sum_{i=0}^{k=n+m-1}\left(\left[f(n-i,m-[k-i])+c\right]\binom{k}{i}\right)-c,&\text{otherwise},
\end{cases}$$
Do you have any idea how to solve this recurrence relation?
Best Answer
You can use bivariate generating functions. I don't know how comfortable you are with that, so I'll show LOTS of steps here! First, define $$ F(x,y):=\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}f(n,m)x^ny^m. $$ First, note that $$ \begin{align*} F(x,y)&=\sum_{n=0}^{\infty}f(n,0)x^n+\sum_{m=0}^{\infty}f(0,m)y^m-1+\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n,m)x^ny^m\\ &=\frac{1}{1-x}+\frac{1}{1-y}-1+\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n,m)x^ny^m, \end{align*} $$ where the $-1$ comes from the fact that we have over-counted the $n=m=0$ term. Applying the recurrence $f(n,m)=f(n-1,m)+f(m-1,n)+c$ for $m,n\geq 1$, we find $$ \begin{align*} \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n,m)x^ny^m&=\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n-1,m)x^ny^m+\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n,m-1)x^ny^m+\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}cx^ny^m. \end{align*} $$ Let's take this term-by-term. First: $$ \begin{align*} \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n-1,m)x^ny^m&=x\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n-1,m)x^{n-1}y^m\\ &=x\sum_{n=0}^{\infty}\sum_{m=1}^{\infty}f(n,m)x^ny^m\\ &=x\left[\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}f(n,m)x^ny^m-\sum_{n=0}^{\infty}f(n,0)x^n\right]\\ &=x\left[F(x,y)-\frac{1}{1-x}\right]. \end{align*} $$ Similarly, $$ \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}f(n,m-1)x^ny^m=y\left[F(x,y)-\frac{1}{1-y}\right]. $$ Finally, $$ \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}cx^ny^m=\sum_{n=1}^{\infty}cx^n\frac{y}{1-y}=\frac{cxy}{(1-x)(1-y)}. $$ So, all told, we find that $F(x,y)$ (after some simplifying) satisfies the functional equation $$ F(x,y)(1-x-y)=\frac{1-x-y+xy(1+c)}{(1-x)(1-y)}, $$ or $$ F(x,y)=\frac{1+c}{1-x-y}-\frac{c}{(1-x)(1-y)}. $$ So, we find that for $n,m\geq 0$, $$ f(n,m)=[x^ny^m]F(x,y)=(1+c)\binom{n+m}{n}-c $$ It is very easy to show that this last term satisfies the recurrence (this is just Pascal's identity, once you write it out), and it satisfies the initial conditions for $n=0$ or $m=0$. We've completely disregarded the terms where $n$ or $m$ is negative; they don't come in to play.