Szeminárium-Rekurziók

1

Szeminárium-Rekurziók

1.1.

A sorozat fogalma

Számsorozatot kapunk, ha pozitív egész számok mindegyikéhez egyértelm˝uen hozzárendelünk egy valós számot. Tehát a számsorozat olyan függvény, amelynek az értelmezési tartománya a pozitív egész számok halmaza, az értékkészlete pedig a valós számok vagy annak egy részhalmaza, vagy komplex számok vagy... . Értelmezési tartomány: N. Értékkészlet: an ∈ R. A sorozat elemeit a-val jelöljük. Az elem sorszámát alsóindexbe tesszük: a1 ,a2 ,a3 ,...,an ,..., ahol a1 az els˝o elem, an az n-edik elem. A líceumi tananyag keretén belül többször találkozunk sorozatokkal. Az els˝o ismerkedés a IX. osztályban történik a számtani illetve mértani sorozatok keretén belül, ugyanakkor a matematikai indukció elvénél is találkozhatunk néhány sorozattal, bár ekkor még hallgatólagosan használjuk a sorozat fogalmát. A IX osztályban még csak ismer˝osöként ismert sorozatok, X,XI osztályban már komoly barátokká válnak, s a tananyag majdnem minden részében felismerhetjük o˝ ket. Ez annak köszönhet˝o, hogy a sorozatra nem kell másképp nézni mint egy függvényre, sajátos függvényre. Röviden ismételjük át a számtani illetve mértani sorozatok f˝o tulajdonságait.

1.2.

Számtani sorozatok

A számtani sorozat olyan számsorozat, amelyben bármely két - ugyanolyan sorrendben vett - szomszédos elemének kül"onbsége állandó. A különbséget differenciának nevezzük, és d-vel jelöljük. Így: an+1 − an = d, ahol n ∈ N, d ∈ R

1

(1.2.1)

FEJEZET 1. SZEMINÁRIUM SZEMINÁRIUM-REKURZIÓK

2

A sorozat bármelyik elemét megkapjuk, ha az el˝oz˝o elemhez hozzáadjuk a különbséget: an+1 = an + d.

(1.2.2)

Ha d > 0 akkor a számtani sorozat szigorúan növekv˝o, ha d < 0 akkor a sorozat elemi szigorúan monoton csökken˝oek, ha d = 0 akkor állandó vagy konstans sorozatról beszélünk. 1.2.1. Tétel. A számtani sorozat n-edik elemét a következ˝o képlettel is kiszámíthatjuk: adjuk hozzá az els˝o elemhez a differencia n − 1-szeresét: an = a1 + (n − 1) · d.

(1.2.3)

1.2.2. Tétel. A számtani sorozat els˝o n tagjának az összegét a következ˝o képlettel számíthatjuk ki: Sn =

(a1 + an ) · n 2a1 + (n − 1)d = . 2 2

(1.2.4)

1.2.3. Tétel. A számtani sorozatban bármely három szomszédos eleme közül a középs˝o a két széls˝onek a számtani közepe. Ez az összefüggés általánosan is igaz: bármely elem a t˝ole szimmetrikusan elhelyezked˝o elemeknek a számtani közepe: an =

1.3.

an+i + an−i , ahol i ∈ N, i < n. 2

(1.2.5)

Mértani sorozatok

A mértani sorozat olyan számsorozat, amelyben bármely két - ugyanolyan sorrendben vett - szomszédos elemének hányadosa állandó. A hányadost, más néven quotienst q-val jelöljük. Így an+1 = q, ahol n ∈ N∗ , q 6= 0, an

(1.3.6)

és az elemek között sem szerepel a nulla. A sorozat bármelyik elemét megkapjuk, ha az el˝oz˝o elemet szorozzuk a hányadossal: an+1 = an · q.

(1.3.7)

Ha a hányados pozitív, akkor a sorozat minden eleme azonos el˝ojel˝u, ha negatív, akkor az elemek váltakozó el˝ojel˝uek. Ha q > 1, akkor a sorozat szigorúan monoton növekv˝o, ha 0 < q < 1, akkor a sorozat szigorúan monoton csökken˝o, ha q = 1, akkor a sorozat konstans. 1.3.4. Tétel. A mértani sorozat n-edik elemét a következ˝o képlettel is kiszámolhatjuk: az els˝o tagot megszorozzuk a hányados n − 1-edik hatványával an = a1 · q n−1 .

(1.3.8)

1.3.5. Tétel. A mértani sorozat els˝o n tagjának összegét a következ˝o képlettel számíthatjuk ki Sn = a1

qn − 1 , q 6= 1. q−1

(1.3.9)


3

1.3.1. Megjegyzés. Ha q = 1, akkor létezik egy β ∈ R konstans, amelyre an = β, minden n ∈ N esetén, ami azt jelenit, hogy Sn = n · β. 1.3.6. Tétel. A mértani sorozat bármely három szomszédos eleme közül a középs˝o négyzete a két széls˝onek a szorzatával egyenl˝o: an+1 =

√

an · an+2 .

(1.3.10)

1.3.2. Megjegyzés. Ez az összefüggés általánosan is igaz: bármely elem négyzete a t˝ole szimmetrikusan elhelyezked˝o elemeknek a szorzata: an =

1.3.1.

√

an−i · an+i , i < n.

Egy alkalmazás

A sorozatok közül több kereskedelmi, gazdasági kérdés tisztázásában a mértani sorozatnak van jelent˝os szerepe. Ilyen például a kamatos kamat számítás, tehát hogy a bankba betett pénzösszeg az évenként hozzácsatolt éves kamattal együtt mennyi lesz. Ezt nevezzük évenkénti t˝okésítésnek. Ha évi p% a kamatláb, akkor évi kamata

1 100

lesz. A pénz 1 +

p 100 -

· p, évi t˝okésítéssel a bankba tett x RON egy év múlva x p x+ ·p=x 1+ 100 100 szorosára növekszik. Ezt jelöljük el q-val, ezt kamattényez˝onek nevezzük. Ezzel a

jelöléssel a bankba tett x RON 1, 2, 3, ..., n év elteltével kamatos kamataival felnövekedve xq, xq 2 , ..., xq n RON lesz.

1.4.

Megoldott feladatok

1.4.1.

Hanoi tornyai

Elöször a Hanoi tornyai néven ismert feladatot mutatjuk be. Edouard Lucas francia matematikus 1883-ban vizsgálta a következ˝o feladatot: 1.4.1. Feladat. Van egy nyolc korongból álló torony; a korongok három rúd egyikén helyezkednek el, alulról felfelé csökken˝o méretben. A cél az, hogy a teljes tornyot valamelyik másik rúdra helyezzük át úgy, hogy minden lépésben egyetlen korongot mozgathatunk, és a följebb elhelyezked˝o korong mindig kisebb kell, hogy legyen, mint a lejjebb elhelyezked˝o. Megoldás. Az ilyen jelleg˝u problémákhoz legjobb oly módon hozzákezdeni, hogy kissé általánosítjuk, majd sajátos esetben a saját feladatot is visszakapjuk. Nézzük mi a helyzet n korong esetén. Az általánosítás egyik el˝onye, hogy még jobban leszükíthetjük a feladatot. Elöször megfigyeljük a jelenségek kis n értékekre. Egy vagy két korong esetén könnyen láthatjuk, hogy miként tudjuk átpakolni a tornyot, és némi kisérletezéssel rátalálunk a megoldásra három korong esetén is. A probléma megoldásában a következ˝o lépés a megfelel˝o jelöl a bevezetése- a jó jelölés és megoldás megszervezés fél gy˝ozelem. Legyen Tn a minimális szükséges lépések száma. Ekkor nyilván T1 = 1, T2 = 3.


4

Tekinthetjük, hogy T0 = 0, hiszen egyetlen lépésre sincs szükség a torony átrakásához, ha n = 0. Elöször helyezzük át az n−1 legkisebb korongot egy másik rúdra(ehhez Tn−1 lépésre van szükség). Ez azt mutatja, hogy Tn ≤ 2Tn−1 + 1. A megoldásunkkal eddig csak annyit bizonyítottunk, hogy 2Tn−1 + 1 lépés elegend˝o, de azt még nem igazoltuk, hogy szükség van ennyi lépésre. Egy leleményes ember talán egy rövidebb utat gondolt el. De létezik jobb út? Valójában nem. Valamikor el kell mozdítanunk a legnagyobb korongot. Ekkor az n − 1 kisebbnek, egyetlen rúdon kell lennie, és ahhoz, hogy ezeket ide helyezzük, legalább Tn−1 elmozgatásra van szükség. Miután legutoljára mozdítottuk el a legnagyobb korongot, még át kell raknunk n − 1 kisebbet (amelyeknek ismét egyetlen rúdon kell elhelyezkedniük) a legnagyobbra és ehez ismét Tn−1 lépés kell. Tehát Tn ≥ 2Tn−1 + 1. Azaz a következ˝o rekurziót kapjuk (

T0 = 0, Tn = 2Tn−1 + 1,

A fenti rekurziót többféleképpen is megoldhatjuk: • Megsejtjük és indukcióval igazoljuk, hogy Tn = 2n − 1. • Bevezetjük an := Tn +1 jelölést és ekkor a következ˝o rekurzióhoz jutunk an+1 = 2an , ami valójában egy mértani sorozat, melynek általános tagjának képletét a 1.3.4. Tétel segítségével határozhatjuk meg, azaz an = 2n , és így Tn = 2n − 1.

1.4.2.

Josephus probléma

A második bevezet˝o probléma az els˝o században élt híres történetíró, Josephus Flavius nevéhez füzöd˝o régi probléma egy változata. A zsidó-római háború idején tagja volt a lázadók egy 41 f˝os csapatának, amelyet egy barlangban t˝orbe csaltak a rómaiak. A felkel˝ok úgy gondolkták, hogy inkább az öngyilkosságot válsztják, semmint fogságba essenek. Elhatározták, hogy körbeállva, és a körben köröskörül haladva megölik minden második, még él˝o személyt, amíg senki sem marad életben. Ám Josephus egy ismeretlen összeesküv˝o-társával hallani sem akart err˝ol az öngyilkossági hülyeségr˝ol, ezért gyorsan kiszámolta, hova álljanak a barátjával ebben az ördögi körben. A mi változatunkban kiinduláskor n ember áll egy körben, akiket, 1-t˝ol n-ig megszámozunk, és addig végzünk minden második személlyel, múg végül egyetlen túlél˝o marad. n = 10 esetén példúl a kiinduló helyzet az alábbi:


5

1 2

10

3

9

4

8

7 5 6

A kivégzési sorrend most 2, 4, 6, 8, 10, 3, 7, 1, 9 így 5 a túlél˝o. A feladat az, hogy meghatározzuk meg a túlél˝o sorszámát, Jn -et. Láttuk, hogy J1 0 = 5. Azt sejthetjük, hogy Jn =

n 2

ha n páros. Az n = 2 szintén alátámsztja a

sejtésünket, ámbár: n

1

2

3

4

5

6

Jn

1

1

3

1

3

5

´ be. Tehát valami a fenti táblázat azt mutatja, hogy n = 4 és n = 6 esetén a feltételezésünk nem igazoldott jobb ötlethez kell fordulnunk, ahhoz, hogy képesek legyünk a pontos értéket megadni. Úgy t˝unik, hogy Jn mindig páratlan. És valóban, jó magyarázata van ennek: amikor elöször haladunk körbe, kiesik valamennyi páros szám. Ezen kivül ha n maga is páros, akkor a kiinduló helyzethez hasonló szituációt kapunk kivéve, hogy fele annyi ember van, és megváltozott a sorszámuk. Tegyük fel, hogy eredetileg 2n ember van. Az els˝o körbejárás után a helyzet a következ˝o:


2n − 1

6

1 3 5

2n − 3

7

...

és a következ˝o lépésben a 3 sorszámú következik. Ez ugyanaz, mint amikor n ember volt, kivéve, hogy valamennyi személy sorszáma megkétszerez˝odött és eggyel csökkent, azaz J2n = 2Jn − 1, ha n ≥ 1. Most már gyorsan áttérhetünk a nagy n-ekre. Tudjuk példálul, hogy J10 = 5, így J20 = 9. Vagy hasonlóan J40 = 17 és általában J5·2m = 2m+1 + 1. De még nem vizsgálodtunk abban az esetben amikor n páratlan. Ha 2n + 1 személy van, akkor kiderül, hogy az 1 sorszámú ember rögtön 2n után esik ki, és ekkor az alábbi helyzettel van dolgunk:


7

3 5

2n + 1

7

2n − 1

9

...

Ismét csaknem az eredeti helyzethez jutottunk, amikor n ember volt, de most megmaradtak sorszáma megkétszerez˝odik és megn˝o eggyel, ezért J2n+1 = 2Jn + 1, ha n ≥ 1. Figyelembe véve, hogy J1 = 1, a következ˝o rekurziót tudjuk levezetni:    J1 = 1,  

J2n = 2Jn − 1,

ha n ≥ 1

J2n+1 = 2Jn + 1,

ha n ≥ 1

(1.4.11)

Keressük a zárt alakot, mert az még gyorsabb, és több információt ad. Végül is ez az élte vagy halál kérdése. Rekurziós összefüggésünk alkalmat teremt rá, hogy kis értékekre gyorsan készítsünk táblázatot. Talán kiszúrunk valami mintázatot, és akkor kitaláljuk a választ: n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Jn

1

1

3

1

3

5

7

1

3

5

7

9

11

13

15

1

Úgy néz ki, hogy 2-hatványonként lehet csoportosítani(ezt függ˝oleges vonallan jelöltük a táblázatban); Jn mindig 1 a csoport elején, és 2-vel növekszik a csoporton belül. Ha tehát n-et, n = 2m + l alakban írjuk, ahol 2m a legmagassab hatványa 2-nek, amely nem nagyob n-nél, akkor látszólag az alábbi megoldást kapjuk a rekurzióra: J2m +1 = 2l + 1 ha m ≥ 0, és 0 ≤ l < 2m .

(1.4.12)

A fenti képletünket m szerinti matematikai indukcióval igazolhatjuk. Látható, hogy m = 0, akkor l = 0, így J1 = 1 -t kapjuk ami nyilvánvalóan igaz, hiszen ez volt a rekurzió kezdeti értéke. Az indukciós lépés két lépsb˝ol áll attól függ˝oen, hogy l páros vagy páratlan. Amennyiben, m > 0 és 2m + l = 2n, akkor l párps, és (1.4.11) valamint az indukciós feltevés alapján J2m +l = 2J2m−1 +l/2 − 1 = 2(2l/2 + 1) − 1 = 2l + 1,


8

és ez pontosan az amit vártunk. Hasonló a bizonyítás a páratlan esetben is, amikor 2m + 1 = 2n + 1. A (1.4.12) illusztrálására határozzuk meg J100 -t: 100 = 26 + 36, tehát J100 = 2 · 36 + 1 = 73.

1.4.3.

Egyenesek és particiók

Harmadik minta példánk inkább geometriai: hány szelet pizzához jutunk n egyenes vágással?

Vagy másképpen mennyi a sík n egyenese által meghatározott tartományainal az Ln , maximális száma? Ezt a problémát els˝oként Jacob Steiner svájci matematikus oldotta meg 1826-ban. Ismét a kis esetekb˝ol fogunk kiindulni, nem elfelejtve, hogy a lehet˝o legkisebbel fogjuk kezdeni. Egyenes nélkül a síknak egyetlen tartománya van, egy egyenes esetén, kett˝o, még két egyenes négy tartományt hoz létre:

1

1

2 2

1

3 4

L0 = 1

L1 = 2

L2 = 4

Természetesen minden egyenes mindkét irányban végtelen. Bizonyára azt gondoljuk, hogy Ln = 2n , azzal érvelve, hogy új egyenest véve megduplázódik a tartományok száma. Sajnos ez tévedés. Akkor kapnánk kétszer annyi tartományt ha az n. egyenes mindegyik tartományt két részre vágná; természetesen eyg régi tartományt legfeljebb két darabra vág, mivel ezek mindegyike konvex. (Egy egyenes maximum két részre vág egy konvex tartományt amelyek maguk is konvexek.) Ám a harmadik egyenes legfeljebb csupán három régi tartományt tud kettévágni, bárhogy helyezkedik is el az els˝o két egyenes:


9

2 1a 4a

3a

1b 4b 3b

Ily módon L3 = 4 + 3 = 7 a legtöbb, amit elérhetünk. Némi gondolkodás után rájöhetünka megfelel˝o általánosításra. Az n. egyenes akkor és csak akkor növeli k-val a tartományok számát, ha k korábbi tartományt metsz, és pontosan akkor vág ketté k régi tartományt, ha az eredeti egyenesekkel k − 1 eltér˝o pontban találkozik. Két egyenesnek legfeljeebb egy metszéspontja van, így az új egynes az n − 1 régi egyenest legfeljebb n − 1 különböz˝o pontban metszheti el, ezért k ≤ n. Megkaptuk a fels˝o korlátot Ln ≤ Ln−1 + n, ha n > 0. Azt is könny˝u megmutatni, hogy elérhet˝o az egyenl˝oség ebben a kifejezésben. Egyszer˝uen úgy helyezzük el az n. egyenest, hogy az ne legyen párhuzamos az el˝oz˝oek közül egyikkel sem, ezért valamennyit metszik, és egyetlen már meglév˝o metszéspontosn se menjen át (tehát valamennyit különböz˝o pontban metsz). Ennélfogva a következ˝o rekurziót kaptuk: ( L0 = 1, Ln = Ln−1 + n,

ha n > 0.

Az általános képlet meghatározásához a következ˝oket írhatjuk fel: Ln = Ln−1 + n Ln−1 = Ln − 2 + (n − 1) .. . L2 = L1 + 1 L1 = L0 + 1 Összeadva Ln = L0 + 1 + 2 + ... + 3 = L0 +

n X j=1

1.4.4.

j =1+

n(n + 1) . 2

Egyéb feladatok

1.4.2. Feladat. Határozzuk meg a következ˝o rekurzívan értelmezett sorozatok általános tagját: (a) a1 = 1, an+1 =

an 5 ;

(1.4.13)


10

(b) a1 = −1, an+1 = 3an + 4; (c) a1 = 3, an+1 = an + n; (d) a1 = 3, a2 = 3, an+2 · an = a2n+1 − 2an+1 · an ; (e) a1 = 5, an+1 = a2n − 4an + 6; Megoldás. 1. an+1 =

an 5

=

1 an . Ekkor a 1.3.4 Tétel segítségével könnyedén megtudjuk mondani az általános 5 |{z} q

tag képletét behelyetesítve a képletbe az információkat. 2. an+1 = 3an + 4, ekkor ha bevezetjük a bn = an + 2 jelölést akkor a következ˝o rekurziót kapjuk bn+1 = 2bn . Ezt a rekurziót szintén megoldhatjuk a 1.3.4 Tétel segítségével. 3. an+1 = an + n rekurzió megoldását lásd fentebb. 4. an+2 · an = a2n+1 − 2an+1 · an , az adott összefüggés mindkét oldalát an+1 · an , a kezdeti értékekb˝ol igazolható, hogy egyik sem nulla. Ekkor bevezetve az xn =

an+1 an

jelölést a követekez˝o rekurziót

kapjuk xn+1 = xn − 2. Ami egy csökken˝o számtani haladványra utal. Ezért xn = 3 − 2n. Ekkor x1 · x2 · .. · xn =

a2 a3 an+1 an+1 · · ... · = = (−1)n−1 (2n − 3)!! a1 a2 an a1

5. A megadott rekurzió a következ˝oképpen írhatjuk át an+1 − 2 = (an − 2)2 . Ebb˝ol következik, hogy an > 2 (figyelembe vettük a kezdeti értékeket is). Ekkor logaritmálva mindkét oldalt és bevezetve xn = ln(an − 2) a következ˝o rekurziót kapjuk xn+1 = 2xn . Melynek általános tagjának a képletére alkalmazzuk a 1.3.4 Tétel. 1.4.3. Feladat. Határozzuk meg a következ˝o rekurzívan értelmezett sorozatok általános tagját: (a) x0 = 31 , xn+1 =

xn 1+2xn , ∀n

xn (b) x0 = 1, xn+1 = √ 3

1+x3n

≥ 0;

, ∀n ≥ 0;


11

Megoldás. 1. A megadott rekurziót megfordítjuk és bevezetjük az yn =

1 xn

jelölést akkor a következ˝o rekurziót

kapjuk yn+1 = yn + 2. A fenti rekurzió egy számtani haladvány, így általános tagjának meghatározása nem mutat túl a tanult képletek használatán. 2. Ennek a feladatnak is a megoldása, hasonló az el˝oz˝o feladat megoldásáéhoz, ugyanis mindkét oldalt felemeljül a harmadik hatványra és alkalmazzuk az el˝oz˝o pontban ismertetett ötletet.

1.5.

Kituzött ˝ feladatok-Házi feladatok

Az alábbi feladatok esetén a piros színu˝ feladatok ismerked˝o (kötelez˝oen megoldandó) feladatok, a kék gyakorló feladatok és a zöld elmélyít˝o jellegu˝ feladatok. A feladatok mellett szerepel egy pontszám. Az összpontszámnak 10-el való osztása adja meg a szemináriumi jegyet. A piros feladatok nem megoldása pontlevonással jár. Minden színu˝ feladatkörb˝ol(piros, kék,zöld) kötelez˝o feladatot oldani. 1. Minden ló színe azonos, amit egy adott ménes lovainak száma szerinti indukcióval bizonyíthatunk az alábbi módon: "Ha egyetlen ló van akkor ez önmagával azonos szín˝u, így az állítás az triviális. Az indukciós lépéshez tegyük fel, hogy n ló van 1-t˝ol n-ig számozva. Az indukciós felvetés szerint az els˝o n − 1 ló színe megegyezik, és azonos az utolsó n − 1 ló színe is. Ám a 2-t˝ol n − 1 ig számozott lovak színe nem változik attól, hogy más csoportba soroljuk o˝ ket, végtére is ezek lovak, nem kaméleonok. Ekkor viszont az 1 és n sorszámú lovak színe is azonos a tranzitivitás alapján, ami azt jelenti, hogy mind az n ló színe megegyezik , amivel a bizony´tás kész. " Hol a hiba a fenti okoskodásban, ha egyáltalán van benne hiba? 2. Adjuk meg a kegkevesebb lépésb˝ol álló megoldást, amellyel az n korongot tartalmazó torony átvihet˝o A rúdról B rúdra, ha közvetlenül nem szabad A-ról B-re és fordítva korongot áthelyezni( vagyis minden lépésben a középs˝o rúdról vagy a középs˝o rúdra kerül a korong; természetesen nagyobb korong soha nem kerülhet egy kisebbre.) 3. Az n egyenes átlal a síkon létrehozott régió közül néhány végtelen, miközben mások korlátosak. Mennyi a korlátos tartományok lehetséges maximális száma? 4. Legyen Hn = Jn+1 − Jn . A (1.4.11) alapján H2n = 2 és H2n+1 = J2n+2 − J2n+1 = 2Hn − 2, minden n ≥ 1 esetén. Ennélfogva úgy t˝unik, hogy n szerinti indukcióval bizonyítható a minden n-re érvényes Hn = 2 egyenl˝oség. Hol a hiba? 5. Maximum hány tartományt hozható létre n egyszeresen törött vonallal? 6. Maximum hány tartományt hozhatunk létre n kétszeresen megtört vonallal. ha mindegyik két párhuzamos félegyenes és az o˝ ket összeköt˝o egyenes szakaszból áll, mint a Z bet˝u?


12

7. Hány sajtszelet nyerhet˝o egyeltlen vastag darabból öt egyenes vágással? (A sajtnakeredeti helyén kell maradnia, amíg valamennyi vágást végrehajtjuk, és mindenegyes vágás egy sík a három dimenziós térben.) Keressünk rekurziós összefüggést az n különböz˝o síkkal nyerhet˝o háromdimenziós tartományok maximális Pn számára. 8. Jospehus barátja aki, úgy menekült meg, hogy az utolsó el˝otti helyen állt. Mi lesz In , azaz az utolsó el˝otti túlél˝o sorszáma, ha minden másodikat végzik ki? (Adjunk rekurziós összefüggést, majd oldjuk meg a kapott rekurziót) 9. Határozzuk meg a következ˝o rekurzívan értelmezett sorozatok általános tagját: (a) a1 = 21 , a2 = 13 , an+2 =

an ·an+1 3an −2an+1 , ∀n

≥ 1;

(b) a1 = 4, an+1 = 3an − 2, ∀n ≥ 1; (c) x0 = 3, x1 = 4, xn+1 = x2n−1 − nxn , ∀n ≥ 1 p √ (e) x0 = 1, x1 = 2, xn+1 = xn + 6 xn−1 , ∀n ≥ 1; (f) x1 = 3, x2 = 2, xn+2 +

1 xn

= 2, ∀n ≥ 1;

10. Határozzuk meg az összes olyan egész számsorozatot amely teljesíti az xn+1 =

n·xn +1 xn +n , ∀n

∈ N

összefüggéseket! 11. Bizonyítsuk be, hogy az xn+1 =

2 2−xn , n

≥ 1 sorozat peridódikus(ha értelmezett)!

12. Bizonyítsuk be, hogy az x0 , x1 ∈ (−k, k), xn+2 =

k2 (xn+1 −xn ) k2 −xn ·xn+1 , ∀n

≥ 0 rekurziót teljesít˝o sorozat

peridódikus! 13. Határozd meg az xn = x2n−1 − 3xn−1 , ∀n ≥ 1.x0 ∈ [−2, 2] sorozat általános tagját! p 14. Határozd meg az x0 = 1, xn+1 (1 + 1 + x2n ) = xn , n ≥ 0 sorozat általános tagját. 15. Határozd meg az x0 = −1, xn =

2xn−1 −3 3xn−1 −4 , n

≥ 1 sorozat általános tagját!

16. Bizonyítsuk be, hogy x0 = 1, x1 = 41, xn+2 = 3xn + értelmezett sorozat minden tagja természetes szám!

q 8(x2n + x2n+1 ), ∀n ≥ 0 összefüggésekkel

Szeminárium-Rekurziók

Recommend Documents