Feladat: B.3735 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Filus Tamás 
Füzet: 2005/március, 158 - 159. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 2004/május: B.3735

Az xn sorozat első két eleme x1=1001, x2=1003 és ha n1, akkor xn+2=xn+1-2004xn. Mennyi a sorozat első 2004 elemének az összege?

Megoldás. Használjuk fel, hogy x1+x2=2004, így a rekurzió az alábbi formában írható:
xn+2=xn+1-x1-x2xn.

Írjuk fel a sorozat első néhány tagját:
1001;1003;x3=x2-x1-x2x1=-1;x4=x3-x1-x2x2=-1-x1-x2x2;x5=x4-x1-x2x3=-x4+x1+x2;x6=x5-x1-x2x4=-x4+x1+x2-x1-x2x4=-1;...
Vegyük észre, hogy x4+x5=x1+x2=2004 és x6=x3=-1.
Teljes indukcióval bebizonyítjuk, hogy tetszőleges nN esetén x3n+1+x3n+2=2004 és x3n+3=-1. Láttuk, hogy ezek n=1-re és 2-re fennállnak.
Tegyük fel, hogy (k-1)-ig igaz az állítás: x3k-2+x3k-1=2004 és x3k=-1. Belátjuk k-ra.
A rekurzió és az indukciós feltevés alapján
x3k+1=x3k-x3k-1-x3k-2x3k-1=-1-x3k-1-x3k-2x3k-1;x3k+2=x3k+1-x3k-1-x3k-2x3k=-x3k+1+x3k-1+x3k-2.
Ebből pedig x3k+1+x3k+2=x3k+1-x3k+1+x3k-1+x3k-2=2004 az indukciós feltevés miatt. Továbbá (ezt felhasználva)
x3k+3=x3k+2-x3k+2-x3k+1x3k+1=-1.

Ebből következik, hogy a sorozat első 2004 tagját hármasával csoportosítva a számok összege minden egyes csoportban 2003.
Mivel 2004=3668, az első 2004 tag 668 ilyen elemhármasból áll, így a keresett összeg 2003668=1338004.