Welcome to NRICH.

 
Unique representation of Natural Numbers
By Philip Ellison on Thursday, January 03, 2002 - 12:49 pm:

The formula 1/2((a+b)2+3a+b) always uniquely represents the natural numbers (a,b) as another natural number. Why?

By Kerwin Hui on Thursday, January 03, 2002 - 04:20 pm:

Actually, what you are required to prove is that

f(a,b)=½[(a+b)2+3a+b]

is an injection N®N, i.e.

f(a,b) is natural for a,b naturals, and
f(a,b)=f(c,d) Þ (a=c and b=d)

Kerwin

By Philip Ellison on Thursday, January 03, 2002 - 05:24 pm:

Erm, actually I was wondering how you proved that it is unique. Any thoughts?

By Kerwin Hui on Thursday, January 03, 2002 - 06:29 pm:

Here is one way:-

First, we establish a bound on a+b (It is very easy). Now go through the possible values to show that at most one works.

Kerwin

By Philip Ellison on Thursday, January 03, 2002 - 09:06 pm:

What is a "bound on a+b"?
Sorry, I haven't had much experience with proofs (well, I've done P1, but that's about it!), or number theory for that matter...

By Dan Goodman on Friday, January 04, 2002 - 03:01 am:

There's a better way of thinking about this. If you imagine a grid where each point has two natural number coordinates. Now, start at the point (0,0), then go to (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (3,1) and so on. If you draw a picture you will see that this is just drawing diagonal lines (each from bottom right to top left) through all the grid points, starting from (0,0) and moving outwards. Now, suppose you want to count how many grid points you've moved through to get to the point (a,b), if we can find a formula for this then we know that this formula uniquely represents each pair of natural numbers (a,b) with a single natural number n, because of the geometric construction. Clearly any point (a,b) is specified precisely by how many points you go through to get to it using the diagonal lines procedure, and also every point (a,b) corresponds to a unique n.

You can work out how many points you pass through to get to (a,b) and I think it should turn out to be your equation above. What you do is draw a diagonal line from your point (a,b) to (I think) (a+b,0). Now, draw the diagonal from (a+b-1,0) to (0,a+b-1). To get to (a,b) we had to pass through all the points in the triangle with vertices (0,0), (a+b-1,0), (0,a+b-1) and the points on the diagonal from (a+b,0) to (a,b). Count the points in the triangle using the formula for the sum of the first n integers, and the points on the diagonal in the obvious way. Add them together and you should get your equation.

It might be that you have to use the natural numbers as meaning 1,2,3,... instead of 0,1,2,.... In which case, you have to start at (1,1) then go to (2,1), (1,2), (3,1),(2,2),(1,3), and so on.

Does that make sense?

By Philip Ellison on Friday, January 04, 2002 - 02:16 pm:

Errr...not really!
Viewing the pair of numbers as coordinates helps, but I don't understand what you mean when you say that a point is specified precisely by how many points you pass through to get to it. Wouldn't then (a,b) be the same as (b,a), or have I missed the point entirely? (very likely!)

By Dan Goodman on Friday, January 04, 2002 - 10:49 pm:

OK, here's a picture of what I mean:

Grid of natural numbers

What I mean by the number of points you go through to get to (a,b) is the number of points on the grid you pass through if you move along the red line in the direction of the arrows. The green numbers next to each grid point give the number of points you had to pass through to get to that point. If you work out (1/2)((a+b)2+a+3b) for a point (a,b) and then look at the green number next to the point in the diagram, you'll find that they're the same.

Does the diagram explain it?

The reason for thinking about it this way rather than just looking at the equation is that: (1) this diagram is where the formula comes from. (2) The diagram makes it clear that the formula gives a unique natural number for each pair (a,b) and also that every natural number n corresponds to exactly one point (a,b).

By Philip Ellison on Saturday, January 05, 2002 - 11:06 am:

Yeah, thanks...I just didn't understand your description before.