28 February 2013

Counting sums of triangular and square numbers

A previous post went on at some length about a programming quiz question and its relation to a result in number theory. As part of that write-up, I noticed a counting interpretation of one of the identities involved. I optimistically wrote that it might become the subject of a future note, and, surprisingly, I have now written that note.

Theorem

The number of ways of writing an integer as the sum of a square number and twice a triangular number is the same as the number of ways of writing it as the sum of two triangular numbers.

You need to be a bit careful about what you mean, because, for instance, 31 = 52 + 2×3 and 31 = (-5)2 + 2×3 count as two ways, and 31 = 28 + 3 and 31 = 3 + 28 also count as two ways. But the idea is to show that for each r2 + 2Ti, there is a matching Tj + Tk.

Proof by picture

In pictures, we place two copies of the triangle next to the square, one above and one to the right. We then see that you can instead look at the resulting pattern as two new triangles.

Sometimes the new triangles fit against each other:

dots

And sometimes the two (same-sized) original triangles overlap, meaning that you have to count some dots twice, and then the two new triangles also overlap — in fact nest:

dots

Written down like this, it seems a trivial result, but nonetheless it's quite pleasing.

Full proof

An identity involving counting sums of square and triangular numbers [pdf].

Comments are closed.