Characteristic value of Fibonacci Sequences

  1. [tex] C(a,b) = a^2 + ab -b^2[/tex]

    The characteristic value of a Fibonacci sequence is an interesting property.
    1) C(a,b) = C(a,a-b)
    2) C(a,b) * C(c,d) = C(ac+ad-bd,bc-ad)
    3) C(a,b) * C(a,a-b) = C(2a^2-2ab+b^2,2ab-b^2) =(C(a,b))^2

    [tex]C(a,b)^n = C(A_{n},-B_{n})[/tex]
    [tex]A_{n}=\sum_{i=0}^{n}F_{i-1}nCia^{i}b^{(n-i)}[/tex]
    [tex]B_{n}=\sum_{i=0}^{n}F_{i-2}nCia^{i}b^{(n-i)}[/tex]

    Opps the last two equations are sums as i goes from 0 to n
    [tex]F_i[/tex] ={-1,1,0,1,1,2,3...} with [tex]F_{0}= 0[/tex]
    nCi are the binominal coefficients
     
    Last edited by a moderator: Feb 24, 2009
  2. jcsd
  3. This one may or may not be proven by induction, base on my post earlier at 7 today it is proven for a=b but for "a" not equal to "b" there is more work to do.
     
  4. Forgive me for this question but what is the:
    Characteristic value of Fibonacci Sequences

    I wasn't a math major when I was in university.
     
  5. Good question since the only known posting on this before me was the posting of the sequence of characteristic values by another , Allan Wechsler http://www.research.att.com/~njas/sequences/A022344 that did not explain the sequence. Go to this link and see my added comments of February 2007. The absolute value of (a^2 +ab -b^2) where a,b are any sequential terms from the nth row of the Wythoff array A035513 which rows are each Fibonacci sequences. It is the absolute value of T(n,i-1)*T(n,i+1)-T(n,i)^2 that actually forms the terms a(n) of sequence A022344, but for some reason no one noted this until my comments. The sequence (which I "discovered" independently) has a formula the same as though the factors were arranged in determinant form which is probably why the sequence was called "Allan Wechsler's J-Determinant Sequence". I call this the "sequence of characteristic values" since it does not matter which adjacent terms from the nth row are used for the sequential terms a,b to compute the value a(n). Note, however, the order must be the order they appear in the nth row of Wythoff's array since C(a,b) is not the same as C(b,a) where a<>b.
     
    Last edited: Mar 1, 2009
  6. I improved upon the last equation so that the Fibonacci series can be other than the standard Fibonacci series.
    Let x and y be [tex]F_0[/tex] and [tex]F_1[/tex] respectively and [tex]F_{n}=F_{n-2}+F_{n-1}[/tex]

    Then

    [tex]C(a,b)^{n} = C(A_{n},B_{n})/C(x,y)[/tex]

    [tex]A_{n} = \sum_{i=0}^{n}F_{i}nCia^{n-i}b^{i}[/tex]

    [tex]B_{n} = \sum_{i=0}^{n}F_{i+1}nCia^{n-i}b^{i}[/tex]

    Now given that [tex]pCi = 0[/tex] mod p(prime) except for [tex]i=0[/tex] and [tex]i=p[/tex]; C(a,b)^(p)=C(a,b) mod p = C(xa +b* F_{p},ya + bF_{p+1}) /C(x,y) would seem to be a new property of Fibonacci series assuming that each of C(a,b), a and b <> 0 mod p.

    This property is the next candidate for proof. Eventually proof of the whole might be found.
     
    Last edited: Mar 1, 2009
  7. I have checked out this "new property" using the standard Fibonacci series but with "F_0" = [tex]F_{-(N+1)/2}[/tex] such that "F_n+1" = [tex]F_{(n+1)/2}[/tex] and set a=b=1. I figured that since the characteristic value of that series was 1 and since a = b = 1, and since [tex]F_{-n} = -1^{n+1}F_{n}[/tex] that the above property could be set forth more clearly. I was rewarded by the following result .

    My new hypothesis
    Let N Be odd and define the subscripts A,B,C,D to be the sequential integers from (N-3)/2 to
    (N+3)/2. Then the following equivalence holds if and only if N is Prime

    If N = -1 mod 4 then [tex]C(-F_{C},F_{B}) = C(-F_{A},F_{D}) \mod N[/tex]

    If N = 1 mod 4 then [tex]C(F_{C},-F_{B}) = C(F_{D},F_{A}) \mod N[/tex]

    I check this as far as my excel program would allow (up to prime = 53). This may or may not be useful but it is an improvement on Wilson's Theory. The only doubt I have is the "and only if" part but neither part stands proven.
     
  8. To: ramsey 2879

    Quoting ramsey 2879
    What a great hypothesis!

    This is truly one of the most interesting results that I have ever seen, and I'm an "old timer"!

    The "if and only if part" does indeed stand a very good chance of being correct
    and from a purely theoretical standpoint, it is clearly of immense importance!

    Please continue posting the results of your reasearch, investigations and other work on this
    incredible discovery!

    Don.
     
  9. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    This looks like the Lucas test, so I imagine the first failure will be at n = 705.
     
  10. After considering the actual values of the first few terms as computed from my expressions they are indeed the Lucus numbers and the test does appear to be an equivalent statement of the Lucus test. It is not the only test generated by the study of powers of the Characteristic function. The Lucus test is derived from letting a = 1 and b both = x and generating powers of C(1,1) by using each the formulas 1-3 as given in my first post in a particula manner. Basically, if you multiply (a,b)*(a,b) to get (A(2),B(2)) by operation 3 and continue doing so to get as per my first post you usually end up with A(n) and B(n) no longer being coprime even if a and b are coprime, but if you alternate the equivalent expressions by letting a= A(1),b=B(1) then doing the multiplication operation 3 of my first post with (a,a-b)*(A(1),B(1)) to get (A(2),B(2)) then use (a,b)*(A(2),B(2)) to get (A(3),B(3) , i.e. by alternating between (a,a-1) and (a,b) as the first ordered pair times the pair (A(n),B(n)) you get coprime A(n),B(n) whenever b is coprime to a. You can also let "a" = x+1 and "b" = x although this generates a triangular series of polynominals for similar to Pascal's triangle, the only similarity is that the generated terms for A(n) and B(n) in the relation C(A(n), B(n)) = C(A,B)^n are polynominals in the nth degree where the first and last term coefficients of A are both the Fibonacci number F(n) and the (first and last term coefficients of B sum to F(n) and also that the remaining terms are all divisible by n if n is prime. Since C(2,1) = 5, then 5*F(n)^2 = 5^n mod n if n is prime. This test (F(n)^2 = 1)is weaker than the Lucus test since there are more presudo primes but apparently holds for all primes other than 5 (this time I checked it out up to the 1,800 th prime). About half of the Lucus presudo primes are also presudo primes for this test, so you can't get a perfect test by a combination of these two tests. I tried other combinations for a and b, but the only apparent tests were variations of these two tests.

    I have been limiting my investigation so far by chosing various other expresions in the first degree for a and b, and determining A(n) and B(n) as polynominals of degree n by the multiplication operation, relation 3 of my first post using alternative first order expresions (a,b) and (a,a-b) as above and determining the relation between a and b such that the polynominals of degree n give all terms divisible by n if n is prime with the exception of one or both of the first and last terms.

    One way to speed the process is to determine the polynoninals for m = 2n by multiplying (A(n),B(n)) with (A(n),A(n)-B(n)) then multiplying these polynominals together using multiple operations 3. This is how I deduced the result given earlier in my thread with respect to the coefficients all being a combination of Fibonacci numbers and the Binominal coefficients.
     
  11. Sorry for the errors. I rushed through my post because I knew my wife was expecting me to take her to the doctor and I wasn't sure if I would have time later. When I get around to it I will post some more.
     
  12. To: Ramsey 2879,

    You took a different approach than did Lucas, and that, in and of itself,
    makes your discovery unique.

    Thanks,

    Don.
     
  13. There is more to show that my approach has some merit.
    I found another Prime Test much stronger than the Lucas Test

    Input an odd number N not divisible by 5 greater than 1
    A = 1
    B = 0
    P = 2
    Do
    C = A
    D = A-B
    A = C+D
    B = -D
    P = P + 2
    Loop Until P> N
    Now (A + (-1)^( N^2 = 1 mod 10)) = 0 Mod N if N is prime
    Also (B +(N^2 = -1 mod 10) = 0 Mod N if N is prime

    This two prong test yields only three presudo primes in the first thousand primes. The first presudo prime is 4181 but I haven't located the other two.

    I think that an advantage to this test is that it only involves addition and subtraction.

    The number of recursions could be shortened by multiplication as per method 3 of my first post in combination with the addition and subtraction

    I would be glad to answer any questions concerning this test.
     
  14. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    Your test takes n/2 steps, much worse than trial division.

    I don't understand the final step in the test; can you give an example, perhaps for n = 101? I get (a, b, c, d) = (1500520536206896083277, -927372692193078999176, 573147844013817084101, 927372692193078999176).
     
  15. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    I reverse engineered it -- he's using the [.] operator where

    [P] = 1 if P is true
    [P] = 0 if P is false

    except he's using parentheses for added confusion. :frown:
     
  16. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    I suppose since I calculated it, I should post it in case someone else wants to know: set

    [tex]u = (3 + \sqrt{5}) / 2[/tex]

    [tex]v = (3 - \sqrt{5}) / 2[/tex]

    This test computes

    [tex]A = \frac{(1-u) u^E - (1-v) v^E}{v - u}[/tex]

    [tex]B = \frac{u^E - v^E}{v - u}[/tex]

    where E = (N - 1) / 2
     
  17. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    Thanks for posting that. Now I can post the first few pseudoprimes. My list matches (but exceeds) ramsey2879's list.

    4181, 5777, 6479, 6721, 10877, 13201, 15251, 27071, 34561, 44099, 47519, 51841, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 75077, 78089, 90061, 96049, 97921, 100127, 109871, 113573, 118441, 139359, 146611, 157079, 161027, 162133, 163081, 168299, 186961, 196559, 197209, 219781, 231703, 233519, 252601, 254321, 257761, 268801, 272611, 283361, 300847, 302101, 303101, 327359, 330929, 399001, 417601, 430127, 433621, 438751, 451979, 486359, 489601, 510719, 512461, 520801, 530611, 544159, 545279, 553679, 553839, 556421, 575599, 618639, 620279, 635627, 636641, 638189, 641199, 655201, 670879, 689359, 701569, 722261, 737471, 741751, 809999, 850541, 851927, 852841, 853469, 881011, 925681, 954239, 993509, 999941
     
  18. The only confusing part I see in the final step as I set forth are the parenthetical true/false expressions.

    If N = 3 or 7 mod 10 then (the expressions = 0,1) (-1)^0 = 1 so we have A+1 and B+1
    If N = 1 or 9 mod 10 then (the expressions = 1,0) ..........=-1 so we have A-1 and B+0

    Interesting reverse engineering, but I actually based this on alternative type 2 multiplication by a = 1+x and b = 1+x or 0 alternatively, but I did only the constant x^(0) part.
     
    Last edited: Mar 31, 2009
  19. Sorry for the confusion, I did not know the convention to put this operator in brackets.
     
  20. Thankyou for posting that. Interesting that such a straight forward recursion should match such a mathematical expression. Interesting that the number 3 pops in when I only used 1's and zeros as my multiplication operators. I will check my list for the presudo primes mention in the next post.
     
  21. I do not get 6479 or 27071 as pseudoprimes. My list does not go any further than 27071. Are you sure they pass Hurkyl's tests with these numbers? If so that is not my test.
     
    Last edited: Mar 31, 2009
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Characteristic value of Fibonacci Sequences
Loading...