## Monday, June 25, 2012

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