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.
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.