You are Here: Home >< Maths

# Strange observation... trying to prove it watch

1. 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 for some , then eventually we reach a th term whereby . 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 then ; that was quite simple, because:

...so it follows that if such a exists, then all following terms are equal.

My problem now is proving that such a exists for all (mod 64). Bear in mind that , and we can reduce the problem by saying that , 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 .

If any of you could help, I would appreciate it.
2. Erm, I think this works, but supposing the first term, , is some number , then can you find a general term for and then by inspecting this, your answer should be clear, it is true for all and for all , unless I've made a horrible mistake....
what I tried...
We should find that

And choosing , we find that .
3. well...i'll leave you to it
4. (Original post by GHOSH-5)
Erm, I think this works, but supposing the first term, is some number , then can you find a general term for and then by inspecting this, your answer should be clear, it is true for all and for all , unless I've made a horrible mistake....
Let's see...

The general term seems to be . I realise that when the term disappears, since , leaving , which itself reduces to for ... and since , voilà!

Thanks a lot
5. (Original post by nuodai)
Thanks a lot
No worries

From where did the question come?

Side note: For an alternate LateX code for '(mod 64)' or whatever, just '\pmod{64}' sorts it out
6. (Original post by GHOSH-5)
No worries

From where did the question come?
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 I have yet more to investigate... I wonder if I can generalise any results for (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
7. (Original post by 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.
Sounds quite clever actually. I wondering exactly why you chose the three buttons to have those specific functions though...
I wonder if I can generalise any results for (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).
I think you'll be able to find some more results if you rather consider common factors between A and C, rather than just if one divides another, but that could be horribly wrong Interesting idea though definitely
8. Were am I? Why does my head hurt? Who's ravaged my orifices with mathematical equations during the summer?!
9. Damn trying to sleep.

(Original post by GHOSH-5)
Sounds quite clever actually. I wondering exactly why you chose the three buttons to have those specific functions though...
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 (i.e. pressing the three buttons in succession) always led to the cycle 42-52-53, so I tried it with just and got 44-54, and with I got 40-50-51-52 and so on.

(Original post by GHOSH-5)
I think you'll be able to find some more results if you rather consider common factors between A and C, rather than just if one divides another, but that could be horribly wrong Interesting idea though definitely
I think you might be right... further investigation pending.
10. (Original post by nuodai)
The idea was to have something that could convert decimal numbers to binary.
That makes sense.
11. Right, back to work!

If , and we let , then . So, if we have such that , then:

Comparing coefficients tells us that and , meaning that and so on. As a sidenote, it must follow that , so if we take , it means that , which is thus a necessary condition for this to occur.

So, if , we end up with , which is independent of , meaning that the starting value does not matter (except for deciding the value of , which will be lower if than if ).

If , we reach a contradiction when we get to the point where , so if this is the case there does not exist such that . However a case may arise where a sum of subsequent powers of will be zero. For example:

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

... so after the th term, we get a cycle of period

Furthermore, it seems that for all then there exist integers such that (assuming this isn't wrong, how can I prove this?!), meaning that all recurrence relations of the form 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.
12. It's trivial that leads to a cycle: there are only C possible values for x_n, and so by the pigeonhole principle, after at most C+1 steps, you end up with with . It's obvious (and easy to prove) that this implies the sequence repeats.
13. (Original post by DFranklin)
It's trivial that leads to a cycle: there are only C possible values for x_n, and so by the pigeonhole principle, after at most C+1 steps, you end up with with . It's obvious (and easy to prove) that this implies the sequence repeats.
Yes, it seems a lot more obvious now Thanks.

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: July 20, 2009
Today on TSR

### Edexcel C4 Maths Unofficial Markscheme

Find out how you've done here

### 2,798

students online now

Exam discussions

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams