Partitioning numbers

October 22, 2008

A student asked me the other day the following rather homework-looking question: Given a natural number n, how many solutions (x,y) does the equation


have for x and y natural numbers?

The question has a very easy answer: Simply notice that 0\le 2y\le n and that any y like this determines a unique x such that (x,y) is a solution. So, there are \frac n2 +1 solutions if n is even (as y can be any of 0,1,\dots,n/2), and there are \frac{n+1}2 solutions if n is odd.

I didn’t tell the student what the answer is, but I asked what he had tried so far. Among what he showed me there was a piece of paper in which somebody else had scribbled


which caught my interest, and is the reason for this posting.

Read the rest of this entry »