Mathematics | Mathematical analysis » Szilágyi Judit - Rekurzív sorozatok

Rekurzı́v sorozatok Szilágyi Judit Babeş-Bolyai Tudományegyetem Oktatói matematika szak Kolozsvár, 2009 januárja Tartalomjegyzék 1. Általános fogalmak 1.1 Néhány ismert rekurzió 1.2 A rekurziók osztályozása 1.3 Rekurzı́v sorozatok általános tagjának meghatározása 1.31 Indukcióval megoldható rekurens sorozatok 1.32 Lineáris rekurenciák megoldása 2 2 3 4 4 6 2. A rekurzı́v sorozatok néhány alkalmazása 2.1 Közelı́tések 2.11 A π közelı́tése 2.12 Newton módszere 2.13 Tetszőleges függvény függvényértékének közelı́tése 2.2 Rekurzı́v számlálások 2.21 Algebra és számelmélet körébe tartozó problémák 2.22 Kombinatorikus

geometria körébe tartozó problémák 10 10 10 11 11 12 12 14 1 1. Általános fogalmak A természetes számok halmazán gyakran értelmezünk olyan függvényeket, amelyeknek az n helyen felvett értékei az 1, 2, . , (n − 1) helyeken felvett értékeitől, vagy ezek közül némelyektől függenek. Ezeket a függvényeket rekurzı́v sorozatoknak nevezzük A sorozat bizonyos számú kezdőtagját természetesen meg kell adni, mert csak ı́gy határozhatjuk meg a következő tagokat. A megadott kezdőtagok száma attól függ, hogy a rekurzió a sorozat egy tagját hány előző tag függvényeként adja meg. A rekurzió az az egyértelmű utası́tás, amellyel a sorozat tagjait az előző tagok segı́tségével fejezzük ki (pl. an+1 = a2n − 2an + 5, ∀n ≥ 1, a0 = a1 = 1) A sorozat explicit alakjának megadása azt jelenti, hogy a sorozat általános tagját n függvényeként fejezzük ki

(például ln = nn−2 2 +1 , ∀n ∈ N). Az explicit alakban megadott sorozat sokkal könnyebben kezelhető, ezért általában a rekurzı́v sorozat explicit alakjának meghatározására törekszünk. Az általános tag megadását a rekurzió megoldásának nevezzük. Természetesen ez nagyon sok esetben nem lehetséges, vagy igen bonyolult technikákat igényel, de a sorozat különböző tulajdonságainak vizsgálata a rekurzió megoldása nélkül is lehetséges. 1.1 Néhány ismert rekurzió a) A Hanoi tornyok problémáját Eduard Lucas francia matematikus terjesztette el 1993-ban. A feladat elsőrendű lineáris rekurenciához vezet A következő történetet fűzték hozzá: Indiában, egy Siva-templom közepén volt egy márványtábla, és ebből három márványtű állt ki. Az első tűre 64 aranykorongot helyeztek, alul a legnagyobb átmérőjűt, fölé egyre kisebbeket. Siva azt parancsolta

a templom papjainak, hogy helyezzék át a korongokat az első tűről a másodikra. Az áthelyezéshez a harmadik korongot is használhatják, de mivel a korongok sérülékenyek egyszerre csak egyet lehet mozgatni, és mivel szent korongok csak kisebb átmérőjű kerülhet nagyobb átmérőjű fölé. Amikor az utolsó korong is a helyére kerül, a világ véget ér. Vizsgáljuk meg, mikor következhet ez be. Nyilván, arra a kérdésre kellene válaszolnunk, hány lépésben lehet átjuttatni a 64 korongot. Ha Hn -nel jelöljük az n korong esetén szükséges lépések számát, akkor H1 = 1, H2 = 3. Ha n korong áthelyezését vizsgáljuk, az áthelyezés során biztosan lesz egy olyan lépés, amikor a legnagyobb korong átkerül az első tűről a másodikra. Ekkor a második tűn más korong nem lehet, az elsőn sem, tehát az összes többi a harmadik tűn van, a szabályok miatt nagyság szerinti

sorrendben. Ettől kezdve egy újabb tornyot kaptam, mely n − 1 korongból áll, most ezeket kell áthelyezni. Tehát áthelyeztünk n − 1 korongot nagyságsorrendben, aztán áthelyeztük az n-ediket, most pedig ismét át kell helyezni n − 1-et. Így a Hn = Hn−1 + 1 + Hn−1 = 2Hn−1 + 1 rekurzióhoz jutunk b) Az egyik legnépszerűbb, legrégibb példa másodrendű lineáris rekurenciára a Fibonacci-sorozat. A sorozat Leonardo Pisano (Fibonacci) olasz matematikus nevéhez kötődik, a probléma Liber Abaci (Az abakusz könyve) cı́mű művében jelent meg, és egy nyúltenyészet elméleti növekedését mutatja be. A Fibonacci-sorozat a következő problémából keletkezett: Egy tenyészetben kezdetben egy nyúlpár van. A nyulak születésüktől kezdve a második hónapban válnak nemzőképessé 2 és ettől kezdve minden hónapban egy újabb nyúlpárt nemzenek és a vizsgált időszakban egyetlen

nyúl sem pusztul el. Hány nyúlpárunk lesz n hónap után? Induláskor 1 nyúlpár van, tehát F0 = 1. Az első hónapban még mindig ugyanennyi, azaz F1 = 1. A második hónapban már F2 = 2 Ha Fn -nel jelöljük az n-edik hónapban a tenyészetben létező nyúlpárok számát, vizsgáljuk meg hány nyúlpárunk lesz az (n+1)-edik hónapban. Az n-edik hónapban meglevő nyulak közül (ezek száma Fn ) az (n − 1)-edik hónapban meglévőek (ezek száma Fn−1 ) már nemzőképesek, ı́gy ezek Fn−1 új nyúlpárt nemzenek. Ezt az Fn+1 = Fn + Fn−1 rekurzióval ı́rhatjuk le c) A Catalan számok sorozata Egy n-oldalú sokszög átlók segı́tségével való háromszögekre bontása vezet el, többek közt, a Catalan-számokhoz. A sokszöget átlói segı́tségével többféleképpen lehet diszjunkt belsejű háromszögekre bontani. Ha cn -nel jelöljük a lehetséges felbontások számát, akkor a

cn sorozat esetén c2 = c3 = 1 és c4 = 2. Ha a sokszög csúcsait A1 , A2 , , An -nel jelöljük, ekkor n ≥ 3 esetén az A1 An oldal pontosan egy háromszög oldala lesz a felbontásban. Ha a háromszög harmadik csúcsa Ak , akkor az A1 An Ak háromszög egyik oldalán egy k oldalú sokszög, a másik oldalán egy (n+1−k) oldalú sokszög keletkezik. Ezek felbontása ck , illetve cn+1−k -féleképpen történhet. Nyilván az A1 An oldallal szemközti csúcs a felbontásban lehet A2 , A3 , . , An−1 csúcs, ı́gy a cn = c2 · cn−1 + c3 · cn−2 + + cn−1 · c2 rekurenciát kapjuk. A1 A2 An n+1-k szög k - szög Ak 1.2 A rekurziók osztályozása A rekurziók, különböző szempontokat figyelembe véve, többféleképpen osztályozhatók: a) aszerint, hogy a rekurencia reláció hány előző tag függvényében ad meg egy tagot, lehet első-, másod-, harmadrendű, stb. Például: a0 = 1, a2 = 1,

a3 = 2, an+1 = 3an − 2an−1 + an−2 harmadrendű rekurencia b) aszerint, hogy a tagot az előző tagok lineáris függvényeként adja-e meg, lehet lineáris vagy nemlineáris rekurencia. Például: a0 = 1, a1 = 1, an+1 = 5an + an−1 lineáris (másodrendű) rekurencia, mı́g a1 = 2, an = 3a2n − 1 nem lineáris (elsőrendű) rekurencia c) aszerint, hogy az an -et megadó függvényben az ai -k együtthatói állandóak, vagy n-tol függőek, lehet állandó együtthatós vagy nem. Például: an = 7an−1 + a2n−1 − 3 állandó együtthatós rekurencia, mı́g an = n · an−1 − 1 nem állandó együtthatós rekurencia 3 1.3 Rekurzı́v sorozatok általános tagjának meghatározása 1.31 Indukcióval megoldható rekurens sorozatok Igen gyakori, hogy a rekurens sorozat első néhány tagját felı́rva megsejtjük a sorozat általános tagját megadó formulát, majd ezt matematikai indukcióval

igazolhatjuk. Természetesen eközben különböző számolási technikák alkalmazása is szükséges lehet. 1.1 Feladat Az (xn )n∈N∗ sorozat teljesı́ti az x1 = 2, xn+1 = x3n , ∀n ∈ N∗ összefüggéseket. Határozzuk meg a sorozat általános tagját Megoldás: Kiszámı́tunk néhány tagot. 1 x2 = 2 3 = 2 3 3 2 x3 = (23 ) = 29 = 23 3 3 x4 = (29 ) = 227 = 23 n−1 Azt sejtjük, hogy xn = 23 , ∀n ∈ N, ami n ∈ {0, 1, 2, 3, 4}-re nyilván igaz. Ha xk = ³ ´3 k 3 k−1 3 3 k−1 2 , akkor xk+1 = xk = 2 = 23 és az összefüggés k + 1-re is igaz. A matematikai n−1 indukció elve alapján xn = 23 , ∀n ∈ N∗ . √ 1.2 Feladat Határozzuk meg az a1 = 1, an = 4 + 4 · a1 + a2 + + an−1 sorozat 2008 tagját. Megoldás: Kiszámı́tunk néhány tagot. a2 = 8 = 8 · 1 a3 = 4 + 4 · 3 = 16 = 8 · 2 a4 = 4 + 4 · 5 = 24 = 8 · 3 a5 = 4 + 4 · 6 = 32 = 8 · 4 Észrevesszük, hogy ezekre az értékekre an = 8(n − 1).

Igazoljuk, hogy ez az összefüggés ∀n ∈ N∗ {1} esetén igaz. √ Ha feltesszük, hogy ai = 8(i − 1), ∀i = 2, k,pakkor ak+1 = 4 + 4 a1 + p √ a2 + . + ak = = 4 + 4 1 + 8[1 + 2 + . + (k − 1)] = 4 + 4 1 + 4(k − 1)k = 4 + 4 4k 2 − 4k + 1 = = 4 + 4(2k − 1) = 8k, tehát az összefüggés (k + 1)-re is igaz. a2008 = 8 · 2007 = 1656. 1.3 Feladat Határozzuk meg az an+1 = rekurziót teljesı́tő sorozat általános tagját. (2n − 1)an − (2n + 1) , ∀n ∈ N, a0 = −1 (2n + 1)an − (2n + 3) 4 15 12 35 3 −1 , a1 = 0, a2 = , a3 = , a4 = , a5 = , a6 = . 1 5 5 17 13 37 Észrevehető, hogy a páros indexű tagokban a számláló és a nevező különbsége 2, és a n2 − 1 . köztük levő szám az index négyzete, tehát páros n-re: an = 2 n +1 8 0 Ha a páratlan indexű tagokat bővı́tjük kettővel, akkor azt kapjuk, hogy a0 = , a3 = , 2 10 24 a5 = , és a fenti képlet ezekre is érvényes. 26 k2 − 1 (2k −

1)ak − (2k + 1) Ha feltételezzük, hogy ak = = , akkor ak+1 = 2 k +1 (2k + 1)ak − (2k + 3) Megoldás: a0 = 4 k2 − 1 − (2k + 1) 2+1 (2k − 1)(k 2 − 1) − (2k + 1)(k 2 + 1) k 2 + 2k k = = = = k2 − 1 (2k + 1)(k 2 − 1) − (2k + 3)(k 2 + 1) k 2 + 2k + 2 (2k + 1) · 2 − (2k + 3) k +1 (k + 1)2 − 1 , ahol k ∈ N∗ rögzı́tett szám. = (k + 2)2 − 1 n2 − 1 Tehát indukcióval igazoltuk, hogy an = 2 , ∀n ∈ N esetén. n +1 (2k − 1) · 1.4 Feladat Az (an )n∈N∗ sorozatot a következőképpen értelmezzük: a1 = 1, an = n+1 (a1 + a2 + . + an−1 ), ∀n ∈ N∗ Határozzuk meg a2005 értékét n−1 Megoldás: a1 = 1, a2 = 3 = 3 · 1 = 3 · 20 , a3 = 8 = 4 · 2 = 4 · 21 , a4 = 20 = 5 · 4 = 5 · 22 , a5 = 48 = 6 · 8 = 6 · 23 1 n ∈ {2, 3, 4, 5}-re igaz az an = (n + 1) · 2n−2 összefüggés. Sőt, ha a1 = 2 · -et ı́runk, akkor 2 ez n = 1-re is igaz. 1, k-ra. A sorozatot Feltételezzük, hogy az összefüggés igaz

∀i = k+2 k+2 (a1 + a2 + . + ak ) = · megadó rekurzió értelmében ak+1 = k k £ ¤ 2 · 2−1 + 3 · 20 + 4 · 21 + . + (n + 1) · 2n−2 k X Ki kell számı́tanunk az S = (i + 1) · 2i−2 összeget. £ i=1 ¤ S = £2S − S = 2 · 20 + 3 · 21 + 4 · 22 + . + k · 2¤k−2 + (k + 1) · 2k−1 − − 2 · 2−1¡ + 3 · 20 + 4 · 21 + . ¢ + (k + 1) · 2k−2 = = −1 − ¡20 + 21 +¢ . + 2k−2 + (k + 1) · 2k−1 = = −1 − 2k−1 − 1 + (k + 1) · 2k−1 = k · 2k−1 . Tehát an = (n + 1) · 2n−1 , ∀n ∈ N∗ , ı́gy a2005 = a2006 · 22003 . a a2n és an+1 = 2 , ∀n ≥ 2 sorozat. a−2 an − 2an + 2 Határozzuk meg a sorozat általános tagját. 1.5 Feladat Adott az a1 = a 6= 2, a2 = Megoldás: A rekurencia reláció mindkét oldalának inverzét felı́rva az 1 = 1− 2 2 + 2 an an an+1 1 elnevezéssel a bn+1 = 2b2n − 2bn + 1 ⇐⇒ 2bn+1 − 1 = összefüggést kapjuk, ami a bn = an 4b2n − 4bn + 1 = (2bn − 1)2

összefüggéshez vezet. Az xn+1 = x2n rekurenciát teljesı́tő sorozatra: x2 = x21 , x3 = x41 ; x4 = x81 , és sejtésünk, ³ ´2 n−1 k−1 k−1 k hogy xn = x12 . Valóban, ha xk = x21 , akkor xk+1 = x2k = x21 = x21 , k ∈ N∗ . ¶2n−1 µ 2 2 2n−1 −1= −1 Tehát 2bn − 1 = (2b1 − 1) , ahonnan és an a n−1 2 · a2 . an = (2 − a)2n−1 + a2n−1 5 1.32 Lineáris rekurenciák megoldása A. Elsőrendű lineáris rekurenciák 1. Az an = b · an−1 + c, ∀n ≥ 2, a1 = a sorozatot meghatározó rekurziót elsőrendű, állandó együtthatós lineáris rekurenciának nevezzük. Ezt a következőképpen oldjuk meg: felı́rjuk az összefüggéseket x = 2, n-re, majd az utolsótól kezdve rendre beszorozzuk b növekvő hatványaival és az egyenlőségek megfelelő oldalait összeadjuk: a2 = ba1 + c a3 = ba2 + c a4 = ba3 + c . . | ·bn−2 | ·bn−3 | ·bn−4 an−1 = b · an−2 + c | ·b1 an = b · an−1 + c |

·b0 an = bn−1 · a1 + c (1 + b + b2 + . + bn−2 ) = bn−1 · a1 + c · A sorozat általános tagja: an = bn−1 · a1 + c · bn−1 − 1 . b−1 bn−1 − 1 , ∀n ∈ N∗ . b−1 2. Az an = b · an−1 + cn , ∀n ≥ 2, a1 = a sorozatot meghatározó rekurziót elsőrendű, nem állandó együtthatós lineáris rekurenciának nevezzük. A rekurzió megoldása: Egy ilyen rekurzióhoz hozzárendelhetünk egy homogén rekurziót úgy, hogy elhagyjuk a cn -et az összefüggésből. Ha hn -nel jelöljük ennek a megoldását, akkor (hn )n∈N∗ teljesı́ti a hn = bn · hn−1 összefüggést. Felı́rjuk a relációt k = 2, n-re, majd összeszorozzuk az egyenlőségek megfelelő oldalait. h2 = b2 · h1 h3 = b3 · h2 h4 = b4 · h3 . . hn = bn · hn−1 hn = h1 · (b2 · b3 · . · bn ) bn an = · an−1 + Ezután az eredeti rekurencia megfelelő oldalait hn -nel osztjuk, ı́gy az hn hn cn an−1 an−1 cn cn an + == = + -et, akkor

az összefüggést kapjuk. Ha xn -nel jelöljük hn hn an hn−1 hn hn bn cn rekurencia adja meg. Ha felı́rjuk az összefüggéseket (xn )n∈N∗ sorozatot az xn = xn−1 + hn n X ck a1 · összefüggést kapjuk, ı́gy an = k = 2, n-re és összeadjuk oket, az xn = x1 + hk h1 k=2 n X ck ∀n ≥ 2-re. hn + hn hk k=2 6 B. Másodrendű, lineáris, homogén rekurenciák Az xn+1 = axn + bxn−1 (1) (b 6= 0), ∀n ≥ 1 alakú rekurenciákat másodrendű, lineáris, homogén rekurenciáknak nevezzük. Az általános tag meghatározása: A megoldásokat q n , q 6= 0 alakban keressük. Ekkor teljesülnie kell a q n+1 = a · q n + b · q n−1 ⇐⇒ q 2 − aq − b = 0 egyenlőségnek. Az x2 − ax − b = 0 (2) egyenletet a rekurzió karakterisztikus egyenletének nevezzük. a) Ha q1 6= q2 az egyenlet különböző valós gyökei, igazoljuk, hogy az (1)-es rekurzió megoldása az xn = α · q1n + β · q2n , n ∈ N sorozat, ahol α-t

és β-t a kezdeti feltételekből határozzuk meg. Bizonyı́tás. Előbb igazoljuk, hogy bármely xn = α · q1n + β · q2n sorozat kielégı́ti az (1)-es rekurenciát. ¡ ¢ n+1 αq + β · q2n+1 = aα · q1n + aβ · q2n + bα · q1n + bβ · q2n ⇐⇒ α q1n+1 − aq1n − bq1n−1 + 1 ¡ n+1 ¢ +β q2 − aq2n − bq2n−1 = 0 ⇐⇒ αq1n−1 (q12 − aq1 − b) + βq2n−1 (q22 − aq2 − b) = 0 igaz, mivel q1,2 az x2 − ax − b = 0 egyenlet gyökei. Másrészt bizonyı́tanunk kell, hogy bármely olyan (xn )n∈N∗ sorozat, amely kielégı́ti az (1)-es rekurenciát, felı́rható xn = αq1n + βq2n alakban. Ha (xn )n∈N megoldása az (1)-es rekurziónak, akkor x0 = α + β, x1 = αq1 + βq2 . A két egyenlőségből kifejezzük α és β x1 − x0 q 2 x0 q 1 − x1 , illetve a β = értékeket kapjuk. Ezek szerint x0 értékeit. Így az α = q2 − q1 q1 − q2 és x1 felı́rható αq10 + βq20 , illetve αq11 + βq21 alakban.

Indukcióval igazoljuk, hogy bármely n ∈ N -re xn = αq1n + βq2n alakban ı́rható. 1, n, akkor ¢xn+1 = axn +bxn+1 = aαq1n +aβq2n +bαq1n−1 + Ha az állı́tás igaz bármely k= ¡ ¢ ¡ +bβq2n−1 = α aq1n + bq1n−1 + β aq2n + bq2n−1 = αq1n+1 + βq2n+1 . b) Ha a karakterisztikus egyenletnek egybeeső gyökei vannak: q1 = q2 = q, akkor xn = (α + βn)q n , ∀n ∈ N, ahol α és β-t a kezdeti feltételekből fejezzük ki. c) Ha a karakterisztikus egyenlet gyökei a q1 = r(cos ϕ+i sin ϕ) és q2 = r(cos ϕ−i sin ϕ) komplex számok, akkor az (1)-es rekurzió megoldása az xn = rn (α cos nϕ + β sin nϕ), ∀n ∈ N, ahol α és β-t a kezdeti feltételekből határozzuk meg. A bizonyı́tások az a) esethez hasonló módon végezhetők el. A következőkben néhány olyan feladatot vizsgálunk meg, amelyek megoldása másodrendű lineáris rekurencia megoldására vezetődik vissza. 1.6 Feladat Határozzuk meg az x1 = 1, x21

+ x22 + + x2n = xn · xn+1 , ∀n ∈ N∗ rekurziót teljesı́tő sorozatot. Megoldás: n = 1-re: x21 = x1 · x2 ⇐⇒ x2 = 1. Ha az összefüggést felı́rjuk (n + 1)-re és az eredeti relációt kivonjuk belőle: ¯ x21 + x22 + . + x2n + x2n+1 = xn+1 · xn+2 ¯¯ − az xn+1 · xn+2 − xn · xn+1 = x2n+1 = xn · xn+1 ¯ x21 + x22 + . + x2n egyenlőséghez jutunk, és mivel xn+1 6= 0 a rekurencia alapján, ezt xn+1 -gyel elosztva az xn+2 = xn+1 + xn , ∀n ≥ 1, x1 = x2 = 1 rekurziót kapjuk, ami a Fibonacci-sorozatot √ 5 1 ± . ı́rja le. Karakterisztikus egyenlete: x2 − x − 1 = 0, melynek gyökei x1,2 = 2 7 à √ !n √ !n 1− 5 1+ 5 +B· alakban ı́rható, ahol A és B az Az általános tag xn = A · 2 2  à à √ ! √ !  1− 5 1+ 5   +B· = x1 = 1 A·    2 2 egyenletrendszer megoldásai. à à √ !2 √ !2   1 − 5 5 + 1   +B· = x2 = 1   A· 2 2 √ √ 5 5 ,B=− értékeket kapjuk,

ı́gy A rendszert megoldva az A = 5 5 √ !n # √ !n à √ "à 1+ 5 1− 5 5 − . xn = 5 2 2 à 1.7 Feladat Az (xn )n∈N sorozat teljesı́ti az x0 = 2, x1 = ∀n ≥ 2 rekurziót. Határozzuk meg [xn ]-et, n ∈ N∗ ¡ ¢ 5 5 és xn = xn−1 · x2n−2 − 2 − , 2 2 Megoldás: Az első tagok: x0 = 2 = 1 + 1 = 20 + 2−0 , 1 5 x1 = = 2 + = 21 + 2−1 , 2 2 5 5 5 x2 = (4 − 2) − = = 21 + 2−1 , 2µ 2 ¶2 5 65 5 25 1 −2 − = = 8 + = 23 + 2−3 , x3 = 2 µ4 8 8 ¶ 2 5 1025 1 65 25 −2 − = = 32 + = 25 + 2−5 . x4 = 64 4 2 32 32 Indukcióval igazoljuk, hogy létezik olyan (bn )n∈N∗ sorozat, amelyre xn = 2bn + 2−bn . n ∈ {0, 1, 2, 3, 4}-re a fenti felbontások alapján igaz. Feltételezzük, hogy állı́tásunk igaz bármely i = 1, k esetén és igazoljuk, hogy (k+1)-re is igaz. A rekurziós összefüggés alapján i 5 ¢ h¡ ¢2 ¡ 5 ⇐⇒ xk+1 = 2bk + 2−bk · 2bk−1 + 2−bk−1 − 2 − ⇐⇒ xk+1 = xk · (x2k−1 − 2) −

2 2 ¶ µ ¡ b ¢ ¡ ¢ 1 ⇐⇒ xk+1 = 2 k + 2−bk · 22bk−1 + 2−2bk−1 − 2+ ⇐⇒ 2 xk+1 = 2bk +2bk−1 + 2−bk −2bk−1 + +2bk −2bk−1 + 2−bk +2bk−1 − 2 − 2−1 , = a 2bk+1 + 2−bk+1 + 2−bk+1 alakban ı́rható, ami, ha xk+1 = 2bk+1 ¡ ¢ bk +2bk−1 −bk −2bk−1 bk −2bk−1 −bk +2bk−1 −1 = 2 +2 + 2 −2+2 −2 egyenlőséggel egyenértékű, és ez fennáll, ha bk+1 = bk + 2bk−1 és bk − 2bk−1 = ±1. A (bn ) sorozat tehát teljesı́ti a bn+1 = bn + 2bn+1 rekurziót, amelynek karakterisztikus egyenlete x2 −x−2 = 0 és az egyenlet gyökei: x1 = −1, x2 = 2. A sorozatot bn = A·(−1)n + ½ A + B = b0 = 0 B · 2n , b0 = 0, b1 = 1 összefüggések adják meg. Ha megoldjuk az −A + 2B = b1 = 1 1 1 1 n egyenletrendszert az A = − , B = értékeket kapjuk, ı́gy bn = (2 − (−1)n ). 3 3 3 Ellenőrizzük, hogy az ı́gy kapott sorozat teljesı́ti a bn − 2bn−1 = 1 rekurziót: 8 ¡ ¢¤ 1 £ n · 2 −

(−1)n − 2 2n−1 − (−1)n−1 = 3 ¤ 1 £ n = · 2 − (−1)n − 2n + 2 · (−1)n−1 = 3 (−1)n−1 · (2 + 1) = (−1)n−1 = ±1 = 3 bn − 2bn−1 = Tehát találtunk olyan (bn )n∈N∗ sorozatot, amelyre xn = 2bn + 2−bn . Így xn = 2 2n −(−1)n 3 +2 −2n +(−1)n 3 , ∀n ∈ N∗ . C. Másodrendű, lineáris, inhomogén rekurenciák Az an+1 = a · an + b · an−1 + c, b, c 6= 0 tı́pusú rekurenciákat másodrendű, lineáris, inhomogén rekurenciáknak nevezzük. Akárcsak az elsőrendűeket, úgy oldjuk meg őket, hogy homogén rekurenciákra vezetjük vissza. Ha rn -nel jelöljük az an − an−1 sorozatot, felı́rjuk az összefüggéseket n − 1 és n-re, ¯ majd megfelelő oldalukat kivonjuk egymásból: ¯ an+1 = a · an + b · an−1 + c ¯ − az rn+1 = arn + brn−1 homogén an = a · an−1 + b · an−2 + c ¯ rekurenciához jutunk, ezt karakterisztikus egyenlet segı́tségével megoldjuk, majd az 

 an − an−1 = rn    an−1 − an−2 = rn−1 összefüggéseket összegezve az an = a0 + (r1 + r2 + . + rn ) .  .    a −a =r 1 0 1 összefüggést kapjuk. Megjegyzés: A rekurziót úgy is visszavezethetjük lineáris rekurzióra, ha an+1 + d = c , a · (an + d) + b(an−1 + d) alakban próbáljuk felı́rni. Innen c + d = ad + bd, és d = a+b−1 ı́gy ez az eljárás a + b 6= 1-re alkalmazható. 1.8 Feladat Határozzuk meg az xn+1 = 6xn −9xn−1 +4, x0 = 3, x1 = 4 rekurzió sorozat általános tagját. Megoldás: Az xn = yn − d jelöléssel az yn+1 − d = 6yn − 6d − 9yn−1 + 9d + 4 ⇐⇒ yn+1 − 6yn + 9yn−1 − 4d − 4 = 0 összefüggést kapjuk, ami d = −1-re az yn+1 − 6yn + 9yn−1 = 0 homogén rekurenciát adja. Karakterisztikus ½egyenlete: q 2 − 6q + 9 = 0, melynek gyökei q1 = q2 = 3. Így yn = y0 = A = 2 (A + nB) · 3n és , ahonnan A = 2 és B = −1 és yn = (2 − n) · 3n , y1 =

(A + B) · 3 = 3 ahonnan xn = yn + 1 = (2 − n) · 3n + 1, ∀n ∈ N. 9 2. A rekurzı́v sorozatok néhány alkalmazása 2.1 Közelı́tések 2.11 A π közelı́tése Igazoljuk, hogy ha egy egységsugarú körbe és a kör köré egyre több oldalú szabályos sokszögeket ı́runk, ezek kerülete 2π-hez közeledik. Jelöljük a körbe ı́rt szabályos n-szög kerületét kn -nel, a köréı́rt n-szögét pedig Kn -nel. Ekkor kn = n · Bi Bi+1 = 2n sin Ugyanakkor 1 1 1 + = · kn K n 2n = Tehát µ 1 1 α + sin 2 tg α2 ¶ α 2 és Kn = n · Ai Ai+1 = 2ntg 1 = · 2n µ cos α2 1 + sin α2 sin α2 2 cos2 α4 1 2 1 1 · · α = , α = α 2n 2 sin 4 cos 4 2n tg 2 K2n 2 + K1n kn ⇒ K2n = 1 ¶ α 2 1 1 + cos α2 = = · 2n sin α2 mivel K2n = 4ntg α 4 K2n ≤ Kn , (1) hiszen a harmonikus közép kisebb vagy egyenlő a nagyobbik számnál. Ugyanakkor s r p sin α4 α α α α α = k2n kn · K2n = 2n sin · 4ntg = 4n

sin cos · 4n α = 4n · sin 2 4 4 4 cos 2 4 tehát kn ≤ k2n ≤ K2n . (2) Az (1) és a (2) összefüggések alapján kn ≤ k2n ≤ K2n ≤ Kn , ∀n ≥ 3 esetén, tehát k3 ≤ k6 ≤ k12 ≤ k24 ≤ · · · ≤ k3·2n ≤ K3·2n ≤ · · · ≤ K24 ≤ K12 ≤ K6 ≤ K3 , azaz a (k3·2n ) sorozat növekvő és felülről korlátos, a (K3·2n ) sorozat pedig csökkenő és alulról korlátos. A (k3·2n ) és a (K3·2n ) sorozatok közös határértéke a 2π szám Tehát az 21 k3·2n és az 21 K3·2n értékek n = 1, 2, 3, . -re egyre inkább megközelı́tik a π értékét. 10 2.12 Newton módszere ³ ´ Tekintsük az x1 = 2, xn+1 = 21 xn + x5n sorozatot. ³ ´ √ √ √ x1 = 2 < 5 ⇒ x51 > 5 ⇒ x2 = 21 x1 + x51 ∈ (x1 , x51 ) közelebb került a 5-höz. ³ ´ √ √ 5 5 1 Hasonlóan x2 = 2, 25 > 5 ⇒ x2 < 5 ⇒ x3 = 2 x2 + x2 ∈ (x2 , x52 ) közelebb került √ a 5-höz. x3 = 2, 2361 . x4 = 2,

2360679779 . x5 = 2, 2360679774 . x6 már 16 pontos számjegyet tartalmaz a tizedesvessző után. Ezzel a módszerrel bármely a pozitı́v szám négyzetgyökének közelı́tő értékét ki lehet számı́tani. ³ ´ √ Legyen x1 > 0 és xn+1 = 21 xn + xan . Az (xn )n∈N∗ sorozat konvergens és határértéke a Bizonyı́tás: Mivel x1 > 0´ és a > 0, azonnal belátható, hogy xn > 0, ∀n ∈ N∗ . ³ a , alkalmazzuk a számtani és mértani közepek közötti Mivel xn = 21 xn−1 + xn−1 q √ a = a, ∀n ≥ 2. egyenlőtlenséget, ahonnan xn ≥ xn−1 · xn−1 ³ ´ 2 n ≤ 0, mivel xn > 0 és x2n ≥ a ∀n ≥ 2. Ugyanakkor xn+1 − xn = 21 xn + xan − xn = a−x 2xn Tehát a sorozat csökkenő és alulról korlátos, emiatt Ha limn∞ xn = l, a ¡ konvergens. ¢ a 1 ⇔ l2 = a egyenlőséghez rekurencia relációban√határértékre térve az l = 2 l + l jutunk, ahonnan l = a. Evvel√ a módszerrel

való közelı́tés gyorsaságát is meghatározhatjuk. Ha az n-edik tag √ eltérését a-tól εn -nel jelöljük, ez azt jelenti, hogy xn √ − a = εn . Legyen xan = b, xn = c ⇒ b < c és εn+1 = xn+1 − a. √ √ 1 (b − c)2 (b − c)2 (2εn )2 ( b − c)2 b+c √ 2 − bc = = √ ≤ εn+1 = √ 2 ≤ a = a · εn ⇒ 2 2 8b 8 · 2 · 2( b + c) xn xn ⇒ εn+1 ≈ k · ε2n ⇒ a pozitı́v tizedesjegyek száma nagyjából megkétszereződik minden lépésben, tehát ez egy igen gyorsan közelı́tő módszer. 2.13 Tetszőleges függvény függvényértékének közelı́tése 2.1 Tétel Ha f : [a, b] R függvény kétszer deriválható [a, b]-n, f (a) · f (b) < 0, n) rekurzióval adott f 0 (x) > 0, f 00 (x) ≥ 0 ∀x ∈ [a, b], akkor az x0 = b, xn+1 = xn − ff0(x (xn ) sorozat konvergens és határértéke az f függvény egyetlen zérushelye. Bizonyı́tás: Mivel f folytonos és f (a) · f (b) < 0,

létezik olyan c ∈ (a, b), amelyre f (c) = 0. Mivel f 0 (x) > 0, ∀x ∈ [a, b], az f szigorúan növekvő, ı́gy egyetlen zérushelye van. Matematikai indukcióval igazoljuk, hogy c ≤ xn+1 ≤ xn , ∀n ∈ N-re 0) ≤ x0 . n = 0-ra: c ≤ x1 ≤ x0 ⇔ c ≤ x0 − ff0(x (x0 ) 0) ≤ x0 ⇔ − ff0(b) ≤ 0, igaz, mivel f 0 (b) ≥ 0 és f (b) > 0. Ugyanakkor, mivel Az x0 − ff0(x (x0 ) (b) (c) ⇔ f konvex, az x-beli érintője a c és b közti húrnál meredekebb, azaz f 0 (b) ≥ f (b)−f b−c f (b) f (b) b − c ≥ f 0 (b) ⇔ c ≤ b − f 0 (b) . 11 Még be kell látni, hogy ha c ≤ xk ≤ xk−1 , akkor c ≤ xk+1 ≤ xk , k ∈ N∗ rögzı́tett szám esetén. f (xk ) ≤ xk c ≤ xk+1 ≤ xk ⇔ c ≤ xk − 0 f (xk ) xk − f (xk ) f (xk ≤ xk ⇔ − 0 ≤ 0 igaz, 0 f (xk ) f (xk ) mivel f 0 (xk ) ≥ 0 és c ≤ xk az indukciós feltétel alapján és mivel f növekvő, következik, hogy f (xk ) ≥ f (c) = 0. Mivel f

konvex, az xk -beli érintője a c és xk közti húrnál meredekebb, azaz f 0 (xk ) ≥ f (xk )−f (c) k) k) ⇔ xk − c ≥ ff0(x ⇔ c ≤ xk − ff0(x . xk −c (xk ) (xk ) 2.2 Rekurzı́v számlálások Igen sok számlálási feladattal találkozhatunk, amelyek megoldása egy rekurencia reláció helyes felı́rásán áll vagy bukik. Természetesen ezek után a rekurencia által adott sorozat általános tagját is meg kell határoznunk, de az esetek többségében a rekurencia felállı́tása jelent nagyobb gondot. 2.21 Algebra és számelmélet körébe tartozó problémák 2.1 Feladat Hányféleképpen lehet felmenni egy n lépcsőfokból álló lépcsőn, ha egyszerre csak egy vagy két lépcsőt léphetünk? Megoldás: Jelöljük an -nel az n lépcsőfok esetén lehetséges felmenések számát. Ha kezdetben egy lépcsőfokot lépünk, akkor marad n − 1 lépcsőfok és ezen an−1

-féleképpen mehetünk fel. Ha kezdetben 2 lépcsőfokot lépünk, akkor marad n − 2 lépcsőfok és ezen an−2 -féleképpen lehet felmenni. Így an = aa−1 + an−2 , ∀n ≥ 2 és a1 = 1, a2 = 2, ez pedig a Fibonacci-sorozatot megadó rekurzió eggyel eltolt tagokkal, azaz an = Fn+1 . 2.2 Feladat Piros és kék golyókból 20 golyó hosszúságú láncot készı́tünk Hányféleképpen tehetjük meg ezt, ha piros golyók nem kerülhetnek egymás mellé? Megoldás: Jelölje xn az n golyóból álló láncok lehetséges számát. Ha az első felfűzött golyó kék, akkor a következő bármi lehet, ı́gy egy n − 1 hosszú láncot kell készı́teni, amit xn−1 -féleképpen tehetjük meg. Ha viszont az első golyó piros, a következőnek kéknek kell lennie, és ı́gy egy n − 2 hosszú láncot kell még készı́tenünk, amit xn−2 -féleképpen tehetjük meg. Innen xn = xn−1 + xn−2 , x1 = 2,

x2 = 3, ami pontosan a Fibonacci-sorozat kettővel eltolt tagokkal, azaz xn = Fn+2 . Tehát x20 = F22 = 17711 2.3 Feladat Hányféleképpen lehet 1 × 2-es dominókkal lefedni egy 2 × n-es táblát? Megoldás: Legyen bn a 2 × n-es tábla lehetséges lefedésinek száma. Ha a 2 × n-es tábla végénél olyan dominót helyezünk el, amely a tábla rövidebb oldalával párhuzamos, akkor marad egy 2 × (n − 1)-es tábla, amit bn−1 -féleképpen fedhetünk le. Ha egy olyan dominót helyeztünk el, amely a hosszabb oldallal párhuzamos, akkor ahhoz, hogy lefedjük a táblát még rá kell helyezzünk egy dominót és ezután egy 2 × (n − 2)-es táblát kell lefednünk. Ezt bn−2 módon tehetjük meg. Így bn = bn−1 + bn−2 és b1 = 1, b2 = 2 Tehát bn = Fn+1 12 2.4 Feladat Határozzál meg az n ∈ N∗ szám 2-hatványok összegeként való felı́rásainak (partı́cióinak) számára egy rekurenciát, majd

számı́tsd ki a 27 partı́cióinak számát! Megoldás: Jelöljük xn -nel az n szám lehetséges partı́cióinak számát. Ekkor n xn 1 2 3 1 2 2 4 5 6 4 4 6 7 8 6 10 9 10 11 10 14 14 P i Páratlan szám esetén (2n + 1 = 2 ), ennek minden partı́ciója kell tartalmazzon legalább egy 1-est. Ha ezt elhagyjuk, akkor 2n-nek egy partı́cióját kapjuk, ezért: x2n+1 = x2n . Páros szám esetén, ha felı́rjuk az összes partı́ciót, ezek között lesznek olyanok, amelyek tartalmaznak 1-est, és olyanok, amelyek nem. Az 1-est tartalmazó partı́ciókban nyilván legalább két 1-esnek kell lennie. Ha ezeket leválasztjuk, akkor a 2n − 2 szám lehetséges partı́cióit melyek száma x2n−2 . Az egyest nem tartalmazó partı́ciókban, ha a P kapjuk, i 2n = 2 -ben leosztunk kettővel, az n szám partı́cióit kapjuk, melyek száma xn . Így x2n = x2n−2 + xn . Tehát egy természetes szám 2-hatványok összegeként

való felı́rásainak számát a következő rekurziós összefüggés adja meg: ½ x2n = x2n−2 + xn x2n+1 = x2n A 27 partı́cióinak száma megegyezik a 26 partı́cióinak a számával, azaz x27 = x26 , tehát x26 -ot kell meghatároznunk. Ha a fenti táblázatot folytatjuk csak a páros indexű tagokkal, akkor a következőt kapjuk: n xn 10 12 14 20 14 16 26 36 18 20 46 60 22 24 26 74 94 114 Tehát a 27 2-hatványok összegeként való felı́rásainak száma: x27 = x26 = 114. 2.5 Feladat Határozzuk meg az {1, 2, , 10} halmaz involúcióinak1 számát! Megoldás: Jelölje an az {1, 2, . , n} halmaz involúcióinak számát Ha meg akarjuk szerkeszteni az {1, 2, . , n + 1} halmaz involúcióit, mivel σ(σ(i)) = i, ∀i = 1, n + 1, ha σ(n + 1) = n + 1, akkor a többi elemnek an módon feleltethetünk meg elemeket. Ha σ(n + 1) = i 6= n + 1, mivel σ(σ(n + 1)) = n + 1 ⇒ σ(i) = n + 1 és a megmaradt n − 1 elemnek

an−1 módon feleltethetünk meg elemeket. Tehát an+1 = an + n · an−1 , ∀n ≥ 1 esetén. 2.6 Feladat Ha a 1,2,3 számjegyek felhasználásával olyan n-jegyű számot akarunk gyártani, amelyben bármely két szomszédos számjegy legfennebb 1-gyel tér el egymástól, hányféleképpen tehetjük meg ezt? 1 σ = σ −1 összefüggést teljesı́tő permutációk 13 Megoldás: Jelöljük xn -nel az n-jegyű, ilyen tulajdonságú számok számát. Ha egy ilyen szám 2-vel kezdődik, akkor utána bármi következhet, tehát xn−1 módon helyezhetjük el a többi számjegyet. Ha 1-gyel kezdődik, akkor viszont nem folytatódhat 3-mal, ı́gy ezek száma xn−1 -(a 3-mal kezdődő (n−1) jegyű számok száma). Hasonlóan, ha 3-mal kezdődik, akkor nem folytatódhat 1-gyel és ezek száma xn−1 -(a 1-gyel kezdődő (n − 1) jegyű számok száma). Tehát xn = 3xn−1 -(a 1-gyel és a 3-mal kezdődő (n

− 1) jegyű számok száma), azaz xn = 3xn−1 − (xn−1 − xn−2 ) = 2xn−1 + xn−2 , ∀n ≥ 3, x1 = 3, x2 = 7. √ 2 A rekurzió 0, melynek gyökei: q1 = 1 + 2 és √1 = √ karakterisztikus egyenlete: √ n q − 2q − q2 = 1 − 2. Ekkor xn = A · (1 + 2) + B · (1 − 2)n A kezdeti értékeket behelyettesı́tve: √ √ ½ A · (1 + √2) + B · (1 − √2) = 3 , A · (1 + 2)2 + B · (1 − 2)2 = 7 √ √ √ √ £ ¤ ahonnan A = 1+2 2 és B = 1−2 2 , ı́gy xn = 21 (1 + 2)n+1 + (1 − 2)n+1 , ∀n ∈ N∗ . 2.22 Kombinatorikus geometria körébe tartozó problémák 2.7 Feladat Legtöbb hány részre osztja n egyenes a sı́kot? Megoldás: Nyilvánvalóan a legtöbb sı́krész akkor keletkezik, ha bármely két egyenes metszi egymást, és nincs három, ugyanazon a ponton átmenő egyenes. Ha xn -el jelöljük az n egyenes által meghatározott tartományok számát, akkor xn−1 egyenes n − 1 részre osztja a

sı́kot. Az n-dik egyenes az (n − 1) egyenes mindegyikét 14 metszi egy pontban, ı́gy keletkezik n − 1 újabb tartomány, és az utolsó metszéspont utáni tartományban is keletkezik egy új tartomány. Tehát az xn = xn−1 + n rekurziót állı́thatjuk fel. Rekurzió megoldása egyszerű: felı́rjuk 2 képletet a rekurenciát k = 1, n-re és összegezzük, ı́gy az xn = 1 + 1 + 2 + . n = n +n+2 2 kapjuk. 2.8 Feladat Legtöbb hány részre osztja a sı́kot n kör? Megoldás: Itt a legtöbb tartományt akkor kapjuk, ha bármely két kör metszi egymást, és nincs három, ugyanazon a ponton átmenő kör. Ha an -nel jelöljük az n kör által meghatározott tartományok számát, akkor n − 1 kör an−1 részre osztja a sı́kot, az n.-dik kör pedig az (n − 1) körön 2(n − 1) metszéspontot határoz meg, és minden új metszésponthoz tartozik egy új tartomány. 15 Így az xn = xn−1 + 2(n −

1) rekurziót kapjuk, ebből szintén a rekurencia relációk összegzésével kapjuk, hogy xn = 2 + 2(1 + 2 + . (n − 1)) = 2 + n(n − 1) = n2 − n + 2 2.9 Feladat Egy 2n oldalhosszúságú háromszöget 4n2 darab, 1 oldalhosszúságú háromszögre bontunk, az oldalakkal párhuzamós egyenesek segı́tségével. Hány egyenlőoldalú háromszög keletkezik? Megoldás: Jelöljük x2n -nel a következő háromszögek számát. Néhány sajátos esetben a kapott értékek: A 2n oldalhosszú háromszög esetében keletkező háromszögeket úgy számoljuk össze, hogy megszámoljuk az CA0 B 0 háromszögekben keletkezőket, és ehhez még hozzáadjuk azokat, amelyek valamelyik csúcsa az AB oldalon levő pontok valamelyike. Bármely két 16 2 pont az AB-ről pontosan egy, egyenlőoldalú háromszögnek oldala, ı́gy C2n+1 = 2n(2n+1) 2 háromszög keletkezik. Tehát az olyan háromszögek száma,

amelyeknek két csúcsa az AB-n . van 2n(2n+1) 2 Olyan háromszögből, amelynek egy csúcsa van az AB-n, van 2n − 1 darab egy oldalhosszú, 2n − 3 darab kettő oldalhosszú, 2n − 5 darab három oldalhosszú, . és 1 darab n oldalhosszú. Tehát összesen: 2n(2n + 1) + 2n − 1 + 2n − 3 + · · · + 1 = n(2n + 1) + n2 = n(3n + 1) 2 háromszögünk van, amelynek valamelyik csúcsa az (AB] oldalon helyezkedik el. Így az x2n = x2n−1 + 3n2 + n rekurziót kapjuk. Ha hasonlóan járunk el a 2n − 1oldalú háromszögek esetében, akkor az (2n − 1)2n + 2n − 2 + 2n − 4 + · · · + 2 = 2 = x2n−2 + n(2n − 1) + (n − 1)n = x2n−2 + 3n2 − 2n rekurziót kapjuk. x2n−1 = x2n−2 + A fenti két rekurziós összefüggésből: x2n = x2n−2 + 6n2 − n. A kapott rekurenciát felı́rjuk k = 2, n-re, és összegezzük, ı́gy az ¸ · n X n(n + 1) n(n + 1)(2n + 1) n(n + 1)(4n + 1) 2 −1 − +1 = x2n = x2 + (6n −n) = 5+6 6 2 2 k=2

képletet kapjuk. 2.10 Feladat Egy n oldalú konvex sokszög átlói között nincs három összefutó a) Hány átlója van a sokszögnek? b) Az átlók az n szöget hány részre osztják? 17 Megoldás: a) Rekurzı́v számlálást alkalmazunk. A négyszögnek 2, az ötszögnek 5 átlója van Ha xn -nel jelöljük az n-szög átlóinak számát, és felveszünk egy (n + 1)-edik pontot, az n + 1-szög átlóinak számát úgy kapjuk, ha megszámoljuk, hogy a már meglevő xn átlón kı́vül milyen más átlókat kapunk. Egy új átló az A1 An és az összes An -ből kifutó átlók, melyek száma n − 2. Tehát xn+1 = xn + 1 + n − 2, azaz xn+1 = xn + n − 1. Felı́rjuk az egyenlőséget minden −1 = k = 3, n − 1-re, összegezzük őket, és ı́gy az xn = x3 + 2 + 3 + · · · + n − 2 = (n−1)(n−2) 2 n(n−3) n2 −3n egyenlőséget kapjuk. Az n-szög atlóinak száma tehát 2 2 b)

Jelöljük yn -el az n-szögben az átlók metszéspontjainak számát. Néhány sajátos esetre xn és yn értékei a mellékelt táblázatban láthatók. n xn y n Ha elkezdjük behúzni az átlókat valamilyen sorrendben, az első átló két 4 2 1 reśzt határoz meg, ettől kezdve pedig minden újabb átló behúzásakor a 5 5 5 már meglévő részek száma d + 1-gyel nő, ha d az illető átlónak a már 6 9 15 behúzott átlókkal alkotott metszéspontjainak a száma. Vezessük be a következő jelöléseket: Jelölje ak a k átló által a sokszögben meghatározott részek számát és bk a k-adik átlónak az előzőleg behúzott átlókkal való metszéspontjainak számát (nyilvánvalóan mindkét érték függ attól, hogy milyen sorrendben húzzuk be az átlókat). A fentiek alapján az ak+1 = ak + bk+1 + 1 rekurziót iŕhatjuk 2 − 1-re felı́rva és összegezve, kapjuk, hogy

fel. A rekurziót minden k = 1, n −3n 2 ³ ´ n2 − 3n − 1, a n2 −3n = a1 + b2 + b3 + · · · + b n2 −3n + 2 2 2 azaz az utolsó átló behúzásakor kapott részek száma egyenlő az első átló behúzásakor 2 + 1-nek és az átlók metszéspontjainak összegével. kapott részek számának (2), n −3n 2 Most már csak azt kell megszámolni, hogy az átlók hány pontban metszik egymást. Minden metszéspontot két átló határoz meg, melyek végpontjai a sokszög négy csúcsában vannak Ugyanakkor bármely csúcsnégyes meghatároz egyetlen metszéspontot, tehát az átlók . metszéspontjainak száma megegyezik a csúcsnégyesek számával, ez pedig n(n−1)(n−2)(n−3) 24 Így n2 − 3n n(n − 1)(n − 2)(n − 3) +1+ = 2 24 n2 (n − 3)2 + 14n(n − 3) + 24 n(n − 3)[12 + (n − 1)(n − 2)] + 24 = = = 24 24 (n − 1)(n − 2)(n2 − 3n + 12) [n(n − 3) + 2][n(n − 3) + 12] = . = 24 24 a n2 −3n = 2 18

Hivatkozások [1] R. L Graham, D E Knuth, G Patashnik: Concrete mathematics, Addison Wesley, Reading, MA, 1989 [2] Kenneth H. Rosen: Discrete Mathematics and Its Applications - Sixth Edition [3] P. A MacMahon: Combinatory Analysis, Chelsea, New York, 1960 [4] V. K Balakrishnan: Combinatorics, Scham’s Outlines, McGraw-Hill, New York, 1995 [5] András, Csapó, Balázs, Szilágyi: Matematika a XI. osztály számára, Státus kiadó [6] Gh. Sireţchi: Calcul diferenţial şi integral, EDP, 1986 [7] I. Muntean, D Popa: Metoda şirurilor recurente, Editura Gil, 1996 [8] Arthur Engel: Probleme de matematica - Strategii de rezolvare, Editura Gil, 2006 [9] Dan Brânzei şi colab.: Şiruri recurente ı̂n liceu, Editura Gil, 1996 [10] Richard Stanley: Exercises on Catalan Number, Cambridge University Press, 1999 19