Remember that wee summing problem we introduced last week? The task was to prove that
, where .
How you prefer to tackle problems like this will depend on your mathematical “personality” and on the tools you have available. For example, you may well see “” and immediately suspect that there’s a proof by induction lurking… and it’s certainly possible to prove this result by induction. However, there’s also a quicker and sneakier way.
For brevity, let’s write . Then is a double sum:
The sneaky bit is to spot that we can rewrite this double sum in a different way, by collecting first all the 1s ( of them), then all the s ( of them), and so on up to the single . Thus
But we can rewrite this more compactly, and thus tidy it up:
We’re nearly there now! Rearranging, we have