A lovely puzzle via @Sheena2907:

For those who need it:

Let $f$ be a function such that $f(1) = 1$ and $f(m+n) = f(m) + f(n) + mn$. Find $f(20)$.

As with many of my favourite puzzles, it’s a twofer: first, get the answer; then, dig deeper.

And as with pretty much all of the puzzles I discuss here, there are spoilers below the line.

There are loads of possible approaches to the first problem. Here’s mine:

  • $f(20) = f(10 + 10)$, or $2f(10) + 100$
  • $f(10) = f(5+5)$, or $2f(5) + 25$
  • $f(5) = f(1+4)$, or $1 + f(4) + 4$
  • $f(4) = f(2+2)$, or $2f(2) + 4$
  • $f(2) = f(1+1)$, or $2(1) + 1$.

Working back up the chain:

  • $f(2) = 3$
  • $f(4) = 10$
  • $f(5) = 15$
  • $f(10) = 55$
  • $f(20) = 210$.

Now. If you were my seven-year-old, you would look at those numbers and say “hey! wait a minute! Those are step-squad numbers!” Numberblocks vocabulary sticks, it turns out; that’s what they call triangular numbers. Can we prove it? Of course we can.

At least, for the rationals.

I’m not going to go through the details for the natural numbers – the nugget is that $f(n) = f(n-1) + n$, and it’s not too tricky to induction-proof your way to $f(n) = \frac{n(n+1)}{2}$.

It’s also not too hard to show that $f(kn) = k f(x) + \frac{k(k-1)}{2} n^2$ in a similar way ((for any integer $k$)), which implies that the result holds for any rational number. (Again, you might want to check the details and see for yourself.)

But irrational numbers… it turns out we can’t say anything about irrational numbers! If we assume that $f$ is continuous, then absolutely: $f(x) = \frac{x(x+1)}{2}$ for all real $x$.

However, we’re not told it’s continuous. There’s nothing at all to stop me stating that $f\left(\sqrt{2}\right) = \pi$ and getting a different definition for $\bb{Q}\left(\sqrt{2}\right)$, for example. In fact, if the function isn’t assumed continuous, we would need to define $f(x)$ for infinitely many irrational constants to make it completely defined.

Ooft.

I enjoyed that – there was surprising depth to what looked like a simple question! What did you make of it? Did you come up with a different proof? I’d love to hear about it!