Another Nice Application of Difference Equations

Here's a nice problem I encountered in a course on applied stochastic processes.

Problem:

Show that the set of all pairs of positive integers can be placed into one-one correspondence with the positive integers by giving an explicit one-one mapping between the two sets.

Solution:

This can be done expediently using the theory of partial difference equations. A standard diagonalization can be characterized by the following relations:

1. \( f(1,1)=1 \)
2. \( f(x,y) = f(x-1,y)+x+y \)
3. \( f(x,y) = f(x,y-1)+x+y-1 \)

These can be written in difference notation as:

1. \( f(1,1)=1 \)
2. \( \frac{\Delta f}{\Delta x} = x+y \)
3. \( \frac{\Delta f}{\Delta y} = x+y-1 \)

Equation 2 gives \( \frac{{\Delta}^2 f}{{\Delta x}{\Delta y}} = 1 \) and equation 3 gives \( \frac{{\Delta}^2 f}{{\Delta y}{\Delta x}} = 1, \) so this is an exact partial difference equation. Summing using equation 2, \[ f(x,y) = x(x+1)/2 + xy + g(y). \] Differencing and setting this equal to equation 3, \[ x+\frac{\Delta g}{\Delta y} = x+y-1 \] and so \( g(y) = y(y+1)/2 - y + C \) . Finally \( f(1,1)=1 \) implies that \( C=-1 \) , and so \[ f(x,y) = x(x+1)/2 + xy + y(y+1)/2 - y - 1. \]