Re: recurrent sequence


Chris wrote:
> Does anyone know the solution of the following problem?
>
> We define a sequence a(n) recursively as follows:
> a(1) and a(2) are arbitrary, and a(n) = abs (a(n-1) - a(n-2) (for n >=
> 3),
>
> where abs(x) is the absolute value of x.
>
> This sequence seems to be eventually periodic for arbitrary a(1) and a(2).
>
> If so,
>
> (1) how to prove it?;
>
> (2) what is the length of the periodic part (in terms of a(1) and a(2)).
>
> Thanks for any help or references.
>
> C. Wildhagen,
>
> Rottterdam, The Netherlands

It looks to me like the sequence will eventually be periodic with
period 3. Furthermore, eventually, the sequence will look like: 0, a,
a, 0, a, a, 0, a, a, ...

Here is my proof:
First, note that from the third term on, no matter what a(1) and a(2)
are, this will be a non-negative sequence.
If, at any point in the sequence you have a 0, then, if the last number
before the 0 was an a, then the sequence will be periodic from that
point, and will look like what I said it would.

Suppose, then, that there is never a 0 in the sequence. Define f(n) =
max{a(n), a(n+1)}. We claim that we can always find a subsequence
(b_n) such that f(b_n) is decreasing. Suppose there are two succesive
numbers a, b, in the sequence.

Case 1: a<b
Then the sequence will be, from that point, (a, b, b-a, a, ...).
Max{b-a, a} < Max{a,b}

Case 2: a=b

Then, (a, b, 0,...) and we are periodic

Case 3: a>b
Then, (a, b, a-b,...). Max{b, a-b}<Max{a,b}

So, f(n) is decreasing (unless there is a 0 term). So, either we get a
0 term, or f(n) eventually equals 0. If f(n) = 0, then we are still
guaranteed a 0 term.

.

Relevant Pages

  • Re: 1-in-4 sequencer freezes up--a noise problem?
    ... Thanks for the note, Chris. ... DIP is not one of the choices in AACircuit, so I assume I'll need to ... LED's on in a sequence over and over. ... Bruce in Fresno ...
    (sci.electronics.basics)
  • Re: OT: This wont ever happen again!
    ... Chris J. wrote: ... but I'm waiting for the really big sequence: ... hmm, do you think the sun will still be burning then? ...
    (alt.support.diabetes)
  • Re: string in a string
    ... Chris wrote: ... > | time similar functionality is needed for a different type of sequence ... I chose the worst of all possible examples. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Comments on my first script?
    ... ;) If I do accidentally drop a semi-colon at the end of the line, ... Also, Chris, can you explain this: ... first I'll create a sequence of integers ... "take every second element from the element with index 2 up to, but not including, the element with index 8" ...
    (comp.lang.python)
  • Re: Question about std::remove
    ... In article, Chris ... apply std::removeto the sequence, and I expect to ... In this particular test case, however, the iterator was ... Alwyn ...
    (alt.comp.lang.learn.c-cpp)