Register to reply

Characteristic value of Fibonacci Sequences

by ramsey2879
Tags: characteristic, fibonacci, sequences
Share this thread:
ramsey2879
#1
Feb24-09, 08:50 AM
P: 894
[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
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
ramsey2879
#2
Feb28-09, 10:13 PM
P: 894
Quote Quote by ramsey2879 View Post
[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
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.
John Creighto
#3
Mar1-09, 01:46 AM
P: 813
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.

ramsey2879
#4
Mar1-09, 09:09 AM
P: 894
Characteristic value of Fibonacci Sequences

Quote Quote by John Creighto View Post
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.
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.
ramsey2879
#5
Mar1-09, 02:23 PM
P: 894
Quote Quote by ramsey2879 View Post
[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
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.
ramsey2879
#6
Mar2-09, 12:07 AM
P: 894
Quote Quote by ramsey2879 View Post
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.
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.
Don Blazys
#7
Mar21-09, 10:29 PM
P: 26
To: ramsey 2879

Quoting ramsey 2879
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.
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.
CRGreathouse
#8
Mar22-09, 12:45 AM
Sci Advisor
HW Helper
P: 3,684
Quote Quote by ramsey2879 View Post
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.
This looks like the Lucas test, so I imagine the first failure will be at n = 705.
ramsey2879
#9
Mar24-09, 01:35 PM
P: 894
Quote Quote by CRGreathouse View Post
This looks like the Lucas test, so I imagine the first failure will be at n = 705.
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.
ramsey2879
#10
Mar24-09, 08:17 PM
P: 894
Quote Quote by ramsey[correction
2879;2130859]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[sic-a and b both = 1 per my post on March 2 at 9am)] 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[sic- operation 2] 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[sic, should be operation 2] 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)[sic -(a,a-b) 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 [sic operations 2] to produce the result given earlier in my thread with respect to the coefficients all being a combination of Fibonacci numbers and the Binominal coefficients.
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.
Don Blazys
#11
Mar26-09, 12:38 AM
P: 26
To: Ramsey 2879,

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

Thanks,

Don.
ramsey2879
#12
Mar31-09, 12:40 AM
P: 894
Quote Quote by Don Blazys View Post
To: Ramsey 2879,

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

Thanks,

Don.
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.
CRGreathouse
#13
Mar31-09, 01:02 AM
Sci Advisor
HW Helper
P: 3,684
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).
Hurkyl
#14
Mar31-09, 01:36 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
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.
Hurkyl
#15
Mar31-09, 01:40 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,099
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
CRGreathouse
#16
Mar31-09, 03:16 AM
Sci Advisor
HW Helper
P: 3,684
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
ramsey2879
#17
Mar31-09, 06:18 AM
P: 894
Quote Quote by CRGreathouse View Post
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).
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.
ramsey2879
#18
Mar31-09, 06:35 AM
P: 894
Quote Quote by Hurkyl View Post
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.
Sorry for the confusion, I did not know the convention to put this operator in brackets.


Register to reply

Related Discussions
Sequences limits and cauchy sequences Calculus & Beyond Homework 3
Cauchy sequences and sequences in general Calculus 7
Fibonacci sequence General Math 4
Induction and Fibonacci Precalculus Mathematics Homework 1
Fibonacci Sequences General Math 2