Hamse’s solution to the circle problem, and difference equations

1 2 4 8 16 31 57 99 163
1 2 4 8 15 26 42 64
1 2 4 7 11 16 22 29
1 2 3 4 5 6 7
1 1 1 1 1 1 1
0 0 0 0 0 0

Whatever about arithmetical slips, Hamse Adam’s solution to the prize question of 10 October was basically correct. Hamse, by an excellent effort of imagination and insight, has found out about a whole new branch of maths.

Click here to download this post as a printable pdf.

Click here for more on the calculus of finite differences, in very readable form from Martin Gardner

The question was about how many regions you get when you mark n points on the circumference of a circle and draw in all the lines connecting them. As Hamse saw, the answer is given by the top line in the table above: 1 region for 1 point, 2 regions for 2 points, and so on up to 163 regions for 9 points.

Hamse’s table lets us calculate the numbers of regions more easily than by counting up the first five numbers in lines of Pascal’s triangle.

The table looks a bit like Pascal’s triangle, but works differently. Each item in a lower line is calculated as the difference between the two items above it, the one above and to the right minus the one above and to the left. Or, each item in an upper line is calculated as the previous item plus the item just below and to the right. Each line shows the “differences” of the sequence in the line above. The usual terminology for this is, if an represents the items in the line above, and bn the items in the line below:

bn=Δan=an+1−an

It’s a matter of convention that this table is written as going “up”, whereas Pascal’s triangle is written as going “down”.

SOLVING DIFFERENCE EQUATIONS

If now we take an to represent the number of regions with n points, Hamse’s table is another way of saying that the equation determining an is: Δ4an=1

In other words, if we take differences once, twice, three times, four times, we end up with a line in which every number is 1.

And a bit more. Since the equation: Δ4an=1 tells only only about differences in the sequence an, it can’t tell us the actual values of an unless we also know something about starting values, in other words the “1”s written in on the left hand side of the table. In other words:

a1=1

Δa1=1

Δ2a1=1

Δ3a1=1

We solve these equations as follows:

For all n, Δan=an+1−an (by definition)

Therefore an+1=(1+Δ)an

A little checking shows that although Δ is not a number, we can calculate on the right hand side as if it were. So:

an+1=(1+Δ)na1

 =sum from r=0 to r=n of nCr.Δra1

 =sum from r=0 to r=4 of nCr.Δra1

(since we can see from the table above that Δ5a1, Δ6a1, Δ7a1, etc. all equal zero)

 =sum from r=0 to r=4 of nCr

(since Δ0a1 [i.e. just a1], Δa1, Δ2a1, Δ3a1, all =1)

 =sum of first five elements of n-th row of Pascal’s triangle.

USING THIS APPROACH TO PROVE WHAT NUMBERS OF REGIONS WE GET, RATHER THAN COUNTING REGIONS AND THEN SEEING THEY FIT THIS PATTERN

Can we deduce directly from the geometry that Δ4an=1 and prove our solution that way? See below for how.

CAKE NUMBERS, PIZZA-EDGE NUMBERS, PIZZA NUMBERS

The third row down in the table, Δ2an, 1, 2, 4, 7, 11, 16, 22… is also of interest. The (n+1)-th item in this row equals the number of regions the whole plane is divided into by drawing n lines. The second row down, Δan, 1, 2, 4, 8, 15, 26, 42… is the “cake numbers” – the (n+1)-th number in the list is the maximum number of regions into which a 3-dimensional cube can be partitioned by exactly n planes.

They are called cake numbers because they count the number of pieces into which a cube-shaped cake can be divided by n cuts of the knife.

On the same principle, the numbers of regions created inside a circle by drawing lines between n points on the circumference could be called pizza-edge numbers, because they count the number of slices into which cuts joining those points on the circumference divide the pizza.

And the numbers of regions created in the plane by drawing n lines could be called pizza numbers, because they count the number of slices into which a pizza can be divided by n straight-line cuts all of whose meeting-points are inside the pizza.

DIFFERENCE EQUATIONS AND DIFFERENTIAL EQUATIONS

Equations like the one Hamse discovered in his table: Δ4an=1 are called difference equations.

Differences, as calculated in Hamse’s table, are the equivalent in discrete mathematics (where we deal with quantities which grow by jumps, like the whole numbers) of what is called differentiation in continuous mathematics (where we deal with quantities which grow smoothly, moving through an infinitely fine scale of values, like real numbers). FP1 students will learn about differentiation later this term.

Difference equations are the equivalent in discrete mathematics of what in continuous mathematics are called differential equations. You begin to learn about differential equations in FP2. Mathematical physics is jam-packed full of differential equations.

RECURRENCE RELATIONS

There are other links to things you are studying. Every difference equation can be rephrased as a recurrence relation, a rule for calculating each items in a sequence from the items before it. You have really been studying recurrence relations ever since a teacher in primary school showed you the sequence

1 4 7 10 …

and asked you what the rule was for continuing the sequence. (Answer: add three to the previous number).

FP1 students have been studying recurrence relations in proofs by induction about sequences, and you will also study recurrence relations in C1.

If San means the successor of an, i.e. an+1, then Δan=(S−1)an Again, a bit of checking will show that although S isn’t a number, we can do calculations on the right hand side as if it were. So:

Δ4an=(S−1)4an

 =(S4−4S3+6S2−4S+1)an

So Δ4an=1 is equivalent to:

an+4−4an+3+6an+2−4an+1+an=1

(which gives us yet another way we could work out the number of regions).

SOLVING RECURRENCE RELATIONS, RATHER THAN PROVING DROPPED-FROM-THE-SKY FORMULAS BY INDUCTION

In FP1, we’ve done proof-by-induction problems where we’re given a recurrence relation like un+1=5un+4 and a value of u1, say u1=4, and we’re asked to prove a formula for the sequence like: un=5n−1

That’s all very well, but leaves in mystery how we ever guessed the formula we’re proving. Actually, we can often solve recurrence relations, as we can solve difference equations, and that gives us the formula for the sequence and proves it at the same time.

In the example above:

un=5un−1+4

 =5(5un−2+4)+4

 =5(5(5un−3+4)+4)+4

 =…

 =5n−1u1+4×[5n−2+5n−3+….+52+5+1]

Now [5n−2+5n−3+….+52+5+1]×[5−1]=5n−1−1

(this is actually the direct way of proving the divisibility statements which Edexcel asks us to prove by induction)

so:

un=5n−1u1+5n−1−1

 =5n−1×(u1+1)−1

 =5n−1 if u1=4.

THERE ARE A LOT MORE INTERESTING USES OF PROOF BY INDUCTION THAN EDEXCEL STUFF

So we see that, oddly, Edexcel asks us to study for proofs by induction claims which can be proved directly, without induction, more simply and more illuminatingly. There are plenty of other mathematical claims for which proof by induction is interesting, indispensable and illuminating, but Edexcel doesn’t want you to study those. It is like introducing a toddler to a knife and fork by asking her or him to use them to eat a banana, or something else better eaten just by hand.

HOW WE COULD HAVE SEEN STRAIGHT OFF THAT THE 2n−1 PATTERN COULDN’T BE RIGHT. POLYNOMIAL INCREASE AND EXPONENTIAL INCREASE. LINKS TO DECISION MATHS

Another interesting insight here is into how we could have seen straight off, without drawing a circle with six points and counting regions, that the rule for the number of regions couldn’t have been 2n−1.

Students who know about differentiation and integration (the reverse of differentiation) will know that if differentiating a function again and again, four times over, gives you a constant (e.g. 1), then the function is of the form f(x)=constant×x4+lower powers of x. In the same way, if Δ4an=1 (for all n), then an=constant×n4+lower powers of n.

We could have seen that directly. If there are n points, there are ½n(n−1) lines, i.e. of of the order of n2 lines. Therefore there are of the order of n4 meeting-points of lines. But (tilting the circle microscopically if necessary) every region has a lowest point which is either a meeting-point of lines, or a meeting-point of lines and the circumference of the circle. There are of the order of n2 meeting-points of lines and the circumference of the circle.

Therefore the number of regions is at most of the order of n4.

(In fact it is (n4/24)+lower powers of n, but all we need to know here is that it is at most of the order of n4.)

But 2n−1 increases much faster for large n than n4. For example, 21000−1 is a number with 301 digits, whereas 10004 is only a 13-digit number. Therefore 2n−1 can’t be the right rule, because for large values of n it would give far too big a number of regions.

This argument is connected with work we have done this term in Decision Maths D1. We have learned about problems like bin-packing, which are “intractable”, meaning that every known exact method involves checking out a number of possibilities which increases “exponentially” (something like 2n, or more) as the number of items to be packed increases. For those we have approximate methods like first-fit, which require only something like n, or n2, or n3, or n4, operations, and give not a perfect but a not-too-bad result.

We have also learned about algorithms like Dijkstra’s or Kruskal’s or Prim’s, which give an exact answer with only something like n, or n2, or… operations in problems where you might at first think we would have to check out an exponentially increasing number of possible paths (minimum spanning tree, shortest path).

We have seen that the “Chinese postman” algorithm is workable for a small number of pairs of odd vertices, but rapidly (exponentially) requires an unworkable number of calculations for large numbers of pairs of odd vertices.

The basic dividing line in decision maths between workable and unworkable algorithms is between those which require only something like n, or n2, or… operations, and those requiring us (or the computer) to check out an exponentially increasing number of possibilities as the number n of items becomes large.

HOW TO PROVE THE Δ4an=1 APPROACH

From the argument above, the formula for PE(n), the number of regions in the pizza-edge problem from joining n points on the circumference, is a polynomial with the highest power of n being n4. But for any number A:

Δ(An)=A

Δ2(An)=0

Δ2(An2)=a constant

Δ3(An)=0

Δ3(An2)=0

Δ3(An3)=a constant

Δ4(An)=0

Δ4(An2)=0

Δ4(An3)=0

Δ4(An4)=a constant

[these facts are the differences version of the calculus facts that: (d4/dx4)(Ax4)=constant, etc.]

Therefore for all n, Δ4PE(n)=a constant=Δ4PE(1)

To solve this difference equation, we need only know what Δ4PE(1), Δ3PE(1), Δ2PE(1), ΔPE(1), and PE(1) are. (See the bit above about “Solving Difference Equations”).

By counting the number of regions for n=1, 2, 3, 4, 5 we find that all those numbers are 1.

Therefore (as in “Solving Difference Equations” above)

PE(n)=sum from r=0 to r=4 of nCr ▇

There are some good and interesting things about this proof.

1. Finding an apparently very vague approximation to PE(n) – just that it is some sort of polynomial in n with highest degree 4 – becomes a decisive step in finding PE(n) exactly.

2. We find the pattern, which is different from PE(n)=2n−1, not by counting regions for n≥6 when PE(n)≠2n−1… but by counting regions only for the values of n for which PE(n) does equal 2n−1.

3. We can use the exact same method to find the cake numbers C(n), and the pizza numbers P(n). This is particularly valuable for C(n), where a direct proof requires a lot of three-dimensional visual intuition.

The advantage of my previous proof, which went by finding a general rule for directly counting regions, is that it gives a better idea of why PE(n) should be what it is.

Proving something twice, by two different methods, seems at first sight a waste of time. But sometimes not. Two proofs can have different merits, and it can be worthwhile to know both of them.