Matematika | Analízis » 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. 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 1 . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 3 4 4 6 . . . . . . . 10 10 10 11 11 12 12 14 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 1.31 Rekurzı́v sorozatok általános tagjának meghatározása 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. 2.1 2.11 A rekurzı́v sorozatok néhány alkalmazása Közelı́tések 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 = µ ¶ 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 Tehát K2n = 1 kn 2 + ⇒ 1 Kn ¶ α 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 ) Az x0 − f (x0 ) f 0 (x0 ) ≤ x0 ⇔ − ff0(b) ≤ 0, igaz, mivel f 0 (b) ≥ 0 és f (b) > 0. Ugyanakkor, mivel (b) f konvex, az x-beli érintője a c és b közti húrnál meredekebb, azaz f 0 (b) ≥ ⇔ c ≤ b − ff0(b) . b − c ≥ ff0(b) (b) (b) 11 f (b)−f (c) b−c ⇔ 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 = 2.22 √ 1+ 2 2 és B = √ 1− 2 , 2 ı́gy xn = 1 2 £ (1 + √ n+1 √ ¤ 2) + (1 − 2)n+1 , ∀n ∈ N∗ . 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 x2n ¸ · n X n(n + 1) n(n + 1)(2n + 1) n(n + 1)(4n + 1) 2 −1 − +1 = = 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