Polinomul Fibonacci
Polinomul Fibonacci
În matematică , polinoamele Fibonacci , denumite în cinstea matematicianului italian Leonardo Fibonacci , sunt o succesiune de polinoame care generalizează numerele Fibonacci , definite într-un mod care este egal cu numărul a n- lea din secvența Fibonacci. De polinoame Lucas generaliza chiar și un număr de Lucas .
Fnu(X){\ displaystyle F_ {n} (x)}Fnu(1){\ displaystyle F_ {n} (1)}
Definiție
Polinoamele Fibonacci sunt definite printr-o relație de recurență liniară .
Fnu(X)={0,dacă nu=01,dacă nu=1XFnu-1(X)+Fnu-2(X),dacă nu≥2{\ displaystyle F_ {n} (x) = {\ begin {cases} 0 și {\ mbox {si}} n = 0 \\ 1 și {\ mbox {si}} n = 1 \\ xF_ {n -1} (x) + F_ {n-2} (x) și {\ mbox {si}} n \ geq 2 \ end {cases}}} ; este un polinom de grad n -1.
Fnu{\ displaystyle F_ {n}}Primele polinoame Fibonacci sunt:
F0(X)=0{\ displaystyle F_ {0} (x) = 0 \,}
F1(X)=1{\ displaystyle F_ {1} (x) = 1 \,}
F2(X)=X{\ displaystyle F_ {2} (x) = x \,}
F3(X)=X2+1{\ displaystyle F_ {3} (x) = x ^ {2} +1 \,}
F4(X)=X3+2X{\ displaystyle F_ {4} (x) = x ^ {3} + 2x \,}
F5(X)=X4+3X2+1{\ displaystyle F_ {5} (x) = x ^ {4} + 3x ^ {2} +1 \,}
F6(X)=X5+4X3+3X{\ displaystyle F_ {6} (x) = x ^ {5} + 4x ^ {3} + 3x \,}
Polinoamele Lucas sunt definite de aceeași inducție, dar cu valori inițiale diferite:
Lnu(X)={2,dacă nu=0X,dacă nu=1XLnu-1(X)+Lnu-2(X),dacă nu≥2.{\ displaystyle L_ {n} (x) = {\ begin {cases} 2, & {\ mbox {si}} n = 0 \\ x, & {\ mbox {si}} n = 1 \\ xL_ {n -1} (x) + L_ {n-2} (x) și {\ mbox {si}} n \ geq 2. \ end {cases}}} ; este un polinom de grad n .
Lnu{\ displaystyle L_ {n}}Primele polinoame Lucas sunt:
L0(X)=2{\ displaystyle L_ {0} (x) = 2 \,}
L1(X)=X{\ displaystyle L_ {1} (x) = x \,}
L2(X)=X2+2{\ displaystyle L_ {2} (x) = x ^ {2} +2 \,}
L3(X)=X3+3X{\ displaystyle L_ {3} (x) = x ^ {3} + 3x \,}
L4(X)=X4+4X2+2{\ displaystyle L_ {4} (x) = x ^ {4} + 4x ^ {2} +2 \,}
L5(X)=X5+5X3+5X{\ displaystyle L_ {5} (x) = x ^ {5} + 5x ^ {3} + 5x \,}
L6(X)=X6+6X4+9X2+2.{\ displaystyle L_ {6} (x) = x ^ {6} + 6x ^ {4} + 9x ^ {2} +2. \,}
Numerele Fibonacci sunt apoi calculate prin evaluarea valorii polinomului F n când x = 1; a numerelor pell sunt determinate prin evaluarea F n atunci când x = 2. În final, numerele Lucas sunt obținute prin evaluarea L n la 1.
Aceste secvențe de polinoame sunt secvențe Lucas asociate: avem
Fnu(X)=Unu(X,-1),{\ displaystyle F_ {n} (x) = U_ {n} (x, -1), \,}
Lnu(X)=Vnu(X,-1).{\ displaystyle L_ {n} (x) = V_ {n} (x, -1). \,}
Generarea de serii
Seria generatorului pentru polinoamele Fibonacci este:
∑nu=0∞Fnu(X)tnu=t1-Xt-t2.{\ displaystyle \ sum _ {n = 0} ^ {\ infty} F_ {n} (x) t ^ {n} = {\ frac {t} {1-xt-t ^ {2}}}.}De asemenea, seria generatoare de polinoame Lucas este:
∑nu=0∞Lnu(X)tnu=2-Xt1-Xt-t2.{\ displaystyle \ sum _ {n = 0} ^ {\ infty} L_ {n} (x) t ^ {n} = {\ frac {2-xt} {1-xt-t ^ {2}}}. }Relații remarcabile
Ca cazuri speciale ale secvențelor Lucas , aceste polinoame verifică multe identități.
Acestea pot fi definite pentru indicii negativi prin
F-nu(X)=(-1)nu-1Fnu(X),L-nu(X)=(-1)nuLnu(X).{\ displaystyle F _ {- n} (x) = (- 1) ^ {n-1} F_ {n} (x), \, L _ {- n} (x) = (- 1) ^ {n } L_ {n} (x).}De asemenea avem:
Fm+nu(X)=Fm+1(X)Fnu(X)+Fm(X)Fnu-1(X){\ displaystyle F_ {m + n} (x) = F_ {m + 1} (x) F_ {n} (x) + F_ {m} (x) F_ {n-1} (x) \,}
Lm+nu(X)=Lm(X)Lnu(X)-(-1)nuLm-nu(X){\ displaystyle L_ {m + n} (x) = L_ {m} (x) L_ {n} (x) - (- 1) ^ {n} L_ {mn} (x) \,}
Fnu+1(X)Fnu-1(X)-Fnu(X)2=(-1)nu{\ displaystyle F_ {n + 1} (x) F_ {n-1} (x) -F_ {n} (x) ^ {2} = (- 1) ^ {n} \,}
F2nu(X)=Fnu(X)Lnu(X).{\ displaystyle F_ {2n} (x) = F_ {n} (x) L_ {n} (x). \,}
Expresii similare cu formula lui Binet există:
Fnu(X)=α(X)nu-β(X)nuα(X)-β(X),Lnu(X)=α(X)nu+β(X)nu,{\ displaystyle F_ {n} (x) = {\ frac {\ alpha (x) ^ {n} - \ beta (x) ^ {n}} {\ alpha (x) - \ beta (x)}}, \, L_ {n} (x) = \ alpha (x) ^ {n} + \ beta (x) ^ {n},}sau
α(X)=X+X2+42,β(X)=X-X2+42{\ displaystyle \ alpha (x) = {\ frac {x + {\ sqrt {x ^ {2} +4}}} {2}}, \, \ beta (x) = {\ frac {x - {\ sqrt {x ^ {2} +4}}} {2}}}sunt soluțiile (în t ) ale
t2-Xt-1=0.{\ displaystyle t ^ {2} -xt-1 = 0. \,}Puterile lui x sunt exprimate ca o combinație de polinoame Fibonacci prin
Xnu=Fnu+1(X)+∑k=1⌊nu/2⌋(-1)k[(nuk)-(nuk-1)]Fnu+1-2k(X).{\ displaystyle x ^ {n} = F_ {n + 1} (x) + \ sum _ {k = 1} ^ {\ lfloor n / 2 \ rfloor} (- 1) ^ {k} \ left [{\ binom {n} {k}} - {\ binom {n} {k-1}} \ right] F_ {n + 1-2k} (x).}De exemplu,
X4=F5(X)-3F3(X)+2F1(X){\ displaystyle x ^ {4} = F_ {5} (x) -3F_ {3} (x) + 2F_ {1} (x) \,}
X5=F6(X)-4F4(X)+4F2(X){\ displaystyle x ^ {5} = F_ {6} (x) -4F_ {4} (x) + 4F_ {2} (x) \,}
X6=F7(X)-5F5(X)+9F3(X)-5F1(X){\ displaystyle x ^ {6} = F_ {7} (x) -5F_ {5} (x) + 9F_ {3} (x) -5F_ {1} (x) \,}
X7=F8(X)-6F6(X)+14F4(X)-14F2(X){\ displaystyle x ^ {7} = F_ {8} (x) -6F_ {6} (x) + 14F_ {4} (x) -14F_ {2} (x) \,}.
Rădăcinile și factorizarea polinoamelor Fibonacci
Dându , acesta este verificat cu notația de mai sus , și , prin urmare , care nu dispar pentru ; astfel rădăcinile sunt imaginar pur . Deducem factorizarea :
X=2eucoshz=eu(ez+e-z){\ displaystyle x = 2 \ mathrm {i} \ cosh z = \ mathrm {i} \ left (\ mathrm {e} ^ {z} + \ mathrm {e} ^ {- z} \ right)}α(X)=(X+X2+4)/2=euez{\ displaystyle \ alpha \ left (x \ right) = \ left (x + {\ sqrt {x ^ {2} +4}} \ right) / 2 = \ mathrm {i} \, \ mathrm {e} ^ {z}}β(X)=(X-X2+4)/2=eue-z{\ displaystyle \ beta \ left (x \ right) = \ left (x - {\ sqrt {x ^ {2} +4}} \ right) / 2 = \ mathrm {i} \, \ mathrm {e} ^ {-z}}Fnu(X)=eunu-1enuz-e-nuzez-e-z{\ displaystyle F_ {n} \ left (x \ right) = \ mathrm {i} ^ {n-1} {\ frac {\ mathrm {e} ^ {nz} - \ mathrm {e} ^ {- nz} } {\ mathrm {e} ^ {z} - \ mathrm {e} ^ {- z}}}}z=eukπ/nu{\ displaystyle z = \ mathrm {i} \, k \ pi / n}Fnu{\ displaystyle F_ {n}}2eucos(kπ/nu){\ displaystyle 2 \ mathrm {i} \ cos {(k \ pi / n)}}Fnu(X){\ displaystyle F_ {n} \ left (x \ right)}
F2nu(X)=X∏1≤k≤nu-1X2+4cos2(kπnu){\ displaystyle F_ {2n} \ left (x \ right) = x \ prod _ {1 \ leq k \ leq n-1} x ^ {2} +4 \ cos ^ {2} \ left ({\ frac { k \ pi} {n}} \ right)} și
F2nu+1(X)=∏1≤k≤nuX2+4cos2(2kπ2nu+1){\ displaystyle F_ {2n + 1} \ left (x \ right) = \ prod _ {1 \ leq k \ leq n} x ^ {2} +4 \ cos ^ {2} \ left ({\ frac {2k \ pi} {2n + 1}} \ dreapta)},
apoi, luând , o expresie trigonometrică a numerelor Fibonacci:
X=1{\ displaystyle x = 1}
Fnu=∏1≤k≤(nu-1)/21+4cos2(kπnu)=∏1≤k≤(nu-1)/23+2cos(2kπnu){\ displaystyle {\ mathcal {F}} _ {n} = \ prod _ {1 \ leq k \ leq (n-1) / 2} 1 + 4 \ cos ^ {2} \ left ({\ frac {k \ pi} {n}} \ right) = \ prod _ {1 \ leq k \ leq (n-1) / 2} 3 + 2 \ cos \ left ({\ frac {2k \ pi} {n}} \ dreapta)} ;
formule analoage pot fi obținute pentru polinoamele Lucas.
Interpretare combinatorie
Dacă F ( n , k ) este coeficientul lui x k în F n ( x ), adică
Fnu(X)=∑k=0nuF(nu,k)Xk,{\ displaystyle F_ {n} (x) = \ sum _ {k = 0} ^ {n} F (n, k) x ^ {k}, \,}atunci F ( n , k ) este numărul de moduri în care putem asfalta o bandă de n -1 pătrate cu domino (dreptunghiuri ) și exact k pătrate unitare. În mod echivalent, F ( n , k ) este numărul de moduri de a scrie n −1 ca o sumă ordonată de 1 și 2, cu exact k apariții de 1. De exemplu, se poate scrie F (6,3) = 4 și 5 în 4 moduri, 1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 2 + 1 + 1 + 1, ca suma a 1 și 2 cu exact trei 1. Determinarea poziția 1 într-o astfel de sumă, devine evident că F ( n , k ) este egal cu coeficientul binomial2×1{\ displaystyle 2 \ times 1}
F(nu,k)=(nu+k-12k){\ displaystyle F (n, k) = {\ binom {\ tfrac {n + k-1} {2}} {k}}}unde n și k sunt de paritate opusă, ceea ce face posibilă citirea acestor coeficienți în triunghiul lui Pascal , așa cum se arată mai sus.
Referințe
(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia în
engleză intitulat
„ Fibonacci polynomials ” ( vezi lista autorilor ) .
-
(în) Arthur T. Benjamin și Jennifer J. Quinn , Dovezi care contează cu adevărat , Washington, DC, MAA ,2003, 193 p. ( ISBN 0-88385-333-7 , citit online ) , „§9.4 Fibonacci și Lucas Polynomial” , p. 141.
-
(în) Leonard Carlitz , „ Câteva polinoame ortogonale legate de numerele Fibonacci ” , Fibonacci Quarterly , vol. 4, n o 1,1966, p. 43-48 ( citește online ).
-
Yuan și Zhang 2002
-
(în) Concursul Carnegie Mellon de informatică și matematică (CMIMC) 2016 , anul 10 (de la pagina 5)
-
Hoggatt și Bicknell 1973
-
(în) Bala Sury, „ Expresii trigonometrice pentru numerele lui Fibonacci și Lucas ” , Acta Math. Univ. Comenianae , vol. 79, n o 22010, p. 199-208 ( citiți online ).
Vezi și tu
Bibliografie
- (en) Dominique Foata și Guo-Niu Han, „ Fibonacci numbers and orthogonal polynomials ” , Leonardo Fibonacci: il tempo, le opere, l'eredit`a scientifica ,1994( citește online )
- (ro) VE Hoggatt și Marjorie Bicknell , „ Roots of Fibonacci polynomials. » , Fibonacci Quarterly , vol. 11,1973, p. 271–274 ( ISSN 0015-0517 , Math Reviews 0332645 , citiți online )
- (ro) VE Hoggatt și Calvin T. Long , „ Proprietăți de divizibilitate ale polinoamelor Fibonacci generalizate ” , Fibonacci Quarterly , vol. 12,1974, p. 113 ( Math Reviews 0352034 , citiți online )
- (en) Paolo Emilio Ricci , „ Generalized Lucas polynomials and Fibonacci polynomials ” , Rivista di Matematica della Università di Parma , vol. 4,1995, p. 137–146 ( Recenzii matematice 1395332 )
- (ro) Yi Yuan și Wenpeng Zhang , „ Unele identități care implică polinoamele Fibonacci ” , Fibonacci Quarterly , vol. 40, n o 4,2002, p. 314 ( Math Reviews 1920571 , citiți online )
- (în) Johann Cigler , „ q Fibonacci polynomials ” , Fibonacci Quarterly , n o 41,2003, p. 31–40 ( Math Reviews 1962279 , citiți online )
Articole similare
linkuri externe
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">