Kistérségi tehetséggondozás
Rekurzív sorozatok Szoldatics József, Dunakeszi Napjainkban egyre több versenyen jelenik meg rekurzív sorozat. Ezek megoldásához ad ötleteket ez az előadás, A feladatok csoportosítva vannak megoldási módszerek szerint. Egy ilyen csoport első feladatát megoldjuk itt az előadáson és ennek felhasználásával javaslom a többi feladat megoldását. Könnyítésül a cikk végén megtalálhatók a feladatok végeredményei. Természetesen ezen feladatok esetében mindig járható út az, hogy kiszámolunk néhány tagot a sorozatból, megsejtjük a zárt alakot és ezt az alakot teljes indukció felhasználásával bizonyítjuk. De ez nem minden esetben járható ill. véleményem szerint általában nem járható. Ennek bizonysága, hogy ha a következő feladatokban a sorozatok elemeit kiszámoljuk, nem lehet olyan egyszerűen rájönni a zárt alakra.
Feladatok Ha más nincs megadva, akkor minden sorozat esetében a feladat: „Adjuk meg zárt alakban a következő sorozatot!”
1.
a1 = 1;
an = an −1 + 5
n ≥ 2.
2.
a1 = 1;
an = 3an −1
n ≥ 2.
3.
a1 = 1;
an = 3an −1 + 5
n ≥ 2.
4.
a1 = 1;
an = 3an −1 + n
n ≥ 2.
5.
a1 = 1;
an = 3an −1 + n + 5 n ≥ 2.
6.
a1 = 1;
an = 7 an −1 + n 2 − 3 n ≥ 2.
7.
a1 = 0; an =
212
n −1 ( an −1 + 1) n ≥ 2. n
Szoldatics József: Rekurzív sorozatok
8.
a1 = 0; an =
9.
a1 = 0; an =
n ( n − 1)
( n + 2 )( n + 1)
( an −1 + 1)
n ≥ 2.
( n + 1) n ( n − 1) a + 1 ( ) ( n + 4 )( n + 3)( n + 2 ) n −1
n ≥ 2.
2
1 1 10. a1 = A; an = 1 − an −1 + n − 1 n ≥ 2. n − 1 11. a1 = 1; an = 1 −
n −1 an −1 n
an −1
n ≥ 2.
12. a1 = 1;
1 an = 1 − 2 n
13. a1 = 1;
an = ( n − 1) an −1 + n 2 − 3n + 1 n ≥ 2.
14. a1 = 2;
an = an −1 + 4
15. a1 = 1;
an = an −1 +
16. a1 = 1;
an =
2013an −1 + 2012 2014an −1 − 2013
n≥2
a2013 = ?
17. a1 = 1;
an =
2an −1 − 4 an −−1
n≥2
a2013 = ?
18. a1 = 3;
an =
2an −1 − 1 an −1 + 1
n≥2
a2013 = ?
19. a1 = 1;
an = 9 + 6 a1 + a2 + ... + an −1
n ≥ 2.
20. a1 = 1;
an = 25 + 10 a1 + a2 + ... + an −1
n ≥ 2.
n ≥ 2.
an −1 +2 2 1
n −n 2
n ≥ 2.
n ≥ 2.
213
Kistérségi tehetséggondozás 21. a1 = 1;
an = 4 + 4 a1 + a2 + ... + an −1
n ≥ 2.
22. a1 = 1;
an =
n +1 ( a1 + a2 + ... + an −1 ) n −1
n ≥ 2.
(
1 1 + 4an −1 + 1 + 24an −1 16 Bizonyítandó: ∀ai ∈ Q
23. a1 = 1;
an =
(
1 3an −1 + 5an2−1 − 4 2 Bizonyítandó: ∀ai ∈ Z
24. a1 = 1;
an =
25. a1 = 1;
an = 3an −1 + 8an2−1 − 8
)
)
n ≥ 2.
n ≥ 2.
n ≥ 2.
Bizonyítandó: ∀ai ∈ Z 26. a1 = 2;
nan = 2 ( 2n − 1) an −1
n ≥ 2.
Bizonyítandó: ∀ai ∈ Z
Megoldások Az egyes feladattípusokból csak az első feladat kerül megoldásra, a többit hasonló módon lehet megoldani.
1. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = an −1 + 5
n ≥ 2.
Megoldás: Ez a közismert számtani sorozat, de oldjuk meg most a rekurzív módszerrel! Írjuk fel a sorozat előző elemeit is ezen a módon:
214
Szoldatics József: Rekurzív sorozatok
an = an −1 + 5 an −1 = an − 2 + 5 an − 2 = an −3 + 5 .... a3 = a2 + 5 a2 = a1 + 5 Adjuk össze az egyenleteket. Vegyük figyelembe, hogy vannak megegyező tagok a két oldalon: an + an −1 + ... + a2 = an −1 + ... + a2 + a1 + 5 ( n − 1)
an = 1 + 5 ( n − 1) = 5n − 4
2. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = 3an −1
n ≥ 2.
Megoldás Ez a közismert mértani sorozat, de oldjuk meg most a rekurzív módszerrel. Mivel az első elem nem nulla, ezért a második sem, ezért a harmadik sem, és ez így folytatódik. Írjuk fel a sorozat előző elemeit is ezen a módon:
an = 3an −1 an −1 = 3an − 2 an − 2 = 3an −3 .... a3 = 3a2 a2 = 3a1 Szorozzuk össze az egyenleteket. Ezt megtehetjük, hiszen egyik sor sem azonosan nulla. Vegyük figyelembe, hogy vannak megegyező tagok a két oldalon:
an ⋅ an −1 ⋅ ... ⋅ a2 = an −1 ⋅ ... ⋅ a2 ⋅ a1 ⋅ 3n −1 an = 3n −1 215
Kistérségi tehetséggondozás 3. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = 3an −1 + 5
n ≥ 2.
Megoldás: Itt most látszatra nem segít egyik előző módszer sem. Pedig egy egyszerű trükk 5 segít, adjuk mind a két oldalhoz -et. Hogy miért ezt és más nem lenne jó? Ez 2 majd az előadáson ki fog derülni.
an = 3an −1 + 5 5 5 15 = 3an −1 + 5 + = 3an −1 + 2 2 2 5 5 an + = 3 an −1 + 2 2 an +
Most vezessünk be egy új sorozatot a következő módon:
5 5 7 5 bn = an + ; b1 = a1 + = ; an = bn − . 2 2 2 2 Erre a sorozatra
7 , 2 bn = 3bn −1 b1 =
ami egy sima mértani sorozat, ennek a zárt alakja
bn =
216
7 n −1 3 2
Szoldatics József: Rekurzív sorozatok és most visszatérünk az eredeti sorozatra
5 7 n −1 5 = 3 − 2 2 2 7 ⋅ 3n −1 − 5 an = . 2 an = bn −
4. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = 3an −1 + n
n ≥ 2.
Megoldás: Próbáljuk az előző feladat módszerét itt is alkalmazni. Adjuk mind a két oldalhoz 1 3 n + -et. Hogy miért ezt és más nem lenne jó? Ez majd az előadáson ki fog 2 4 derülni. an = 3an −1 + n
1 3 1 3 3 9 n + = 3an −1 + n + n + = 3an −1 + ( n − 1) + 2 4 2 4 2 4 1 3 1 3 an + n + = 3 an −1 + ( n − 1) + 2 4 2 4 an +
Most vezessünk be egy új sorozatot a következő módon:
bn = an +
1 3 1 3 9 1 3 n + ; b1 = a1 + + = ; an = bn − n − . 2 4 2 4 4 2 4
Erre a sorozatra
9 , 4 bn = 3bn −1 , b1 =
217
Kistérségi tehetséggondozás ami egy sima mértani sorozat, ennek a zárt alakja
bn =
9 n −1 3 4
és most visszatérünk az eredeti sorozatra
1 3 9 1 3 n − = 3n −1 − n − 2 4 4 2 4 n −1 9 ⋅ 3 − 2n − 3 an = . 4 an = bn −
7. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 0; an =
n −1 ( an −1 + 1) n ≥ 2. n
Megoldás: Rendezzük át a sorozat képzési szabályát a következő módon:
n −1 ( an −1 + 1) n nan = ( n − 1) an −1 + ( n − 1) an =
Írjuk fel a sorozat előző elemeit is ezen a módon:
nan = ( n − 1) an −1 + ( n − 1)
( n − 1) an −1 = ( n − 2 ) an − 2 + ( n − 2 ) ( n − 2 ) an −2 = ( n − 3) an −3 + ( n − 3) .... 3a3 = 2a2 + 2 2a2 = a1 + 1
218
Szoldatics József: Rekurzív sorozatok Adjuk össze az egyenleteket. Vegyük figyelembe, hogy vannak megegyező tagok a két oldalon:
nan + ( n − 1) an −1 + ... + 2a2 = ( n − 1) an −1 + ...2a2 + a1 + ( n − 1) + ( n − 2 ) + ... + 1 nan = a1 + 1 + 2 + 3 + ... + ( n − 1) azaz
nan = a1 +
n −1
∑ i =a +
n ( n − 1)
1
i =1
2
mivel a sorozat első eleme a1 = 0 , ezért
nan =
n ( n − 1)
2 n −1 an = . 2
8. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 0; an =
n ( n − 1)
( n + 2 )( n + 1)
( an −1 + 1)
n ≥ 2.
Megoldás: Rendezzük át a sorozat képzési szabályát a következő módon:
n ( n − 1)
( a + 1) ( n + 2 )( n + 1) n −1 ( n + 2 )( n + 1) an = n ( n − 1) an−1 + n ( n − 1) an =
Szorozzuk végig mind a két oldalt ( n + 1) n -nel, ami nyilván nem nulla. Azért ezt a kifejezést választottuk, hogy a rekurziós összefüggésünkben az index léptetése után egyforma együtthatók jöjjenek létre a két oldalon.
219
Kistérségi tehetséggondozás
( n + 2 )( n + 1)2 nan = ( n + 1) n 2 ( n − 1) an −1 + n2 ( n 2 − 1) . A jobb oldal második tagját kifejtve
( n + 2 )( n + 1)2 nan = ( n + 1) n2 ( n − 1) an −1 + n4 − n2 . Írjuk fel a sorozat előző elemeit is ezen a módon:
( n + 2 )( n + 1)2 nan = ( n + 1) n2 ( n − 1) an −1 + n4 − n2 ( n + 1) n2 ( n − 1) an −1 = n ( n − 1)2 ( n − 2 ) an −2 + ( n − 1)4 − ( n − 1)2 2 2 4 2 n ( n − 1) ( n − 2 ) an − 2 = ( n − 1)( n − 2 ) ( n − 3) an −3 + ( n − 2 ) − ( n − 2 ) ..... 5 ⋅ 4 ⋅ 3a3 = 4 ⋅ 32 ⋅ 2a2 + 34 − 32 2
4 ⋅ 32 ⋅ 2a2 = 3 ⋅ 22 ⋅1a1 + 24 − 22 Adjuk össze az egyenleteket. Vegyük figyelembe, hogy vannak megegyező tagok a két oldalon: n
n
n
n
i =2
i =2
i =1
i =1
( n + 2 )( n + 1)2 nan = 12a1 + ∑ i 4 − ∑ i 2 = 12a1 + ∑ i 4 − ∑ i 2 azaz
( n + 2 )( n + 1)2 nan = 12a1 + = 12a1 + = 12a1 +
(
30
6
n ( n + 1)( 2n + 1) 3n + 3n − 1 − 1 = 6 5 2
(
n ( n + 1)( 2n + 1) 3n 2 + 3n − 6 30
mivel a sorozat első eleme a1 = 0 , ezért
220
) − n ( n + 1)( 2n + 1) =
n ( n + 1)( 2n + 1) 3n2 + 3n − 1
) = 12a + ( n + 2 )( n + 1) n ( n − 1)( 2n + 1) 1
10
Szoldatics József: Rekurzív sorozatok
( n + 2 )( n + 1)2 nan =
( n + 2 )( n + 1) n ( n − 1)( 2n + 1) 10
( n − 1)( 2n + 1) . an = 10 ( n + 1) 13. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = ( n − 1) an −1 + n 2 − 3n + 1 n ≥ 2.
Megoldás: Végezzünk egy kis átalakítást a rekurziós formulán
an = ( n − 1) an −1 + n 2 − 3n + 1 an + n = ( n − 1) an −1 + n 2 − 2n + 1 an + n = ( n − 1) an −1 + ( n − 1)
2
an + n = ( n − 1) ( an −1 + n − 1) Most vezessünk be egy új sorozatot a következő módon:
bn = an + n; b1 = a1 + 1 = 2; an = bn − n Erre a sorozatra
b1 = 2,
bn = ( n − 1) bn −1. Mivel az első elem nem nulla, ezért a második sem, ezért a harmadik sem, és ez így folytatódik.
221
Kistérségi tehetséggondozás Írjuk fel a sorozat előző elemeit is ezen a módon:
bn = ( n − 1) bn −1
bn −1 = ( n − 2 ) bn − 2
bn − 2 = ( n − 3) bn −3 .... b3 = 2b2 b2 = 1b1
Szorozzuk össze az egyenleteket. Ezt megtehetjük, hiszen egyik sor sem azonosan nulla. Vegyük figyelembe, hogy vannak megegyező tagok a két oldalon:
bn ⋅ bn −1 ⋅ ... ⋅ b2 = bn −1 ⋅ ... ⋅ b2 ⋅ b1 ⋅ ( n − 1)( n − 2 ) . ⋅ .. ⋅ 2 ⋅1 bn = 2 ⋅ ( n − 1) !
és most visszatérünk az eredeti sorozatra
an = bn − n = 2 ⋅ ( n − 1) !− n an = 2 ⋅ ( n − 1) !− n.
16. feladat Adjuk meg a sorozat 2013. elemét:
a1 = 1; an =
2013an −1 + 2012 2014an −1 − 2013
Megoldás: Számítsuk ki elemeket a sorozatból:
a1 = 1, a2 = 4025, a3 = 1.
222
n≥2
a2013 = ?
Szoldatics József: Rekurzív sorozatok Tehát egy olyan sorozattal van dolgunk, ami periodikus. Esetünkben a periódus hossza 2, ami azt jelenti, hogy minden páratlan indexű elem megegyezik, tehát a2013 = 1.
19. feladat Adjuk meg zárt alakban a következő sorozatot:
a1 = 1;
an = 9 + 6 a1 + a2 + ... + an −1
n ≥ 2.
Megoldás: A sorozat megadási módjából következik, hogy
an = 9 + 6 a1 + a2 + ... + an −1 > 9
n ≥ 2.
Most két megoldási módot is megnézünk. I. Megoldás: Írjuk fel az előző elemre is a rekurziós összefüggést:
an −1 = 9 + 6 a1 + a2 + ... + an − 2 2
an −1 − 9 = a1 + a2 + ... + an − 2 . 6 Ezt most használjuk fel az eredeti rekurziós összefüggésbe 2
a −9 an −1 + 9 an = 9 + 6 a1 + a2 + ... + an −1 = 9 + 6 n −1 + an −1 = 9 + 6 6 6 a +9 an = 9 + 6 ⋅ n −1 = an −1 + 18. 6
2
Ez egy számtani sorozat, de csak a 3. elemtől igaz az összefüggés (miért?)
an = 9 + 6 a1 + a2 + ... + an −1 > 9
n≥2
an = a2 + 18 ⋅ ( n − 2 ) = 18n − 21
223
Kistérségi tehetséggondozás A keresett összefüggés
n =1 1 an = 18 n − 21 n ≥2 II. Megoldás: Rendezzük át a rekurziós összefüggést
an = 9 + 6 a1 + a2 + ... + an −1 a1 + a2 + ... + an −1 + an = 9 + 6 a1 + a2 + ... + an −1 + a1 + a2 + ... + an −1
(
a1 + a2 + ... + an −1 + an = 3 + a1 + a2 + ... + an −1
)
2
a1 + a2 + ... + an −1 + an = 3 + a1 + a2 + ... + an −1 Most vezessünk be egy új sorozatot a következő módon:
bn = a1 + a2 + ... + an −1 + an ; b1 = a1 = 1; an = bn2 − bn2−1 Erre a sorozatra
b1 = 1, bn = bn −1 + 3. Ez egy számtani sorozat, amire bn = 1 + 3 ( n − 1) = 3n − 2 és most visszatérünk az eredeti sorozatra
an = bn2 − bn2−1 = ( 3n − 2 ) − ( 3n − 5 ) = 18n − 21. 2
2
A keresett összefüggés
1 an = 18n − 21
224
n =1 n≥2
n ≥ 2.
Szoldatics József: Rekurzív sorozatok 23. feladat Bizonyítsuk be, hogy minden elem racionális a következő sorozatban:
a1 = 1;
an =
(
1 1 + 4an −1 + 1 + 24an −1 16
)
n ≥ 2.
Megoldás: A sorozat megadási módjából következik, hogy an >
1 > 0 n ≥ 2. 16
Most is két megoldási módot is megnézünk. I. Megoldás: Ha valamelyik elem racionális a sorozatban, akkor a következő elem racionalitása csak a gyökös kifejezésen múlik. Tehát, ha be tudjuk látni, hogy a gyökös kifejezések racionalitása öröklődik, akkor a sorozat minden eleme racionális lesz. Rendezzük át a rekurziós összefüggést
(
)
1 1 + 4an −1 + 1 + 24an −1 16 3 3 24an = + 6an −1 + 24an −1 + 1 2 2 5 3 24an + 1 = + 6an −1 + 24an −1 + 1 2 2 an =
3 1 24an + 1 = + 24an −1 + 1 2 2 3 1 24an + 1 = + 24an −1 + 1 2 2 Ez utóbbi azt mondja, hogy ha egyszer a következő megfelelő kifejezés, azaz a
2
24ai −1 + 1 kifejezés racionális, akkor 24ai + 1 is racionális. Az első elemre
24a1 + 1 = 5 racionális, tehát akkor minden elem a sorozatban racionális.
225
Kistérségi tehetséggondozás II. Megoldás: Megadjuk a sorozat zárt alakját, ami bizonyítani fogja a racionalitást. Rendezzük át a rekurziós összefüggést
an =
(
1 1 + 4an −1 + 1 + 24an −1 16
(
96an = 6 1 + 4an −1 + 1 + 24an −1
)
)
96an + 4 = 10 + 24an −1 + 6 1 + 24an −1
(
4 ( 24an + 1) = 3 + 1 + 24an −1
)
2
2 24an + 1 = 24an −1 + 1 + 3 2 24an + 1 − 6 = 24an −1 + 1 − 3
2
(
)
24an + 1 − 3 = 24an −1 + 1 − 3
Most vezessünk be egy új sorozatot a következő módon:
bn = 24an + 1 − 3; b1 = 24a1 + 1 − 3 = 2; an = Erre a sorozatra
b1 = 2, 2bn = bn −1 , bn =
1 bn −1 . 2
Ez egy mértani sorozat, aminek az összefüggése:
1 bn = 2 2
226
n −1
=
4 2n
.
1 1 2 ( bn + 3) − . 24 24
Szoldatics József: Rekurzív sorozatok és most visszatérünk az eredeti sorozatra 2
1 4 1 1 16 24 2 1 1 1 + 3 − = + n + 9 − = + n+ , n 2n 2n 24 2 3 2 2 24 24 2 24 3 ⋅ 2 2 1 1 an = + + . 3 ⋅ 22n 2n 3 an =
Ez pedig egy racionális kifejezés.
Hasznos/szükséges összefüggések a megoldásokhoz n
∑i =
n ( n + 1)
i =1 n
∑
i2 =
2
∑
i = 3
∑
i4 =
n 2 ( n + 1)
2
=
2
∑i
5
=
∑
i6 =
n 2 ( n + 1)
2
∑i
=
∑
i8 =
2
) = 2n
+ 2n − 1
6
5
+ 15n 4 + 10n3 − n 30
+ 6 n5 + 5n 3 − n 2 12
(
) = 6n
n ( n + 1)( 2n + 1) 3n 4 + 6n3 − 3n + 1 42
(
n 2 ( n + 1) 3n 4 + 6n3 − n 2 − 4n + 2 24
i =1 n
( 2n 12
2
7
) = 6n
30
i =1 n
n 4 + 2n3 + n 2 4
(
i =1 n
2n2 + 3n 2 + n 6
n ( n + 1)( 2n + 1) 3n2 + 3n − 1
i =1 n
=
6
i =1
n
n2 + n 2
n ( n + 1)( 2n + 1)
i =1 n
=
) = 3n
7
+ 21n6 + 21n5 − 7n3 + n 42
8
+ 12n7 + 14n6 − 7 n 4 + 2n 2 24
(
n ( n + 1)( 2n + 1) 5n6 + 15n5 + 5n 4 − 15n3 − n 2 + 9n − 3 90
i =1
=
)=
10n9 + 45n8 + 60n7 − 42n5 + 20n3 − 3n 90
227
Kistérségi tehetséggondozás n
∑i
9
=
n 2 ( n + 1)
2
(n
2
)(
+ n − 1 2n4 + 4n3 − n 2 − 3n + 3 20
i =1
=
)=
2n + 10n + 15n − 14n6 + 10n4 − 3n2 20 10
9
8
Végeredmények A feladatok végeredményei a következők: 1.
an = 1 + 5 ( n − 1) = 5n − 4
2.
an = 3n −1
3.
an =
4.
an
5.
an
6.
an
7.
an
8.
an
7 ⋅ 3n −1 − 5 2 n −1 9 ⋅ 3 − 2n − 3 = 4 19 ⋅ 3n −1 − 2n − 13 = 4 n −1 71 ⋅ 7 − 9n 2 − 21n + 13 = 54 n −1 = 2 ( n − 1)( 2n + 1) = 10 ( n + 1)
9.
an = =
n10 + 15n9 + 90n8 + 270n7 + 393n6 + 135n5 − 340n 4 − 420n3 − 144n 2
( n − 1) n 10 ( n + 2 )
A 10. an = n 2 ( n − 1)
228
10 ( n + 4 )( n + 3)
n =1 n≥2
2
( n + 2 )3 ( n + 1)2 n
=
Szoldatics József: Rekurzív sorozatok
1 n = 2k 2 11. an = n +1 n = 2k + 1 2n n +1 12. an = 2n 13. an = 2 ⋅ ( n − 1) !− n 14. an = 2n 2
2n − 1 n 16. a2013 = 1 17. a2013 = 4
15. an =
18. a2013 =
2 3
n =1 1 19. an = 18n − 21 n ≥ 2 n =1 1 20. an = 8n − 8 n ≥ 2 n =1 1 21. an = 50n − 65 n ≥ 2 22. an = ( n + 1) 2n − 2 23. an =
2
+
1
3⋅ 2 2 24. an = 3an −1 − an − 2 2n
n
+
1 3
25. an = 6an −1 − an − 2 26. an =
2n ⋅1⋅ 3 ⋅ 5 ⋅ ... ⋅ ( 2n − 1) n!
=
( 2n ) !
2n = n !⋅ n ! n
229
