Find the generating function for a series , given a recurrence relation I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation:
ways(p,q)=4*min(p-1,q-1)+2*(p-1+q-1)+ways(p-1,q)+ways(p,q-1)-ways(p-1,q-1)

The constraints specified on p,q (both independently) are 10^6, so any brute force attempt will timeout. In order to solve this recurrence I searched on OEIS for smaller values (p=2 , p=3 and so on). However I found only a satisafactory recurrence for (p=2 or q=2) and not for others. Wikipedia suggests that the solutions to this recurrence should be solutions to a Diophantine equation in p,q. Is it so?
To summarize , my question is:
How do I find the generating function of this recurrence. 
Is there any generalized approach for doing so?
What is the role of Diophantine equations?
Does a generating function necessarily exist for all recurrences? (Only asked because of no sequence on OEIS)
If so, then please elaborate.

 A: Write the recurrence in terms of $w(p, q)$ for brevity, and so that there are no subtraction in indices:
$$
w(p + 1, q + 1)
  = 4 \min(p, q) + 2 (p + q)
     + w(p, q + 1) + w(p + 1, q) - w(p, q)
$$
Define the double generating function $W(x, y) = \sum_{p, q} w(p, q) x^p y^q$,
Multiply by $x^p y^q$, sum over $p \ge 0$ and $q \ge 0$. Need a few sums:
\begin{align}
\sum_{p \ge 0} w(p, 0) x^p         
  &= W(x, 0) \\
\sum_{q \ge 0} w(0, q) y^q
  &= W(0, y) \\
\sum_{p, q} w(p, q + 1) x^p y^q
  &= \frac{W(x, y) - W(x, 0)}{y} \\
\sum_{p, q} w(p + 1, q) x^p y^q
  &= \frac{W(x, y) - W(x, 0)}{y} \\
\sum_{p, q} w(p + 1, q + 1) x^p y^q
  &= \frac{W(x, y) - W(0, y) - W(x, 0) + W(0, 0)}{x y}
\end{align}
Lucky of us:
$$
W(0, y) = W(x, 0) = 0
$$
We will use the following fact, given:
$$
A(z) = \sum_{k \ge 0} a_k z^k
$$
then:
$$
\sum_{k \ge 0} k a_k z^k
  = z A'(z)
$$
In particular:
\begin{align}
\sum_{0 \le k < n} k z^k
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1 - z^n}{1 - z} \\
\sum_{k \ge n} n z^k
  &= n z^n \frac{1}{1 - z} \\
\sum_{k \ge 0} \min(k, n) z^k
  &= \sum_{0 \le k < n} k z^k + \sum_{k \ge n} n z^n \\
  &= \frac{z (1 - z^n)}{(1 - z)^2} \\
\sum_{k \ge 0} k z^k
  &= \frac{z}{(1 - z)^2}
\end{align}
In particular:
\begin{align}
\sum_{p, q} (p + q) x^p y^q
  &= \sum_{p, q} p x^p y^q + \sum_{p, q} q x^p y^q \\
  &= \frac{x}{(1 - x)^2 (1 - y)} + \frac{y}{(1 - x) (1 - y)^2} \\
\sum_{p, q} \min(p, q) x^p y^q
  &= \sum_{p \ge 0} x^p \sum_{q \ge 0} \min(p, q) y^q \\
  &= \sum_{p \ge 0} x^p \frac{y - y^{p + 1}}{(1 - y)^2} \\
  &= \frac{y}{(1 - y)^2 (1 - x)} - \frac{y}{(1 - y)^2} \sum_{p \ge 0} x^p y^p \\
  &= \frac{x y}{(1 - x) (1 - y) (1 - x y)}
\end{align}
Recognizing the various parts in the sum alluded to above, then solving for $W(x, y)$ gives:
\begin{align}
W(x, y)
  &= \frac{2 x y (x + y - 3 x y (x + y) + 4 x^2 y^2)}
          {(1 - x)^3 (1 - y)^3 (1 - x y)}
\end{align}
This is the requested generating function. It looks like it can be made to confess the coefficients $w(p, q)$, but I'll leave it here for now.
