I have run into this recurrence relation while trying to solve a problem in probability.
$$ g(r, s) = pg(r - 1, s) + qg(r, s - 1) $$
$$ g(0, s) = 1, g(r, 0) = 0 $$
So far I have concluded that
$$ g(r, s) = \sum_{k = 0}^{s}\binom{r}{k}p^{r - k}q^{k}g(k, s - k) $$
But I'm not sure where to go now...
Define the bivariate generating function $$G(x, y) = \sum_{\substack{r \ge 0 \\ s \ge 0}} g(r, s) x^r y^s$$, shift indices and write:
$\begin{align} g(r + 1, s + 1) = p g(r, s + 1) + q g(r + 1, s) \end{align}$
Multiply by $x^r y^s$, sum over $r \ge 0, s \ge 0$ and get:
$\begin{align} \frac{G(x, y) - G(0, y) - G(x, 0) + G(0, 0)}{x y} = p \frac{G(x, y) - G(x, 0)}{y} + q \frac{G(x, y) - G(0, y)}{x} \end{align}$
Now you need boundary conditions:
$\begin{align} G(x, 0) &= \sum_{r \ge 0} g(r, 0) x^r \\ &= 0 \\ G(0, y) &= \sum_{s \ge 0} g(0, s) y^s \\ &= \frac{1}{1 - y} \end{align}$
Solving for $G(x, y)$:
$\begin{align} G(x, y) &= \frac{1 - q y} {1 - p x - (1 - q) y + p x y + q y^2} \\ &= \frac{1 - q y}{(1 - y) (1 - p x - q y)} \\ &= \frac{1 - q}{1 - q - p x} \cdot \frac{1}{1 - y} + \frac{p q x}{1 - q - p x} \frac{1}{1 - p x - q y} \end{align}$
Now you can expand as geometric series in $y$, and expand the resulting terms again in $x$. You'll get a double sum, out of which to pick the coefficient of $x^r y^s$.