Mathematrec

Here’s a rather well known mathematical gotcha. What’s the next number in this series: 1, 2, 4, 8, 16… ? Answer, of course, 31.

Draw a circle, mark some points on the circumference, connect every such point to every other, and count the number of regions the circle’s been divided into. With one point there are no lines and the circle consists of 1 region:

With two points there is one line and 2 regions:

Three, four, five points give you 4, 8, 16 regions:

You might confidently predict six points will give you 32 regions. But no.

Just by symmetry (you don’t have to place the points symmetrically, but I did, and it helps with the counting) you can see the number of regions is odd, and 1 more than a multiple of 3. In fact it’s 31 — a classic case of Richard K. Guy's Strong Law of Small Numbers: “There aren't enough
small numbers to meet the many demands made of them”. In fact it's his Example 5.

By the way, starting with 6 points, you have to be careful where you place them. If a line between two points intersects two or more other lines at the same point in the circle’s interior, then you get fewer regions. What we’re counting is the maximum number of regions you can get.

If you think about it you realize that, if we add new points clockwise from all the old points, then when we add the \(n^{th}\) point and \(n-1\) lines to connect them to previous points, one line crosses no others, another crosses all but one of the \(n-2\) lines drawn from the previous point, another crosses all but two of those lines and all but one of the \(n-3\) lines drawn from the second previous point, and so on. Think about how many new regions that generates and you see the second point generates 1 new region, the third generates 2, the fourth generates 4, the fifth generates 8, and the sixth generates 15. Then the total number of regions is 1, 2, 4, 8, 16, 31…

(And after that, 57 and 99. Amusingly, for 10 points the number of regions is 256. I see no powers of two after that.)

In fact these numbers do follow a formula, but it's not an exponential (\(2^n\)). It's a quartic polynomial.

Suppose you have 3 results \(r_0\), \(r_1\), and \(r_2\), and you want a formula in terms of \(n\) that spits them out if you plug in \(n = 0, 1, 2\). Well, consider this fraction:
$$\frac{(n-1)(n-2)}{(0-1)(0-2)}$$
Pretty obviously this is 1 when \(n=0\) and 0 when \(n=1\) or \(n=2\). Similarly
$$\frac{(n-0)(n-2)}{(1-0)(1-2)}$$
is 1 when \(n=1\) and 0 when \(n=0\) or \(n=2\), and
$$\frac{(n-0)(n-1)}{(2-0)(2-1)}$$
is 1 when \(n=2\) and 0 when \(n=0\) or \(n=1\). But that means
$$r_0\frac{(n-1)(n-2)}{(0-1)(0-2)} + r_1\frac{(n-0)(n-2)}{(1-0)(1-2)} + r_2\frac{(n-0)(n-1)}{(2-0)(2-1)}$$
is \(r_0\) when \(n=0\), \(r_1\) when \(n=1\), and \(r_2\) when \(n=2\).

Using 1, 2, and 4 for the results we want, you can simplify the above formula down to this quadratic:
$$f_3(n) = \frac{1}{2}(n^2+n+2)$$
Plug in 0, 1, 2 and you get 1, 2, and 4.

By a similar means you can get formulas to generate any five numbers you want — say, 1, 2, 4, 8, and 16. The algebra gets tedious but when you simplify it down it's
$$f_5(n) = \frac{1}{24}(n^4-2n^3+11m^2+14m+24)$$
and it does indeed give you the first five powers of 2 when you plug in 0 through 4. And this turns out to be exactly the formula for the number of regions in the circle when divided as above: Plug in 5 and you get 31.

It seems amusing that the first value past the ones you built in is almost a power of 2, but falls short by 1. So close! But not!

But here's a strange thing.

If you plug 3 into \(\frac{1}{2}(n^2+n+2)\) you get 7 — also 1 less than the next power of 2. A curious coincidence!

Or is it? What's a formula that generates the single result, 1? Obviously the constant function \(f_1(n) = 1\). That generates 1 and then 1 — which is 1 less than \(2^1\).

And a formula that generates 1, 2? Easy: \(f_2(n) = n+1\). And when you plug in 2 you get 3 — 1 less than \(2^2\).

Can you work out the cubic polynomial that generates 1, 2, 4, 8? Here it is:
$$f_4(n) = \frac{1}{6}(n^3+0n^2+5n+6)$$
And if you plug in 4 you get 15 — 1 less than \(2^4\).

We have another sequence here — 1, 3, 7, 15, 31... What's the next number? If you make a quintic that generates 1, 2, 4, 8, 16, and 32, what does it generate next? 63? Or is this a meta-example of the Strong Law of Small Numbers? I.e., does the pattern break here?

It doesn't break. It doesn't break for the eighth term either, or the ninth, or anything through the 18th. (After that my Python script starts giving me results that are not \(2^n-1\), but there's floating point arithmetic involved and I'm pretty sure it's rounding errors.)

Well, that's pretty remarkable at first sight. Assuming the pattern never breaks, it means: If you draw an \(n^{th}\) order polynomial through the points (0, 1), (1, 2), (2, 4), ... (\(n-1\), \(2^{n-1}\)), then it will always pass through (\(n\), \(2^n-1\)).

But why? It's not at all obvious. I mean, look at the formula for the first 10 powers of 2:
$$\frac{1}{362880}(n^9-27n^8+366n^7-2646n^6+12873n^5-$$
$$31563n^4+79064n^3+34236n^2+270576n+362880)$$
Can you look at that and see why it should give you 1023 when you plug in \(n=10\)?

I haven't really worked out the proof of it, but I'm sure the key is to look at the differences between successive values of \(f_m(n)\). For \(f_2(n)\) the differences are 1, 1, 1, 1... — which is \(f_1(n)\). For \(f_3(n)\) the differences are 1, 2, 3, 4, 5... — which is \(f_2(n)\). For \(f_4(n)\) the differences are 1, 2, 4, 6, 11... — which is \(f_3(n)\). And so on: \(f_m(n+1)-f_m(n) = f_{m-1}(n)\). Then by induction it's clear the \(n^{th}\) value of \(f_n\) is \(2^n-1\).