[math-fun] Fibonacci polynomial puzzle
Define Fibonacci polynomials F_n(Y) for integer n , variable Y via F_0(Y) = 0 , F_1(Y) = F_{-1}(Y) = 1 , F_{n+2}(Y) - Y F_{n+1}(Y) - F_n(Y) = 0 . See https://en.wikipedia.org/wiki/Fibonacci_polynomials http://mathworld.wolfram.com/FibonacciPolynomial.html --- though compare alternative (marginally less tractable in practice) http://oeis.org/wiki/Fibonacci_polynomials . The polynomial sequence shares elementary properties with the Fibonacci number sequence F_n : in particular strong divisibility, established via essentially the same argument --- see (engagingly pedestrian) https://proofwiki.org/wiki/Divisibility_of_Fibonacci_Numbers [Whence this property may be inferred for other sequences --- 14 and counting --- in OEIS. Strong divisibility, that is, not engaging pedestrianism.] I hope to post a more comprehensive account in a few days, explaining the how these matters bear on eccentric gear trains; meanwhile the following modest though positive advance afforded me such satisfaction, that I am unable to resist a little waving it about. **Puzzle** Show that there is a constant t such that for all odd prime p , F_2p(Y) = s Y F_p(Y) F_p(Z) ; where s = (-1)^((p-1)/2) and Z^2 = -(Y^2 + t) . Evaluate t , and deduce that F_p(Y) is irreducible. For example when p = 7 , F_14(Y) = Y (Y^6+5*Y^4+6*Y^2+1) (Y^6+7*Y^4+14*Y^2+7) , irreducibly. Fred Lunnon ____________________________________________________________ n F_n(Y) 0 0 1 1 2 Y 3 Y^2 + 1 4 Y^3 + 2*Y 5 Y^4 + 3*Y^2 + 1 6 Y^5 + 4*Y^3 + 3*Y 7 Y^6 + 5*Y^4 + 6*Y^2 + 1 8 Y^7 + 6*Y^5 + 10*Y^3 + 4*Y 9 Y^8 + 7*Y^6 + 15*Y^4 + 10*Y^2 + 1 10 Y^9 + 8*Y^7 + 21*Y^5 + 20*Y^3 + 5*Y 11 Y^10 + 9*Y^8 + 28*Y^6 + 35*Y^4 + 15*Y^2 + 1 12 Y^11 + 10*Y^9 + 36*Y^7 + 56*Y^5 + 35*Y^3 + 6*Y 13 Y^12 + 11*Y^10 + 45*Y^8 + 84*Y^6 + 70*Y^4 + 21*Y^2 + 1 14 Y^13 + 12*Y^11 + 55*Y^9 + 120*Y^7 + 126*Y^5 + 56*Y^3 + 7*Y 15 Y^14 + 13*Y^12 + 66*Y^10 + 165*Y^8 + 210*Y^6 + 126*Y^4 + 28*Y^2 + 1 16 Y^15 + 14*Y^13 + 78*Y^11 + 220*Y^9 + 330*Y^7 + 252*Y^5 + 84*Y^3 + 8*Y ____________________________________________________________
An associated problem involving (notionally) only Fibonacci numbers: For variable m,n , assumed to take only coprime (or perhaps distinct prime) values, express the integer F_(m n) / (F_m F_n) as a polynomial in suitable F_k . [ Eg. for m,n = 5,7 , F_35/F_5 F_7 = 141961 .] A partial solution, independent of coprimality, is F_(mn) / F_n = SUM_{1 <= k <= m} F_(mn-kn+1) F_(n-1)^(k-1) ; extracting factor F_m as well threatens more of a challenge ... Fred Lunnon On 11/25/15, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Define Fibonacci polynomials F_n(Y) for integer n , variable Y via
F_0(Y) = 0 , F_1(Y) = F_{-1}(Y) = 1 ,
F_{n+2}(Y) - Y F_{n+1}(Y) - F_n(Y) = 0 .
See https://en.wikipedia.org/wiki/Fibonacci_polynomials http://mathworld.wolfram.com/FibonacciPolynomial.html --- though compare alternative (marginally less tractable in practice) http://oeis.org/wiki/Fibonacci_polynomials .
The polynomial sequence shares elementary properties with the Fibonacci number sequence F_n : in particular strong divisibility, established via essentially the same argument --- see (engagingly pedestrian) https://proofwiki.org/wiki/Divisibility_of_Fibonacci_Numbers
[Whence this property may be inferred for other sequences --- 14 and counting --- in OEIS. Strong divisibility, that is, not engaging pedestrianism.]
I hope to post a more comprehensive account in a few days, explaining the how these matters bear on eccentric gear trains; meanwhile the following modest though positive advance afforded me such satisfaction, that I am unable to resist a little waving it about.
**Puzzle** Show that there is a constant t such that for all odd prime p ,
F_2p(Y) = s Y F_p(Y) F_p(Z) ;
where s = (-1)^((p-1)/2) and Z^2 = -(Y^2 + t) .
Evaluate t , and deduce that F_p(Y) is irreducible.
For example when p = 7 ,
F_14(Y) = Y (Y^6+5*Y^4+6*Y^2+1) (Y^6+7*Y^4+14*Y^2+7) ,
irreducibly.
Fred Lunnon
____________________________________________________________
n F_n(Y) 0 0 1 1 2 Y 3 Y^2 + 1 4 Y^3 + 2*Y 5 Y^4 + 3*Y^2 + 1 6 Y^5 + 4*Y^3 + 3*Y 7 Y^6 + 5*Y^4 + 6*Y^2 + 1 8 Y^7 + 6*Y^5 + 10*Y^3 + 4*Y 9 Y^8 + 7*Y^6 + 15*Y^4 + 10*Y^2 + 1 10 Y^9 + 8*Y^7 + 21*Y^5 + 20*Y^3 + 5*Y 11 Y^10 + 9*Y^8 + 28*Y^6 + 35*Y^4 + 15*Y^2 + 1 12 Y^11 + 10*Y^9 + 36*Y^7 + 56*Y^5 + 35*Y^3 + 6*Y 13 Y^12 + 11*Y^10 + 45*Y^8 + 84*Y^6 + 70*Y^4 + 21*Y^2 + 1 14 Y^13 + 12*Y^11 + 55*Y^9 + 120*Y^7 + 126*Y^5 + 56*Y^3 + 7*Y 15 Y^14 + 13*Y^12 + 66*Y^10 + 165*Y^8 + 210*Y^6 + 126*Y^4 + 28*Y^2 + 1 16 Y^15 + 14*Y^13 + 78*Y^11 + 220*Y^9 + 330*Y^7 + 252*Y^5 + 84*Y^3 + 8*Y
____________________________________________________________
Mathworld expresses that ratio of Fibonacci numbers as a single value of a Fibonacci polynomial: for m odd integer, F_{mn} / F_m = F_n ( F_{m-1} + F_{m+1} ) --- after stripping frivolous disguise! However, the sum formula holds more generally for integer m,n , and for Fibonacci polynomials: F_{mn}(Y) / F_n(Y) = SUM_{1 <= k <= m} F_{mn-kn+1}(Y) ( F_{n-1}(Y) )^{k-1} ; can this more general form be improved in a similar fashion? Fred Lunnon On 11/27/15, Fred Lunnon <fred.lunnon@gmail.com> wrote:
An associated problem involving (notionally) only Fibonacci numbers: For variable m,n , assumed to take only coprime (or perhaps distinct prime) values, express the integer F_(m n) / (F_m F_n) as a polynomial in suitable F_k .
[ Eg. for m,n = 5,7 , F_35/F_5 F_7 = 141961 .]
A partial solution, independent of coprimality, is F_(mn) / F_n = SUM_{1 <= k <= m} F_(mn-kn+1) F_(n-1)^(k-1) ; extracting factor F_m as well threatens more of a challenge ...
Fred Lunnon
On 11/25/15, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Define Fibonacci polynomials F_n(Y) for integer n , variable Y via
F_0(Y) = 0 , F_1(Y) = F_{-1}(Y) = 1 ,
F_{n+2}(Y) - Y F_{n+1}(Y) - F_n(Y) = 0 .
See https://en.wikipedia.org/wiki/Fibonacci_polynomials http://mathworld.wolfram.com/FibonacciPolynomial.html --- though compare alternative (marginally less tractable in practice) http://oeis.org/wiki/Fibonacci_polynomials .
The polynomial sequence shares elementary properties with the Fibonacci number sequence F_n : in particular strong divisibility, established via essentially the same argument --- see (engagingly pedestrian) https://proofwiki.org/wiki/Divisibility_of_Fibonacci_Numbers
[Whence this property may be inferred for other sequences --- 14 and counting --- in OEIS. Strong divisibility, that is, not engaging pedestrianism.]
I hope to post a more comprehensive account in a few days, explaining the how these matters bear on eccentric gear trains; meanwhile the following modest though positive advance afforded me such satisfaction, that I am unable to resist a little waving it about.
**Puzzle** Show that there is a constant t such that for all odd prime p ,
F_2p(Y) = s Y F_p(Y) F_p(Z) ;
where s = (-1)^((p-1)/2) and Z^2 = -(Y^2 + t) .
Evaluate t , and deduce that F_p(Y) is irreducible.
For example when p = 7 ,
F_14(Y) = Y (Y^6+5*Y^4+6*Y^2+1) (Y^6+7*Y^4+14*Y^2+7) ,
irreducibly.
Fred Lunnon
____________________________________________________________
n F_n(Y) 0 0 1 1 2 Y 3 Y^2 + 1 4 Y^3 + 2*Y 5 Y^4 + 3*Y^2 + 1 6 Y^5 + 4*Y^3 + 3*Y 7 Y^6 + 5*Y^4 + 6*Y^2 + 1 8 Y^7 + 6*Y^5 + 10*Y^3 + 4*Y 9 Y^8 + 7*Y^6 + 15*Y^4 + 10*Y^2 + 1 10 Y^9 + 8*Y^7 + 21*Y^5 + 20*Y^3 + 5*Y 11 Y^10 + 9*Y^8 + 28*Y^6 + 35*Y^4 + 15*Y^2 + 1 12 Y^11 + 10*Y^9 + 36*Y^7 + 56*Y^5 + 35*Y^3 + 6*Y 13 Y^12 + 11*Y^10 + 45*Y^8 + 84*Y^6 + 70*Y^4 + 21*Y^2 + 1 14 Y^13 + 12*Y^11 + 55*Y^9 + 120*Y^7 + 126*Y^5 + 56*Y^3 + 7*Y 15 Y^14 + 13*Y^12 + 66*Y^10 + 165*Y^8 + 210*Y^6 + 126*Y^4 + 28*Y^2 + 1 16 Y^15 + 14*Y^13 + 78*Y^11 + 220*Y^9 + 330*Y^7 + 252*Y^5 + 84*Y^3 + 8*Y
____________________________________________________________
participants (1)
-
Fred Lunnon