Fibonacci-polinomok

A Fibonacci-polinomok a Fibonacci-számokhoz hasonló számsorozatok neve.

1. számú Fibonacci-polinomok

Az (1. számú) Fibonacci-polinomok kiszámítása a következő (A011973 sorozat az OEIS-ben):

C és n természetes számok, C az egész sorozatra jellemző konstans, n a sorozat elemének sorszáma.

${\displaystyle f_{1}(C,0)=0}$

${\displaystyle f_{1}(C,1)=1}$

${\displaystyle f_{1}(C,n+1)=Cf_{1}(C,n)+f_{1}(C,n-1)}$

Ha n értéke 1-től 13-ig változik, a sorozat első elemei C-től függően ezek lesznek:

n=1: ${\displaystyle (1)}$

n=2: ${\displaystyle (C)}$

n=3: ${\displaystyle (C^{2}+1)}$

n=4: ${\displaystyle (C^{3}+2C)}$

n=5: ${\displaystyle (C^{4}+3C^{2}+1)}$

n=6: ${\displaystyle (C^{5}+4C^{3}+3C)}$

n=7: ${\displaystyle (C^{6}+5C^{4}+6C^{2}+1)}$

n=8: ${\displaystyle (C^{7}+6C^{5}+10C^{3}+4C)}$

n=9: ${\displaystyle (C^{8}+7C^{6}+15C^{4}+10C^{2}+1)}$

n=10: ${\displaystyle (C^{9}+8C^{7}+21C^{5}+20C^{3}+5C)}$

n=11: ${\displaystyle (C^{10}+9C^{8}+28C^{6}+35C^{4}+15C^{2}+1)}$

n=12: ${\displaystyle (C^{11}+10C^{9}+36C^{7}+56C^{5}+35C^{3}+6C)}$

n=13: ${\displaystyle (C^{12}+11C^{10}+45C^{8}+84C^{6}+70C^{4}+21C^{2}+1)}$

Az (1. számú) Fibonacci-polinomok (páratlan n-ek esetében) megkaphatók a következő formulával is:

${\displaystyle f_{1}(C,n)=\sum _{k=0}^{\frac {n-1}{2}}{\binom {n-1-k}{k}}C^{n-1-2k}}$.

Az alábbi függvény (a Binet-formula általánosítása) is azonos eredményre vezet (ez a Fibonacci-polinomok kiszámításának legbonyolultabb módja):

${\displaystyle f_{1}(C,n)={\cfrac {\left({\cfrac {C+{\sqrt {C^{2}+4}}}{2}}\right)^{n}-\left({\cfrac {C-{\sqrt {C^{2}+4}}}{2}}\right)^{n}}{\sqrt {C^{2}+4}}}}$

2. számú Fibonacci-polinomok

A Fibonacci-polinomoknak létezik egy másik „családja” is. Ez abban különbözik, hogy a műveletek során nem az utolsó, hanem az utolsó előtti polinomot kell szorozni a D konstanssal.

${\displaystyle f_{2}(D,0)=0}$

${\displaystyle f_{2}(D,1)=1}$

${\displaystyle f_{2}(D,n+1)=f_{2}(D,n)+Df_{2}(D,n-1)}$

Értékei n = 1 ... 13 tartományra:

n=1: ${\displaystyle (1)}$

n=2: ${\displaystyle (1)}$

n=3: ${\displaystyle (1+D)}$

n=4: ${\displaystyle (1+2D)}$

n=5: ${\displaystyle (1+3D+D^{2})}$

n=6: ${\displaystyle (1+4D+3D^{2})}$

n=7: ${\displaystyle (1+5D+6D^{2}+D^{3})}$

n=8: ${\displaystyle (1+6D+10D^{2}+4D^{3})}$

n=9: ${\displaystyle (1+7D+15D^{2}+10D^{3}+D^{4})}$

n=10: ${\displaystyle (1+8D+21D^{2}+20D^{3}+5D^{4})}$

n=11: ${\displaystyle (1+9D+28D^{2}+35D^{3}+15D^{4}+D^{5})}$

n=12: ${\displaystyle (1+10D+36D^{2}+56D^{3}+35D^{4}+6D^{5})}$

n=13: ${\displaystyle (1+11D+45D^{2}+84D^{3}+70D^{4}+21D^{5}+D^{6})}$

Zárt formula:

${\displaystyle f_{2}(D,n)=\sum _{k=0}^{\frac {n-1}{2}}{\binom {n-1-k}{k}}D^{k}}$

Általános alak:

${\displaystyle f_{2}(D,n)={\cfrac {\left({\cfrac {1+{\sqrt {1+4D}}}{2}}\right)^{n}-\left({\cfrac {1-{\sqrt {1+4D}}}{2}}\right)^{n}}{\sqrt {1+4D}}}}$

Megjegyzések

1. megjegyzés

Legfőbb különbség a két polinom-család között az, hogy az 1. Fibonacci-polinomok "hiányosak" (vagy csupa páros, vagy csupa páratlan kitevőjű hatványt tartalmaznak).

2. megjegyzés

Mindkét polinom-családban közös, hogy ha az együtthatókat összeadjuk, akkor Fibonacci-számokat kapunk, például:

ha (n=11): ${\displaystyle (1+9+28+35+15+1)=89}$,

vagy ha (n=13): ${\displaystyle (1+11+45+84+70+21+1)=233}$.

3. megjegyzés

A rekurzió miatt, ha n értéke osztható d-vel, akkor ${\displaystyle f_{1}(C,n)}$ osztható ${\displaystyle f_{1}(C,d)}$-vel, illetve ${\displaystyle f_{2}(D,n)}$ osztható ${\displaystyle f_{2}(D,d)}$-vel (akár konkrét számokról, akár polinomokról van szó).

4. megjegyzés

Mindkét esetben, ha n értéke prímszám, akkor a hozzá tartozó polinom irreducibilis (a természetes számok teste felett), ha n értéke összetett szám, akkor a hozzá tartozó polinom reducibilis.

5. megjegyzés

Az (1. számú) Fibonacci-polinomok általános alakjában szereplő ${\displaystyle {\cfrac {C+{\sqrt {C^{2}+4}}}{2}}}$ kifejezés megkapható, mint az ${\displaystyle x^{2}-Cx-1=0}$ (másodfokú) egyenlet nagyobbik (pozitív) gyöke is, továbbá ez a gyök egy állandó számokból álló („homogén”) lánctört határértéke is egyben:

${\displaystyle x_{1}={\cfrac {C+{\sqrt {C^{2}+4}}}{2}}=[C;C,C,C,C,C,C,C,\cdots ]=C+{\cfrac {1}{C+{\cfrac {1}{C+\cdots }}}}}$.

Arany, ezüst és fém-számokat előállító polinomok

A fent ismertetett két módszert kombinálni is lehet, (amikor a C-vel és a D-vel való szorzást egy ütemben hajtjuk végre):

${\displaystyle f_{3}(C,D,0)=0}$

${\displaystyle f_{3}(C,D,1)=1}$

${\displaystyle f_{3}(C,D,n+1)=Cf_{3}(C,D,n)+Df_{3}(C,D,n-1)}$

Polinomjaink (ha (n) értéke 1-től 13-ig változik) a következők:

n=1: ${\displaystyle (1)}$

n=2: ${\displaystyle (C)}$

n=3: ${\displaystyle (C^{2}+D)}$

n=4: ${\displaystyle (C^{3}+2CD)}$  

n=5: ${\displaystyle (C^{4}+3C^{2}D+D^{2})}$

n=6: ${\displaystyle (C^{5}+4C^{3}D+3CD^{2})}$

n=7: ${\displaystyle (C^{6}+5C^{4}D+6C^{2}D^{2}+D^{3})}$

n=8: ${\displaystyle (C^{7}+6C^{5}D+10C^{3}D^{2}+4CD^{3})}$

n=9: ${\displaystyle (C^{8}+7C^{6}D+15C^{4}D^{2}+10C^{2}D^{3}+D^{4})}$

n=10: ${\displaystyle (C^{9}+8C^{7}D+21C^{5}D^{2}+20C^{3}D^{3}+5CD^{4})}$

n=11: ${\displaystyle (C^{10}+9C^{8}D+28C^{6}D^{2}+35C^{4}D^{3}+15C^{2}D^{4}+D^{5})}$

n=12: ${\displaystyle (C^{11}+10C^{9}D+36C^{7}D^{2}+56C^{5}D^{3}+35C^{3}D^{4}+6CD^{5})}$

n=13: ${\displaystyle (C^{12}+11C^{10}D+45C^{8}D^{2}+84C^{6}D^{3}+70C^{4}D^{4}+21C^{2}D^{5}+D^{6})}$

Vegyük az alábbi (másodfokú) egyenlet két gyökét (ahol C természetes szám, D egész szám):

${\displaystyle x^{2}-Cx-D=0}$

${\displaystyle x_{1}={\cfrac {C+{\sqrt {C^{2}+4D}}}{2}}}$

${\displaystyle x_{2}={\cfrac {C-{\sqrt {C^{2}+4D}}}{2}}}$

Ezzel a két gyökkel (a Fibonacci-számokat generáló függvény mintájára) megkonstruálhatunk egy (három-változós) függvényt:

${\displaystyle f_{3}(C,D,n)={\cfrac {(x_{1})^{n}-(x_{2})^{n}}{x_{1}-x_{2}}}}$, azaz

${\displaystyle f_{3}(C,D,n)={\cfrac {\left({\cfrac {C+{\sqrt {C^{2}+4D}}}{2}}\right)^{n}-\left({\cfrac {C-{\sqrt {C^{2}+4D}}}{2}}\right)^{n}}{\sqrt {C^{2}+4D}}}}$.

Ez a függvény (a hozzá tartozó polinomokkal együtt) univerzális, mert

(I.) ${\displaystyle (C=1)}$ és ${\displaystyle (D=1)}$ esetén a Fibonacci-számokat állítja elő,

(II.) ${\displaystyle (D=1)}$ és ${\displaystyle (C=2,3,4)}$ esetén a METAL-számokat (ezüst, bronz, vörösréz) állítja elő.^[1]

(III.)

${\displaystyle (C=6)}$ és ${\displaystyle (D=-1)}$ esetében azokat a számokat, melyeknek a négyzete háromszögszám, az ${\displaystyle M^{2}=N(N+1)/2}$ (Diofantoszi) egyenlet egész (M) megoldásait:

M = 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179, 271669860, 1583407981, 9228778026, 53789260175, 313506783024, 1827251437969, 10650001844790, 62072759630771, 361786555939836, 2108646576008245, 12290092900109634, 71631910824649559 ...

(IV.)

${\displaystyle (D=1)}$ és ${\displaystyle (n=3)}$ esetében a ${\displaystyle (C^{2}+1)}$ formulát kapjuk, ami ${\displaystyle (C=2,4,16,256)}$ esetében a Fermat-féle prímszámokat állítja elő ${\displaystyle (5,17,257,65537)}$.

(V.)

${\displaystyle (C=3)}$ és ${\displaystyle (D=-2)}$ esetében pedig Mersenne-számokat kapunk, képletük: ${\displaystyle (M_{n}=2^{n}-1)}$.

Bármilyen meglepő, ebből az következik, hogy a Mersenne-számok is rekurzívak:

${\displaystyle M_{0}=0}$

${\displaystyle M_{1}=1}$

${\displaystyle M_{n+1}=3M_{n}-2M_{n-1}}$.