Feladat: N.149 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bérczi Gergely ,  Juhász András ,  Lippner Gábor ,  Lukács László 
Füzet: 1998/március, 163 - 165. oldal  PDF file
Témakör(ök): Rekurzív eljárások, Számsorozatok, Polinomok, Nehéz feladat
Hivatkozás(ok):Feladatok: 1997/október: N.149

Definiáljuk az (an) sorozatot a következőképpen:
a0=a1=1,(n+1)an+1=(2n+1)an+3nan-1.(4)
Mutassuk meg, hogy a sorozat egész számokból áll.

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.

Megmutatjuk, hogy an nem más, mint az (1+x+x2)n polinomban xn együtthatója. Jelöljük egyelőre cn-nel az xn együtthatóját az (1+x+x2)n polinomban. Azt könnyű ellenőrizni, hogy c0=a0=1 és c1=a1=1. Mivel

(1+x+x2)n=xn(1+x+1x)n=xnk=0nnchoosek(x+1x)k,
ebből az alakból kiolvasható, hogy
cn=0kn2nchoose2k2kchoosek=0kn2n!k!2(n-2k)!.(1)

Az (1) azonosság egyszerű átrendezéseiből kapjuk, hogy
cn+1=0kn+12(n-1)!k!2(n-2k+1)!n(n+1),cn=0kn+12(n-1)!k!2(n-2k+1)!n(n-2k+1),cn-1=0kn-12(n-1)!k!2(n-2k-1)!=0kn+12(n-1)!k!2(n-2k+1)!(n-2k)(n-2k+1),cn-1=0kn+12(n-1)!(k-1)!2(n-2k+1)!=0kn+12(n-1)!k!2(n-2k+1)!k2.
Ezek alapján
(2n+1)cn+3ncn-1=(2n+1)cn+4ncn-1-ncn-1==0kn+12(n-1)!k!2(n-2k+1)!((2n+1)n(n-2k+1)+4nk2-n(n-2k)(n-2k+1))==0kn+12(n-1)!k!2(n-2k+1)!n(n+1)2=(n+1)cn+1,
vagyis az (an) és (cn) sorozatokra ugyanaz a rekurzió teljesül.
 
Megjegyzések. 1. Egy polinom együtthatóit komplex függvénytani eszközökkel is lehet kezelni. Például az (x2+x+1)n polinomban xn együtthatóját felírhatjuk a következő alakban:
cn=12π-ππ(e2it+eit+1)ne-intdt.
Ebből a rekurzió parciális integrálással nyerhető. (A feladat innen származik.)
2. Lippner Gábor és Lukács László az F(x)=n=0anxn generátorfüggvény vizsgálatával egy érdekes azonosságot fedezett fel:
a0an+a1an-1+...+an-1a1+ana0=3n+1+(-1)n4.(2)
Nem nehéz végiggondolni, hogy F definíciója |x|<13 esetén értelmes, és ebben az intervallumban teljesül rá a
(3x2+2x-1)F'(x)+(3x+1)F(x)=0;F(0)=1
homogén lineáris differenciálegyenlet. Ezt megoldva F(x)=1(1-3x)(1+x),
F2(x)=341-3x+141+x=34n=0(3x)n+14n=0(-x)n=n=03n+1+(-1)n4xn.
Másfelől
F2(x)=(n=0anxn)2=n=0(a0an+...+ana0)xn,
és a függvény az együtthatókat egyértelműen meghatározza, ebből (2) következik.
Természetesen (2) bizonyításához nincs szükség analitikus eszközökre, teljes indukcióval is igazolható.
A (2) azonosságból a feladat állítása viszonylag egyszerűen következik.