When in Cuba, and leaving behind iPad and all, I was idling around how many Domino stones there are in a game of Dominoes that goes from 0 to 9.
Basically, we have all combinations of numbers 0-9 plus a doubled stone for each number, i.e.
With my son we arrived at the number by thinking:
- For number 0, 0 can be combined with all other numbers: 10 dominoes
- For number 1, it can be combined with all others, however, 1 combination (0,1) is already present: 9 dominoes
- For each subsequent number, you add the missing combinations - it is always 1 less than the previous one.
Mathematically, you can express this as
Now, if you arrange the numbers in pairs, where you take the left and right boundary of the remaining sequence of numbers you end up with
If you generalize this pattern you get that the sum of the pair is always one more than the biggest number, and you can form pairs up to the half of the biggest number:
Intuitively, this seems to work out for any sequence starting with 1 up to some arbitrary number n.
At this point I attempted a proof by induction (and I’m pretty sure I got the details wrong, but I was happy at the end), which I hadn’t done for several decades at this point.
Let’s establish the baseline, and settle that the equation works for n = 1:
That is correct.
Now, for the next step we get that
by the very definition of a sum. Substituting our equation on both sides, we get
Let’s multiply both sides by 2:
The point being that this holds true for any x, we can expand the solution for the previous step into the solution for the next step, coming all the way down to our baseline. Looking chill from this side of the screen!
See, there is no boredom with a pen and a piece of paper :)