Let Transform S'=P(S) simultaneously replace every 1 in S with a 100, and every 0 in S to a 10. Now, take S₀ =1 , and set S_n+1 =P(S_n )

Now let

c_n =(the number of ones in S_n )/(the number of digits in S_n )

How can we find what lim(n-> infinity )c_n is equal to. It seems to converge to sqrt(2)-1 (try finding c_n for S_n up to n=8), but I'm not sure how to prove this.

Thanks,

Brad

Hi Brad,

Let a_n = no. of 1s in S_n
and b_n = no. of digits in S_n .

Notice that each digit in S_n will generate exactly one 1 for S_n+1 (because there is exactly one 1 in both 10 and 100). Hence a_n+1 = b_n . [1]

However what will happen to b_n+1 , the no. of digits? Well each 1 is replaced by 100, so the length of the chain increases by two, due to each 1 in S_n (as 100 is three-digit). Each 0 produces 10, so each 0 will increase the chain by one digit. So:

b_n+1 = b_n + 2(a_n ) + (b_n -a_n )

because there are b_n - a_n 1s. So:

b_n+1 = a_n + 2b_n . [2]

Combining [1] and [2] and shuffling about with n gives:

a_n = 2a_n-1 + a_n-2 [3]
b_n = 2b_n-1 + b_n-2 [4]

Now let's first find the limit of b_n /b_n-1 with n going to infinity (call the limit y). First of all can you see why it has to tend to a limit at all (I'll explain this further if you like - it is probably the hardest part). Then write [4] as:

b_n /b_n-1 = 2 + b_n-2 /b_n-1

Now if b_n /b_n-1 is converging to y, it will be pretty close to b_n-1 /b_n-2 . With n tending to infinity in fact, these two values will both converge to y. So they we'd have:

y = 2 + 1/y

as b_n-2 /b_n-1 = 1/[b_n-1 /b_n-2 ] = 1/y

y² - 2y - 1 = 0
(y-1)² = 2
y = sqrt(2) + 1 (because y> 0).

Next rewrite [2] as:

b_n+1 /b_n = a_n /b_n + 2

a_n /b_n is the value you want. The left hand bit we've already done and it's y = sqrt(2)+1. So for n going off to infinity:

a_n /b_n = sqrt(2) + 1 - 2 = sqrt(2) - 1

like you said.

Michael

Good proof. I had originally wondered whether that result would be true, as it ends up being an irrational density of ones. But, I quess that's why it's a quasiperiodic series rather than a periodic one.

Thanks,

Brad

Now that's a very interesting point you made, about it being an irrational density. But it really is! And the reason that this is OK is that although S_n will have a rational density (for finite n) the limit as n tends to infinity does not have to be rational. This is because in general a rational sequence (i.e. a sequence whose nth term is rational) does not have to tend to an irrational limit.

Example:

3
3.1
3.14
3.141
3.1415
3.14159
...

A rational sequence tending to the irrational pi . In fact of course nearly all rational sequences tend to an irrational limit.

I'm not sure what you mean by quasi-periodic though?

Michael

By quasi-periodic, I mean that there are finite segments within S_infinity that each occur an infinite number of times at different places in the sequence. Basically, I mean that the series has order to it, but not the sort of order that a periodic sequence, say 10101010..... has to it. If it were periodic like this, then it couldn't have irrational density.

Brad