2

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.
Dref D
  • 21
  • Without any initial values, any value will do. I vote for 42. – vonbrand Apr 16 '14 at 13:57
  • 1
    Yes, any sequence whatsoever has a generating function, just declare $A(z) = \sum_{n \ge 0} a_n z^n$ – vonbrand Apr 16 '14 at 14:00
  • "Diophantine equation" is just an equation where you are interested in integer (or natural, rarely rational) solutions. – vonbrand Apr 16 '14 at 14:02
  • Hi! Forgot to mention, this is my attempt: http://ideone.com/KRIjAk . The initial value conditions are specified for p=1 or q=1. Please throw some light on how to find the generating function as well. – Dref D Apr 16 '14 at 16:02
  • What are the exact initial conditions? You need $ways(p, 0)$ and $ways(0, q)$ for all $p$, $q$ (or equivalent) for the recurrence to make sense. – vonbrand Apr 16 '14 at 16:27
  • @vonbrand According to his python source, the initial values are as follows:

    $\begin{align}ways(0, q) &= 0 &ways(p, 0) &= 0 \ ways(1, q) &= q(q-1) &ways(p, 1) &= p(p-1)\end{align}$

    But I'll let the OP confirm.

     – Anant Apr 16 '14 at 16:45
  • @Anant yes, these are the initial conditions – Dref D Apr 18 '14 at 14:07

1 Answers1

1

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.

vonbrand
  • 27,812