wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Periodic Fibonacci
        
(Message started by: Icarus on Mar 22nd, 2006, 8:07pm)
Title: Periodic Fibonacci
Post by Icarus on Mar 22nd, 2006, 8:07pm
True or False:

Let {fn} be the Fibonacci series (f1 = f2 = 1, fn+1 = fn + fn-1). For any positive integer q, if k is the smallest index for which q | fk (q divides fk), then q | fn if and only if k | n.
Title: Re: Periodic Fibonacci
Post by Barukh on Mar 23rd, 2006, 5:51am
I think I tried to show this here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1140257977;start=0#19)?
Title: Re: Periodic Fibonacci
Post by Icarus on Mar 23rd, 2006, 2:47pm
Similar, but it does not appear to be the same thing to me.

I will say, however, that almost immediately after posting this, I realized that it is nearly trivial if approached from the right direction.
Title: Re: Periodic Fibonacci
Post by ecoist on Mar 24th, 2006, 11:52am
Since f0=0, it follows that k is the period of q.  Hence q | fn if and only if k | n.
Title: Re: Periodic Fibonacci
Post by Icarus on Mar 24th, 2006, 3:14pm
That is just restating the problem. It is not a proof of anything.
Title: Re: Periodic Fibonacci
Post by Icarus on Mar 24th, 2006, 4:05pm
Sorry. I now realize you were building off the result of the other thread. But it doesn't follow necessarily that k is the period of q. For example, consider the periodic sequence

0  1  2  0  3  4  0  1  2  0  3  4  0  ...


Besides which, you can prove this whole result much more easily than the proof in the other thread (which adds size requirements to k, but lacks the "only if" portion of this one).
Title: Re: Periodic Fibonacci
Post by ecoist on Mar 24th, 2006, 6:25pm
I spoke too soon.  Certainly, q can divide a term in the middle of the period of the sequence.  Sorry, Icarus.  q=5 illustrates this:

1 1 2 3 0 2 2 4 1 0 1 ... (mod 5)

The period is 10 yet still divisible by k=5.
Title: Re: Periodic Fibonacci
Post by ecoist on Mar 25th, 2006, 5:39am
True.  First a little lemma.

If q | f(m), then f(m+1)=f(m+2)=a (mod q), for some integer a; whence f(s+m)=af(s) (mod q), for all s[ge]0.

So, when m=s=k, q | f(2k).  When m=k and s=2k, q | f(3k), etc.

Conversely, let p be a divisor of q and a.  Then the lemma implies that p divides all f(t), for all t[ge]m modulo q.  Since f is periodic modulo q, it follows that p divides f(1)=1 modulo q; so p=1.  But then the shortest interval between terms divisible by q is k.  Now let q | f(n) and set n=ku+r, with 0[le]r<k.  Then q divides f(ku) and f(n), so r=0 and k | n.
Title: Re: Periodic Fibonacci
Post by Icarus on Mar 25th, 2006, 8:29am
That is in essense the proof I found, and if you are familiar with the properties of the cyclic groups Zq, it is almost trivial when stated in those terms. The essential artifact is that adjacent elements of the Fibonacci sequence are always relatively prime (anything that divides both fn+1 and fn must also divide fn-1 = fn+1 - fn, and by induction, must also divide f1 = 1).

In fact, we can generalize to result to many other recursive sequences. Say that the sequence Fn has the "index-divisor property for q" if q | Fn if and only if k | n, where k is the smallest index > 0 for which q | Fk.

Lemma: If P(x, y) is a polynomial and Fn is an integer sequence satisfying the recursion relation Fn+1 = P(Fn, Fn-1), and if Fn has the property that any two adjacent elements are relatively prime, then Fn has the index-divisor property for all divisors q of F0.

Proof: Consider the sequence Gn = Fn mod q in Zq. G0 = Gk = 0, and G1 and Gk+1 must both be generators of Zq, since F1 and Fk+1 are both relatively prime to q. Therefore there is an automorphism h of Zq which carries G1 to Gk+1, and also h(G0) = 0 = h(Gk). Now if h carries Gn and Gn+1 to Gn+k and Gn+k+1 respectively, then
h(Gn+2) = h(P(Gn+1, Gn)) = P(h(Gn+1), h(Gn)) = P(Gn+k+1, Gn+k) = Gn+k+2.
So by induction, h(Gn) = h(Gn+k) for all n >= 0. Since h(x) = 0 if and only if x = 0, and since k is the smallest index for which Gk = 0, the conclusion follows.

Corrolary: If P(x, y) is a polynomial with integer coefficients, and if Fn is a sequence with F0 = 0, GCD({Fn}) = 1, and which  satisfies the recursion Fn+1 = P(Fn, Fn-1)Fn + Fn-1, then Fn has the index-divisor property for all integers q.

Proof: Since Fn-1 = Fn+1 - P(Fn, Fn-1)Fn, any common divisor p of Fn+1 and Fn also divides Fn-1, and by the forward recursion formula, it must also divide Fn+2. By induction, p must divide Fm for all m, and hence must be 1. Thus all adjacent elements of Fn are relatively prime, and since every integer other than zero divides F0 = 0, the corrolary follows. (q=0 works because there is no index k for which q | Fk.)

_________________________________________________

I find this an extraordinary property, that divisors enter the Fibonacci sequence in such a regular fashion, and I think it goes a long way towards explaining the pattern in Jock's new avatar.
Title: Re: Periodic Fibonacci
Post by Eigenray on Mar 25th, 2006, 6:27pm
If F is the matrix
[ 0  1 ]
[ 1  1 ],
then Fn =
[ fn-1  fn ]
[ fn  fn+1 ].
This gives a rather concise proof: q|fn iff Fn is a scalar matrix mod q, so k is simply the order of F in the group PGL2(Zq).  (That is, the quotient of GL2(Zq), the group of invertible 2x2 matrices over the ring Zq, by the (central) subgroup of scalar matrices.)


on 03/25/06 at 08:29:57, Icarus wrote:
G0 = Gk = 0, and G1 and Gk+1 must both be generators of Zq, since F1 and Fk+1 are both relatively prime to q. Therefore there is an automorphism h of Zq which carries G1 to Gk+1, and also h(G0) = 0 = h(Gk). Now if h carries Gn and Gn+1 to Gn+k and Gn+k+1 respectively, then
h(Gn+2) = h(P(Gn+1, Gn)) = P(h(Gn+1), h(Gn)) = P(Gn+k+1, Gn+k) = Gn+k+2.

To commute with polynomials you need h to be a ring automorphism, and Zq just doesn't have that many.
Title: Re: Periodic Fibonacci
Post by Icarus on Mar 26th, 2006, 11:53am

on 03/25/06 at 18:27:17, Eigenray wrote:
To commute with polynomials you need h to be a ring automorphism, and Zq just doesn't have that many.


You're right. I should of thought about that a little more closely. The result still holds for all recursions of the form Fn+1 = AFn + Fn-1, but I was mistaken in believing it held for more general ones.
Title: Re: Periodic Fibonacci
Post by James Fingas on Jul 25th, 2006, 11:59am
Not entirely true. The original question doesn't hold for k=2. Seems to work after that, though.

My solution [ed] which now I see is the same as ecoist's [/ed]:
First of all, note that f0=0 is divisible by any number. Now look at the fibonacci sequence in modulo q arithmetic. The sequence starts off with 1 1 , follows with a sequence of numbers that are not equal to q, and then a zero. For instance (q = 17):

1 1 2 3 5 8 13 4 0

Now what happens after the zero? The next numbers are 4 and 4, so we therefore get the same sequence multiplied by a constant. For a prime number q, multiplying any two non-zero numbers smaller than q by a constant will not give you a multiple of q. Therefore, the second sequence will return to zero only at the point the first sequence returned to zero, which is to say it will have the same length, which proves the point.

For a composite q, we must show that the number immediately before the zero (call it m) does not share any factors with q, or the multiplication in the above step could lead to premature zeros. This is simple to show. Suppose gcf(m,q) = n, and note that zero is also divisible by n. Subsequent numbers in the sequence are formed by adding multiples of n, and possibly subtracting q (also a multiple of n). These operations will always produce multiples of n. However, a simple finiteness argument shows us that that the modulo fibonacci sequence repeats itself, so we know that the number 1 must show up again. Therefore the only possible n is 1.
Title: Re: Periodic Fibonacci
Post by Icarus on Jul 25th, 2006, 2:25pm

on 07/25/06 at 11:59:17, James Fingas wrote:
Not entirely true. The original question doesn't hold for k=2.


You get to pick q, not k. For q=1, k=1; and for q>1, k>2. k = 2 never comes up.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board