Feladat: F.2896 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Csorba Péter ,  Csörnyei Marianna ,  Faragó Gergely ,  Párniczky Benedek 
Füzet: 1992/november, 365 - 367. oldal  PDF file
Témakör(ök): Algebrai átalakítások, Elsőfokú (és arra visszavezethető) egyenletrendszerek, Számsorozatok, Irracionális egyenletek, Rekurzív sorozatok, Feladat
Hivatkozás(ok):Feladatok: 1992/március: F.2896

Legyen minden n nemnegatív egészre an=[(1+2)n]. Bizonyítsuk be, hogy tetszőleges k2 esetén

a2k=2a2k-1+a2k-2ésa2k+1=2a2k+a2k-1+2.

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.

Legyen bn=(1+2)n+(1-2)n. A zárójelet a binomiális tétel szerint felbontva láthatjuk, hogy bn értéke (minden n-re) egész szám. Mivel páros n-re 0<(1-2)n<1, páratlan n-re pedig -1<(1-2)n<0, azért

bn={+1=an+1,ha  n  páros.[(1+2)n]=anha  n  páratlan.
Így a2m=b2m-1 és a2m-1=b2m-1. A bizonyítandó összefüggések közül az elsőt a bn-ek segítségével felírva:
b2k-1=2b2k-1+b2k-2-1,
azaz
b2k=2b2k-1+b2k-2,(1)
a második összefüggés pedig a következő alakot ölti
b2k+1=2(b2k-1)+b2k-1+2,
azaz
b2k+1=2b2k+b2k-1.(2)

Az (1) és (2) együtt éppen azt jelenti, hogy minden n-re
bn+2=2bn+1+bn.(3)

A (3) azonosság fennállását egyszerű számolással igazolhatjuk:
bn+2=(1+2)n+2+(1-2)n+2==(1+2)(1+2)n+1+(1-2)(1-2)n+1==2bn+1+(2-1)(1+2)n+1+(-2-1)(1-2)n+1==2bn+1+(2-1)(1+2)(1+2)n+(-2-1)(1-2)(1-2)n==2bn+1+bn.

Faragó Gergely (Fazekas M. Főv. Gyak. Gimn., III. o. t.)
 

Megjegyzés. Észrevehetjük, hogy 1+2 és 1-2 az x2-2x-1 polinom gyökei. A megoldásbeli számoláshoz hasonlóan általában beláthatjuk, hogy ha x1,x2,...,xk az xk-ak-1xk-1-ak-2xk-2-...-a1x-a0 polinom gyökei, és c1,c2,...,ck tetszőleges rögzített számok, akkor a
bn=c1x1n+c2x2n+...+ckxkn(n=1,2...)
sorozat elemeire teljesül a
bn+k=ak-1bn+k-1+ak-2bn+k-2+...+a1bn+1+a0bn
rekurzió. Ez az észrevétel lehetővé teszi, hogy lineáris rekurzióval adott sorozatok tagjait explicit formulával előállítsuk. Legyenek ugyanis d1,...,dk;a0,...,ak-1 rögzített számok, és definiáljuk a (bn) sorozatot a következőképpen:
b1=d1,b2=d2,...,bk=dk,

bk+1=ak-1bk+ak-2bk-1+...+a1b2+a0b1,

bk+i=ak-1bk+i-1+ak-2bk+i-2+...+a1bi+1+a0bi(i=1,2,...).
 

Tegyük fel, hogy az xk-ak-1xk-1-...-a0 polinomnak x1,x2,...,xk páronként különböző gyökei. Megmutatható, hogy ekkor léteznek olyan c1,...,ck számok, amelyekkel (bármely n-re) a sorozat n-edik tagja: bn=c1xn+...+ckxn; a ci értékeket egy k egyenletből álló lineáris egyenletrendszer megoldásaként kaphatjuk.
Példaként tekintsük a b1=1, b2=1, bi+2=bi+1+bi(i=1,2,...) előírással meghatározott, közismert Fibonacci-sorozatot. A rekurzióbeli együtthatók segítségével előálló x2-x-1 polinom gyökei 1+52 és 1-52.
Keressük a sorozat elemeit bn=c1(1+52)n+c2(1-52)n alakban. (Bárhogyan válasszuk is c1,c2-t, ezzel már a bi+2=bi+1+bi összefüggés fennállását biztosítottuk.) A b1=b2=1 követelmény a következő két egyenletet adja c1-re és c2-re:
1+52c1+1-52c2=1,3+52c1+3-52c2=1.
Az egyenletrendszer (egyértelmű) megoldása: c1=15,c2=-15, így az n-edik Fibonacci-szám:
bn=15((1+52)n-(1-52)n).

Az érdeklődő olvasó figyelmébe ajánljuk a következő kérdést: Hogyan ,,menthető át'' az ismertetett módszer azokban az esetekben, amikor a megfelelő polinom gyökei nem mind különbözőek (létezik ,,többszörös'' gyök), illetve ha a polinomnak egyáltalán nem létezik valós gyöke. Az előbbihez b1=b2=1,bi+2=6bi+1-9bi, az utóbbihoz b1=b2=1,bi+2=2bi+1-4bi vizsgálata szolgálhat tapasztalatokkal.