How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c? 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?
 A: 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.
