Feladat: F.3006 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Burcsi Péter ,  Fey Dániel ,  Hertz István ,  Koblinger Egmont ,  Németh Ákos ,  Németh Zoltán ,  Rákóczi Bálint ,  Szádeczky-Kardoss Szabolcs ,  Szeredi Tibor ,  Valkó Benedek 
Füzet: 1994/december, 498 - 499. oldal  PDF  |  MathML 
Témakör(ök): Racionális együtthatós polinomok, Fibonacci-sorozat, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1994/március: F.3006

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az egyszerűség kedvéért definiáljuk a Fibonacci-sorozatot nempozitív indexekre is úgy, hogy az an+2=an+1+an, azaz an=an+2-an+1 azonosság ezekre is igaz maradjon:

a0=a2-a1=1-1=0;a-1=a1-a0=1-0=1;a-2=a0-a-1=0-1=-1;a-3=a-1-a-2=1-(-1)=2;⋮

A feladat állítása helyett a következőt fogjuk bebizonyítani:
Ha p egy n-edfokú polinom, és p(1),p(2),...,p(n+2) a kiterjesztett Fibonacci-sorozat ugyanilyen sorrendben egymás után következő elemei, akkor p főegyütthatója 1n!.
A bizonyítást n szerinti teljes indukcióval végezzük.
Először megmutatjuk, hogy a kiterjesztett sorozatban pontosan egyszer szerepel a 0. (Mint láttuk, ez éppen az a0.)
Tegyük fel, hogy ax=0, ahol x<0. (x>0 esetén ax>0). Ekkor ax+1 nem lehet 0, mert ellenkező esetben az egész sorozat nullákból állna. Viszont a rekurzió miatt ax+2=ax+ax+1=ax+1, ax+3=ax+1+ax+2=2ax+1, és általában ax+k=akax+1 lenne. Mivel k>0 esetén ak>0, ez k=-x választással azt jelentené, hgoy a0≠0, ami ellentmondás.
A sorozatban tehát csak egyszer szerepel a 0.
Legyen most n=0, azaz p konstans polinom. A feltétel szerint p(1) és p(2) két szomszédos elem: p(1)=ak, p(2)=ak+1. Mivel p konstans, ak=ak+1, amiből ak-1=ak+1-ak=0. Mint láttuk, ez csak akkor teljesül, ha k-1=0, azaz k=1 és p(x)=a1=1. Ilyenkor p főegyütthatója 1=10!, az állítás teljesül.
Tegyük fel, hogy az állítást már bebizonyítottuk n=(m-1)-re, és legyen p egy olyan m-edfokú polinom, amelyre p(1)=ak,p(2)=ak+1,...,p(m+2)=ak+m+1 valamilyen alkalmas k-val. Legyen
p(x)=bmxm+bm-1xm-1+...+b1x+b0.

Azt akarjuk bebizonyítani, hogy bm=1m!.
Tekintsük a q(x)=p(x+1)-p(x) polinomot. Erről a következőket állítjuk:
a) a q polinom (m-1)-edfokú és a főegyütthatója mbm;
b) q(1),q(2),...,q(m+1) ugyanilyen sorrendben egymás után következő elemei a kiterjesztett Fibonacci-sorozatnak.
a)
q(x)=p(x+1)-p(x)==(bm(x+1)m+bm-1(x+1)m-1+...+b1(x+1)+b0)--(bmxm+bm-1xm-1+...+b1x+b0).

A hatványozást elvégezve, a legalább (m-1)-edfokú tagok:
(bmxm+(m1)bmxm-1+bm-1xm-1)-(bmxm+bm-1xm-1)=mbmxm-1.

Az állítás tehát teljesül.
b) Ha 1≤j≤m+1, akkor
q(j)=p(j+1)-p(j)=ak+j-ak+j-1=ak+j-2,

tehát q(1)=ak-1,q(2)=ak,q(3)=ak+1,...,q(m+1)=ak+m-1; ez az állítás is teljesül.
Az indukciós feltevés szerint q főegyütthatója 1(m-1)!, tehát mbm=1(m-1)!, vagyis bm=1m!. Állításunkat ezzel igazoltuk.
A feladat a bizonyított állításnak speciális esete.
Megjegyzések.
1. Az indukció nem működik a sorozat kiterjesztése nélkül, ugyanis q(1) a sorozatban megelőzi p(1)-et. Emiatt a p(1)=a1 esetet külön kellene vizsgálni.
2. A polinom értékei is egyértelműek; ez a megoldásból könnyen látható:
p(1)=a101,p(2)=a102,...p(102)=a202.

Ebből az is következik, hogy maga a p polinom is egyértelmű.
3. Az eddigiekből még nem látszik, hogy a feladatnak megfelelő polinom létezik. Ismeretes azonban, hogy pontosan egy olyan legfeljebb 100-adfokú polinom létezik, amelyre p(1)=a101,...,p(101)=a201. (Ezt a polinomot Lagrange-interpolációs polinomnak nevezik.) A megoldáshoz hasonlóan be lehet bizonyítani, hogy p-ben a 100-adfokú tag együtthatója 1100! és p(102)=a202.