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 a_{n} represents the items in the line above, and b_{n} the items in the line below:

b_{n}=Δa_{n}=a_{n+1}−a_{n}

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 a_{n} to represent the number of regions with n points, Hamse’s table is another way of saying that the equation determining a_{n} is: Δ^{4}a_{n}=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: Δ^{4}a_{n}=1 tells only only about *differences* in the sequence a_{n}, it can’t tell us the actual values of a_{n} 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:

a_{1}=1

Δa_{1}=1

Δ^{2}a_{1}=1

Δ^{3}a_{1}=1

We solve these equations as follows:

For all n, Δa_{n}=a_{n+1}−a_{n} (by definition)

Therefore a_{n+1}=(1+Δ)a_{n}

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

a_{n+1}=(1+Δ)^{n}a_{1}

=sum from r=0 to r=n of nCr.Δ^{r}a_{1}

=sum from r=0 to r=4 of nCr.Δ^{r}a_{1}

(since we can see from the table above that Δ^{5}a_{1}, Δ^{6}a_{1}, Δ^{7}a_{1}, etc. all equal zero)

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

(since Δ^{0}a_{1} [i.e. just a_{1}], Δa_{1}, Δ^{2}a_{1}, Δ^{3}a_{1}, 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 Δ^{4}a_{n}=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, Δ^{2}a_{n}, 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, Δa_{n}, 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: Δ^{4}a_{n}=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 Sa_{n} means the successor of a_{n}, i.e. a_{n+1}, then Δa_{n}=(S−1)a_{n} 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:

Δ^{4}a_{n}=(S−1)^{4}a_{n}

=(S^{4}−4S^{3}+6S^{2}−4S+1)a_{n}

So Δ^{4}a_{n}=1 is equivalent to:

a_{n+4}−4a_{n+3}+6a_{n+2}−4a_{n+1}+a_{n}=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 u_{n+1}=5u_{n}+4 and a value of u_{1}, say u_{1}=4, and we’re asked to prove a formula for the sequence like: u_{n}=5^{n}−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:

u_{n}=5u_{n−1}+4

=5(5u_{n−2}+4)+4

=5(5(5u_{n−3}+4)+4)+4

=…

=5^{n−1}u_{1}+4×[5^{n−2}+5^{n−3}+….+5^{2}+5+1]

Now [5^{n−2}+5^{n−3}+….+5^{2}+5+1]×[5−1]=5^{n−1}−1

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

so:

u_{n}=5^{n−1}u_{1}+5^{n−1}−1

=5^{n−1}×(u_{1}+1)−1

=5^{n}−1 if u_{1}=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 2 ^{n−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 2^{n−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×x^{4}+lower powers of x. In the same way, if Δ^{4}a_{n}=1 (for all n), then a_{n}=constant×n^{4}+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 n^{2} lines. Therefore there are of the order of n^{4} 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 n^{2} meeting-points of lines and the circumference of the circle.

Therefore the number of regions is at most of the order of n^{4}.

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

But 2^{n−1} increases *much* faster for large n than n^{4}. For example, 2^{1000−1} is a number with 301 digits, whereas 1000^{4} is only a 13-digit number. Therefore 2^{n−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 2^{n}, 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 n^{2}, or n^{3}, or n^{4}, 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 n^{2}, 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 n^{2}, 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 Δ ^{4}a_{n}=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 n^{4}. But for any number A:

Δ(An)=A

Δ^{2}(An)=0

Δ^{2}(An^{2})=a constant

Δ^{3}(An)=0

Δ^{3}(An^{2})=0

Δ^{3}(An^{3})=a constant

Δ^{4}(An)=0

Δ^{4}(An^{2})=0

Δ^{4}(An^{3})=0

Δ^{4}(An^{4})=a constant

[these facts are the differences version of the calculus facts that: (d^{4}/dx^{4})(Ax^{4})=constant, etc.]

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

To solve this difference equation, we need only know what Δ^{4}PE(1), Δ^{3}PE(1), Δ^{2}PE(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)=2^{n−1}, not by counting regions for n≥6 when PE(n)≠2^{n−1}… but by counting regions only for the values of n for which PE(n) does equal 2^{n−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.