THE COOL MATHS PART

Proof of the length of term N (Skip this if you can’t be bothered)

So, say we took, for example, the 15th iteration of the process, knowing the output will be a list of R’s and L’s. We could ask, how long is this list? Is there a rule for calculating how long the list will be?

Let’s find out!

It’s pretty apparent from the process that to go from the length of one term to the next, you double the length and add 1. so the length of term N, Nlen, is twice the length of the previous term plus one. Or, more formally,

Nlen = 2(N-1)len+1

We can see this in the length of the first few terms:

R – 1

RRL – 3 – 2(1)+1

RRLRRLL – 7 – 2(3)+1

There’s one problem with this process. To find the length of the 15th term, we would have to find the length of the first term, then double that and add one, double and add one, and so on until we reach term 15. This isn’t particularly practical, especially if we want the length of, say, the squillionth term (All the technical language here today.)

So, is there a better way of finding the length? As it turns out, yes. What happens when you take the lengths of the first few terms (1,3,7) and add 1. You get (2,4,8). These are the first few powers of two – does this mean that the length of term N is the Nth power of two, take away one? Is this a coincidence, or a pattern? As it turns out, it’s a pattern, and there is a neat way to prove this. This is an example of proof by induction (albeit one lacking much rigor.)

We want to prove that Nlen is 2N-1, right? The first thing we do is confirm it for at least one case. Take, for example, N=1. then:
21-1 = 1, and Nlen=1
So we know the formula is correct for at least this one case.

The next step is the crucial one – show that, if this formula is true for N, it is also true for N+1. How do we do this? Well, let’s say that Nlen does equal 2N-1. (I know that this is the statement we want to prove, but stick with me for a bit.) What happens when we go to the next term? Well, going from Nlen to (N+1)len, we double the length and add 1. taking Nlen to be 2N-1, we get:

(N+1)len=2(2N-1)+1 = 2*2N-2+1 = 2*2N-1 = 2N+1-1

Which is the same as substituting (N+1) for N in 2N-1. This means that, if we can prove this equation:

Nlen = 2N-1

for ANY value of N, then we prove it for ALL of them, since if it works for N it works for N+1, and (N+1)+1, and so on. But we’ve already proved it for the case N=1, which means N=2, N=3, and so on, all work. (This is called a proof by induction.)

This is where things get interesting

Recursive Algorithms

The formula that I described for the dragon curve is of a type known as recursive – this means that, to find the Nth iteration of the dragon curve, you need to find the 1st dragon curve, then use that to get the second, then third and so on until you get to N. This means that you have to find all the smaller dragon curves to find the curve you want. I wanted to see if I could make a formula that didn’t require this, and would let you generate the Nth dragon curve straight away.

Interesting? Finally!

On the quest to find this formula (I didn’t find one), I found a really cool property of the curve.

For those of you who couldn’t be bothered with the proof above, all you need to know is this:

Nlen = 2N-1

Where Nlen is the length of the Nth dragon curve (that list of R’s and L’s.) This just tells you that the length of the Nth dragon curve is 1 less than 2 to the power of N.

So, how would you go about finding a general formula?

Firstly, we’ll say the Dragon curve starts with a right turn, R, as we’ve been doing the whole time anyway. This means we always know the first letter of the sequence. Can you guess what it is?

That’s right, it’s an R! Good job, you’re on a roll. Let’s see if we can keep that momentum going. The next trick involves going back and taking a sneaky peek at the rules we use to generate this sequence, specifically this bit:

  1. RRL
  2. Flip it – LRR
  3. Change all “L”‘s to “R”‘s, and visa versa – RLL
  4. Append this to the original (RRL), and leave a gap between them – RRL_RLL
  5. Put an “R” in the gap – RRLRRLL

This bit is important. essentially, at the end of each step, we take our sequence of length 2N-1, and append an “R” to it (making the length 2N), before adding the reversed bit afterwards. This means that every 2Nth letter of the sequence is an “R”. If we take a fairly large term, say the 6th term, we can see this:

RRLRRLLRRRLLRLLRRRLRRLLLRRLLRLLRRRLRRLLRRRLLRLLLRRLRRLLLRRLLRLL

Every power of 2 term is a Right turn. This means that we know N out of the 2N-1 terms. It’s better than nothing, right? Well, what happens when we take these letters out, and just leave the ones we don’t know?

       L   RLL   RRLLRLL   RRLRRLLLRRLLRLL   RRLRRLLRRRLLRLLLRRLRRLLLRRLLRLL

We get a new sequence of letters. Can we figure out a rule for these?

Well, first of all, we look at the length of each list of letters.

L – 1

RLL – 3

RRLLRLL – 7

RRLRRLLLRRLLRLL – 15

RRLRRLLRRRLLRLLLRRLRRLLLRRLLRLL – 31

That’s interesting. It seems that the number of letters matches up with the formula for the number of letters in an entire dragon curve, for N = 1,2,3,4, and 5. Is it possible that each of these lists is also a dragon curve?

As it turns out, they are dragon curves – but they are different to our starting dragon curve. First of all, they are backwards, they should look like this:

L

LLR

LLRLLRR

LLRLLRRLLLRRLRR

LLRLLRRLLLRRLRRLLLRLLRRRLLRRLRR

All I’ve done is flip them around, or if you like I’m reading from right to left. The second difference is that they start with an L, instead of an R. Other than that, they follow the rules of the dragon sequence:

1: L

2: L + L + R = LLR

3: LLR + L + LRR = LLRLLRR

4: LLRLLRR + L + LLRRLRR = LLRLLRRLLLRRLRR

5: LLRLLRRLLLRRLRR + L + LLRLLRRRLLRRLRR = LLRLLRRLLLRRLRRLLLRLLRRRLLRRLRR

What on earth does this mean then?

What this means is that a dragon curve of N iterations is made up of N-1 dragon curves, ranging in size from 1 to N-1, separated by a right turn (or a left turn, if the dragon curve starts with a left.) This can be seen if you change the colour of the dragon curve every time you get to one of the new subcurves, for example:

Dragon

Basically, the moral of the story is pretty pictures.

Advertisements