Rekurzív sorozatok

Mi a közös az alábbi sorozatokban?

a) a1=3; an=an-1+n.  (n>1)
b) b1=2, b2=3, bn=bn-1⋅√2+bn-2⋅sin(π/4).  (n>2)
c) c1=1, c2=1, cn=cn-1+cn-2. (n>2)

Mindhárom esetben az első (néhány) tag közvetlenül (explicit módon) lett megadva. A további tagok definíciójánál hivatkozunk az előző tagra vagy tagokra. Az ilyen sorozatok az un. rekurzív sorozatok.

Az egyik legismertebb rekurzív sorozat az un. Fibonacci sorozat.

Definíció:

Rekurzív sorozatoknak(rekurzív módon megadott sorozatoknak) nevezzük azokat a sorozatokat, amikor a sorozat általános tagját az előtte állók függvényében adjuk meg. 

Ezeknél a sorozatoknál az első néhány tagot explicit (közvetlen) módon meg kell adni. A rekurzív módon megadott sorozatok n-edik tagjára vonatkozó hozzárendelési szabálya sok esetben megadható explicit módon is.

Rekurzív megadás: a1=3; an=an-1+n. Ahol n>1.;
Az első néhány tagja a sorozatnak:
a2=a1+2=5a3=a2+3=a1+2+3=8a4=a3+4=a1+2+3+4=12,… és így tovább. Az n-edik tagr:  an=a1+(2+3+4+…+n).

Az an=a1+(2+3+4+…+n) átalakítható így: ​\( a_{n}=a_{1}+\frac{n(n+1)}{2}-1=2+\frac{n(n+1)}{2} \)​. mivel a1=3.
Itt felhasználtuk, hogy a1=3 és (2+3+4+…+n)=(1+2+3+4+…+n)-1=n(n+1)/2-1. (Az  1+2+3+4+…+n egy számtani sorozat első n tagjának összege, amely zárt alakban n(n+1)/2.)

Ugyanezt tapasztalhatjuk a számtani sorozatoknál:
Legyen a számtani sorozat első tagja 3, (a1=3), minden rákövetkező pedig 5-tel legyen nagyobb az előzőnél (differenciája d=5.)
Az n-edik tag megadása rekurzív módon: a1=3, an=a1+(n-1)⋅5
Explicit megadás: an=5⋅n-2.

Feladat:

Az {an} sorozat első tagja legyen 1; azaz a1=1. A sorozat n-edik tagját a következő rekurzív módon adjuk meg:  an=4⋅an-1+1.
Írjuk fel a sorozat első néhány tagját, majd állítsuk elő a sorozat n-edik tagját zárt alakban. (explicit módon)!

A sorozat első 4 tagja a definíció szerint:
a1=1; a2=4⋅1+1=5; a3=4⋅5+1=21; a4=4⋅21+1=85.

Sejtés: a sorozat n-edik tagját a következő képlet adja explicit módon: ​\( a_{n}=\frac{4^{n}-1}{3} \)​ .

A bizonyítás teljes indukcióval történik.

1. Első lépésben kiszámítjuk a sejtésben megfogalmazott képlet segítségével.

a2=(42-1)/3=(16-1)3=5a3=(43-1)/3=(64-1)3=21 , a4=(44-1)/3=(256-1)3=85.

Tehát ezekben az esetekben a képlet ugyanazt az értéket adja, mint amit a definíciónál kaptunk.

2. Második lépesben feltételezzük, hogy a sejtés igaz. Tehát: \( a_{n}=\frac{4^{n}-1}{3} \)​. (indukciós feltevés.)

3. Harmadik lépésben bizonyítandó, hogy a sejtés az (n+1)-dik tagra is öröklődik.
A bizonyításban felhasználjuk a definíciót és az indukciós feltevést.

A definíció szerint: an+1=4⋅an+1.

Az indukciós fetételezési képletet behelyettesítve an helyére: ​\( a_{n+1}=4·\frac{4^{n}-1}{3}+1=\frac{4·4^{n}-4}{3}=\frac{4^{n+1}-4+3}{3}=\frac{4^{n+1}-1}{3} \)​.

És ezt kellett igazolni.

 

 

 

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.