Strange observation... trying to prove it

Long story short, as a result of having too much free time I seem to have found that if a recurrence relation is defined by

Unparseable latex formula:

x_{n+1} = 2x_n + k\ (\mbox{mod 64})

for some

0 \le k < 64

, then eventually we reach a

p

th term whereby

x_p = x_{p+1} = \cdots = 64 - k

. I found this when playing around with my PIC programmer with 6 LED outputs and repeatedly pressing sequences of buttons which either double, add 10 to or add 1 to a number.

Now, I've proven that if

x_p = 64 - k

then

x_{p+1} = 64 - k

; that was quite simple, because:

Unparseable latex formula:

\newline x_{p+1} = 2x_p + k\ (\mbox{mod 64}) = 128 - k\ (\mbox{mod 64}) = 64 - k

...so it follows that if such a

p

exists, then all following terms are equal.

My problem now is proving that such a

p

exists for all

x

(mod 64). Bear in mind that

x, p \in \mathbb{Z}

, and we can reduce the problem by saying that

0 \le x < 64

, since it's all mod 64... my problem is that I've never encountered a method of proof which allows me to show that something exists for all

x

.

If any of you could help, I would appreciate it.

Reply 1

w04andia

well...i'll leave you to it :smile:

Reply 2

nuodai

Let's see...

The general term seems to be

\displaystyle 2^n x + k \sum_{r=0}^{n-1} 2^r

. I realise that when

n \ge 6

the

2^n x

term disappears, since

Unparseable latex formula:

64x = 0 (\mbox{mod 64})

, leaving

\displaystyle k \sum_{r=0}^{n-1} 2^r

, which itself reduces to

63k

for

n \ge 7

... and since

Unparseable latex formula:

63k (\mbox{mod 64}) = 64k - k (\mbox{mod 64}) = 64 - k (\mbox{mod 64})

, voilà!

Thanks a lot :smile:

Reply 3

nuodai

From programming a PIC microcontroller, bunging it on a circuit board with a few input buttons and 6 output LEDs*, pushing 3 buttons** in succession repeatedly, watching patterns of lights come up and investigating their properties. As you can see, I'm very cool :yes:

I have yet more to investigate... I wonder if I can generalise any results for

x_{n+1} = Ax_n + B \pmod C

(and I'm guessing that this will have something to do with whether A divides C or not; either way, I'm going to bed now).

*The LEDs represent integers modulo 64
**One button doubles the number, another adds 10, another adds 1

Reply 4

nasri-diaby

Were am I? Why does my head hurt? Who's ravaged my orifices with mathematical equations during the summer?!

Reply 5

nuodai

Damn trying to sleep.

There are actually 4 buttons, but only 3 are relevant here. The idea was to have something that could convert decimal numbers to binary. Obviously there was a limit since there are only 6 LEDs, so there was no need for a hundreds button, so I just had a tens and units button. I also had a button which counts up from 0 to 63 in binary, and the double button came just because I wanted to use the 4th button for something, and that seemed appropriate. Whilst messing around with it to see if it worked, I discovered that

2x + 10 + 1

(i.e. pressing the three buttons in succession) always led to the cycle 42-52-53, so I tried it with just

2x + 10

and got 44-54, and with

2x + 10 + 1 + 1

I got 40-50-51-52 and so on.

I think you might be right... further investigation pending.

Reply 6

nuodai

Right, back to work!

If

x_{n+1} = Ax_n + B \pmod C

, and we let

x_0 = x

, then

\displaystyle x_n = A^n x + B\sum_{r=0}^{n-1} A^r \pmod C

. So, if we have

p

such that

x_p = x_{p+1}

, then:

\newline \displaystyle A^p x + B\sum_{r=0}^{p-1} A^r = A^{p+1} x + B\sum_{r=0}^{p} A^r \pmod C

Comparing coefficients tells us that

A^p = A^{p+1} \pmod C

and

\displaystyle A^p = 0 \pmod C

, meaning that

A^{p+1} = 0 \pmod C

and so on. As a sidenote, it must follow that

A^p = kC

, so if we take

A, C \in \mathbb{Z}

, it means that

\dfrac{A^p}{k} = C \Rightarrow A\cdot \dfrac{A^{p-1}}{k} = C \Rightarrow A|C

, which is thus a necessary condition for this to occur.

So, if

A|C

, we end up with

\displaystyle x_p = B\sum_{r=0}^{p-1} A^r \pmod C

, which is independent of

x

, meaning that the starting value does not matter (except for deciding the value of

p

, which will be lower if

x|C

than if

x \nmid \!\ C

).

If

A \nmid \!\ C

, we reach a contradiction when we get to the point where

A^p = 0 \pmod C

, so if this is the case there does not exist

p

such that

x_p = x_{p+1}

. However a case may arise where a sum of subsequent powers of

A

will be zero. For example:

\newline 3^0 + 3^1 + 3^2 = 3^1 + 3^2 + 3^3 = \cdots = 3^p + 3^{p+1} + 3^{p+2} = 0 \pmod {13}

In such cases, the sequence of terms will form a cycle. In general, if

\displaystyle \sum_{r=0}^{n-1} A^{p+r} = 0 \pmod C

, then:

\newline \displaystyle A^{p+n-1} = -\sum_{r=0}^{n-2} A^{p+r} \pmod C\ (*)\newline[br]A^{p-1} = -\sum_{r=0}^{n-2} A^{p+r} \pmod C\newline[br](*)\ \Rightarrow A^{p-1} = A^{p+n-1} \pmod C\newline[br]\Rightarrow \boxed{A^p = A^{p+n} \pmod C}

... so after the

p

th term, we get a cycle of period

n

Furthermore, it seems that for all

A,C \in \mathbb{Z}

then there exist integers

n,p

such that

\displaystyle \sum_{r=0}^{n-1} A^{p+r} = 0 \pmod C

(assuming this isn't wrong, how can I prove this?!), meaning that all recurrence relations of the form

x_{n+1} = Ax_n + B \pmod C

eventually lead to a cycle [and it would make little sense if they didn't lead to a cycle...]

I have a feeling that at least 50% of this is either wrong or uses flawed logic (I have probably assumed things I should prove, or abused modular arithmetic), so help me out if that's the case.