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