A lineáris rekurziókra vonatkozó alaptétel

1. példa Legyen

a_n=4a_n-1+a_n-2, ha n>₌2

a₀=a₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,5,21,89,377,1597,6765,28657,121393,514229,...

A generátorfüggvény:

Legyen A(x)=a₀+a₁x+a₂x²+a₃x³+...= 1+x+5x²+21x³+89x⁴+377x⁵+1597x⁶+...

Így A(x)=1-3x+4xA(x)+x²A(x). Azaz

A(x)=(1-3x)/(1-4x-x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-4x-x²=(1-2x)²-5x²= [(1-2x)-(gyök(5)x)][(1-2x)+(gyök(5)x)]= [1-(2x+gyök(5)x)][1-(2x-gyök(5)x)]= [1-(2+gyök(5))x][1-(2-gyök(5))x] Legyen N₁=1-(2+gyök(5))x és N₂=1-(2-gyök(5))x
N₁ és N₂ segítségével x és 1 is kifejezhetõ:
N₂-N₁=2gyök(5)x,
N₂/(2-gyök(5))-N₁/(2+gyök(5))=1/(2-gyök(5))-1/(2+gyök(5)).
Rendezve
gyök(5)/10 N₂-gyök(5)/10 N₁=x,
(5+2gyök(5))/10 N₂+(5-2gyök(5))/10 N₁=1.
A számláló kifejezése N₁ és N₂ segítségével: 1-3x=(5-gyök(5))/10 N₂+(5+gyök(5))/10 N₁,
A fenti képletek a generátorfüggvénybe való beírása: A(x)=(1-3x)/(1-4x-x²)=[(5-gyök(5))/10 N₂+(5+gyök(5))/10 N₁]/ N₁N₂= (5-gyök(5))/10 1/N₁+(5+gyök(5))/10 1/N₂= (5-gyök(5))/10 1/(1-(2+gyök(5))x)+(5+gyök(5))/10 1/(1-(2-gyök(5))x).

* A generátorfüggvénybõl a_n-re vonatkozó képlet kiolvasása:

a_n=[xⁿ]A(x)= [xⁿ]((5-gyök(5))/10 1/(1-(2+gyök(5))x)+(5+gyök(5))/10 1/(1-(2-gyök(5))x))= (5-gyök(5))/10 (2+gyök(5))ⁿ+(5+gyök(5))/10 (1-(2-gyök(5))ⁿ.

2. példa Legyen

b_n=3b_n-1-2b_n-2, ha n>₌2

b₀=2, b₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 2,1,-1,-5,-13,-29,-61,-125,-253,-509,-1021,-2045,...

A generátorfüggvény:

Legyen B(x)=b₀+b₁x+b₂x²+b₃x³+...= 2+x-x²-5x³-13x⁴-29x⁵-61x⁶+...

Így B(x)=2-5x+3xB(x)-2x²B(x). Azaz

B(x)=(2-5x)/(1-3x+2x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-3x+2x²=(1-x)(1-2x). Legyen N₁=1-x és N₂=1-2x.
N₁ és N₂ segítségével x és 1 is kifejezhetõ:
N₁-N₂=x,
2N₁-N₂=1.
A számláló kifejezése N₁ és N₂ segítségével: 2-5x=2(2N₁-N₂)-5(N₁-N₂)= -N₁+3N₂.
A fenti képletek a generátorfüggvénybe való beírása: B(x)=(2-5x)/(1-3x+2x²)=(-N₁+3N₂)/N₁N₂= -1/N₂+3/N₁= -1/(1-2x)+3/(1-x).

* A generátorfüggvénybõl b_n-re vonatkozó képlet kiolvasása:

b_n=[xⁿ]B(x)= [xⁿ](-1/(1-2x)+3/(1-x))=3-2ⁿ.

3. példa Legyen

c_n=5c_n-1+2c_n-2, ha n>₌2

c₀=c₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,7,37,199,1069,5743,30853,165751,890461,....

A generátorfüggvény:

Legyen C(x)=c₀+c₁x+c₂x²+c₃x³+...= 1+x+7x²+37x³+199x⁴+1069x⁵+5743x⁶+...

Így C(x)=1-4x+5xC(x)+2x²C(x). Azaz

C(x)=(1-4x)/(1-5x-2x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-5x-2x²=(1-5/2 x)²-25/4 x²-2x²= (1-5/2 x)²-33/4 x²= [(1-5/2 x)-(gyök(33)/2 x)][(1-x)+(gyök(33)/2 x)]= [1-(5/2 x+gyök(33)/2 x)][1-(5/2 x-gyök(33)/2 x)]= [1-(5+gyök(33))/2 x][1-(5-gyök(33))/2 x] Legyen N₁=1-(5+gyök(33))/2 x és N₂=1-(5-gyök(33))/2 x.
N₁ és N₂ segítségével x és 1 is kifejezhetõ:
N₂-N₁=gyök(33)x,
2N₂/(5-gyök(33))-2N₁/(5+gyök(33))=2/(5-gyök(33))-2/(5+gyök(33)).
Rendezve
gyök(33)/33 N₂-gyök(33)/33 N₁=x,
(33+5gyök(33))/66 N₂+(33-5gyök(33))/66 N₁=1.
A számláló kifejezése N₁ és N₂ segítségével: 1-4x=(33-3gyök(33))/66 N₂+(33+3gyök(33))/66 N₁.
A fenti képletek a generátorfüggvénybe való beírása: C(x)=(1-4x)/(1-5x-2x²)= [(33-3gyök(33))/66 N₂+ (33+3gyök(33))/66 N₁]/ N₁N₂= (33-3gyök(33))/66 1/N₁+ (33+3gyök(33))/66 1/N₂= (33-3gyök(33))/66 1/(1-(5+gyök(33))/2 x)+ (33+3gyök(33))/66 1/(1-(5-gyök(33))/2 x).

* A generátorfüggvénybõl c_n-re vonatkozó képlet kiolvasása:

c_n=[xⁿ]C(x)= [xⁿ](33-3gyök(33))/66 1/(1-(5+gyök(33))/2 x)+ (33+3gyök(33))/66 1/(1-(5-gyök(33))/2 x)= (33-3gyök(33))/66 ((5+gyök(33))/2)ⁿ+ (33+3gyök(33))/66 ((5-gyök(33))/2)ⁿ.

4. példa Legyen

d_n=2d_n-1-d_n-2, ha n>₌2

d₀=1, d₁=3.

Érdemes felírni a sorozat elsõ néhány elemét: 1,3,5,7,9,11,13,15,17,19,21,23,25,27,...

A generátorfüggvény:

Legyen D(x)=d₀+d₁x+d₂x²+d₃x³+...= 1+3x+5x²+7x³+9x⁴+11x⁵+13x⁶+...

Így D(x)=1+x+2xD(x)-x²D(x). Azaz

D(x)=(1+x)/(1-2x+x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-2x+x²=(1-x)².
A számláló felírható (1-x) polinomjaként:
1+x=2-(1-x)
A fenti képletek a generátorfüggvénybe való beírása: D(x)=(1+x)/(1-2x+x²)= (2-(1-x))/(1-x)²=2/(1-x)²-1/(1-x).

* A generátorfüggvénybõl d_n-re vonatkozó képlet kiolvasása:

d_n=[xⁿ]D(x)= [xⁿ](2/(1-x)²-1/(1-x))= 2[xⁿ]1/(1-x)²-[xⁿ]1/(1-x)= 2(n+1)-1=2n+1.

A fenti kiolvasáshoz a lényeges ismeret, hogy tudjuk: [xⁿ]1/(1-x)^k=(^-k_n)=(^n+k-1_k-1). Így speciálisan [xⁿ]1/(1-x)²=n+1.

5. példa Legyen

e_n=-2e_n-1-e_n-2, ha n>₌2

e₀=e₁=1.

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,-3,5,-7,9,-11,13,-15,17,-19,21

A generátorfüggvény:

Legyen E(x)=e₀+e₁x+e₂x²+e₃x³+...= 1+x-3x²+5x³-7x⁴+9x⁵-11x⁶+...

Így E(x)=1+3x-2xE(x)-x²E(x). Azaz

E(x)=(1+3x)/(1+2x+x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1+2x+x²=(1+x)².
A számláló felírható (1+x) polinomjaként:
1+3x=3(1+x)-2
A fenti képletek a generátorfüggvénybe való beírása: E(x)=(1+3x)/(1+2x+x²)= (3(1+x)-2)/(1+x)²=-2/(1+x)²+3/(1+x).

* A generátorfüggvénybõl e_n-re vonatkozó képlet kiolvasása:

e_n=[xⁿ]E(x)= [xⁿ](-2/(1+x)²+3/(1+x))= -2[xⁿ]1/(1+x)²+3[xⁿ]1/(1+x)= -2(-1)ⁿ(n+1)+3(-1)ⁿ=(-1)ⁿ(1-2n).

6. példa Legyen

f_n=6f_n-1-9f_n-2, ha n>₌2

f₀=f₁=1.

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,-3,-27,-135,-567,-2187,...

A generátorfüggvény:

Legyen F(x)=f₀+f₁x+f₂x²+f₃x³+...= 1+x-3x²-27x³-135x⁴-567x⁵-2187x⁶+...

Így F(x)=1-5x+6xF(x)-9x²F(x). Azaz

F(x)=(1-5x)/(1-6x+9x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-6x+9x²=(1-3x)².
A számláló felírható (1-3x) polinomjaként:
1-5x=5/3 (1-3x)-2/3
A fenti képletek a generátorfüggvénybe való beírása: F(x)=(1-5x)/(1-6x+9x²)= (5/3 (1-3x)-2/3)/(1-3x)²=-2/3 1/(1-3x)²+5/3 1/(1+x).

* A generátorfüggvénybõl f_n-re vonatkozó képlet kiolvasása:

f_n=[xⁿ]F(x)= [xⁿ]((1-5x)/(1-6x+9x²))= -2/3[xⁿ]1/(1-3x)²+5/3 [xⁿ]1/(1-3x)= -2/3 3ⁿ(n+1)+5/3 3ⁿ=(3-2n)3^n-1.

7. példa Legyen

g_n=4g_n-1-5g_n-2, ha n>₌2

g₀=g₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,-1,-9,-31,-79,-161,-249,-191,481,...

A generátorfüggvény:

Legyen G(x)=g₀+g₁x+g₂x²+g₃x³+...= 1+x-x²-9x³-31x⁴-79x⁵-161x⁶+...

Így G(x)=1-3x+4xG(x)-5x²G(x). Azaz

G(x)=(1-3x)/(1-4x+5x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-4x+5x²=(1-2x)²+x²=(1-2x)²-(ix)²= [(1-2x)-(ix)][(1-2x)+(ix)]= [1-(2x+ix)][1-(2x-ix)]= [1-(2+i)x][1-(2-i)x] Legyen N₁=1-(2+i)x és N₂=1-(2-i)x
N₁ és N₂ segítségével a számláló kifejezhetõ:
N₂+N₁=2-4x,
N₂-N₁=2ix, azaz iN₂-iN₁=-2x.
A két egyenlet átlaga
(1+i)/2 N₂+(1-i)/2 N₁=1-3x,
(5+2gyök(5))/10 N₂+(5-2gyök(5))/10 N₁=1.
A fenti képletek a generátorfüggvénybe való beírása: G(x)=(1-3x)/(1-4x+5x²)=[(1+i)/2 N₂+(1-i)/2 N₁]/ N₁N₂= (1+i)/2 1/N₁+(1-i)/2 1/N₂= (1+i)/2 1/(1-(2+i)x)+(1-i)/2 1/(1-(2-i)x).

* A generátorfüggvénybõl g_n-re vonatkozó képlet kiolvasása:

g_n=[xⁿ]G(x)= [xⁿ]((1+i)/2 1/(1-(2+i)x)+(1-i)/2 1/(1-(2-i)x))= (1+i)/2 (2+i)ⁿ+(1-i)/2 (2-i)ⁿ.

8. példa Legyen

h_n=2h_n-1-4h_n-2, ha n>₌2

h₀=h₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,-2,-8,-8,16,64,64,-128,-512,-512,...

A generátorfüggvény:

Legyen H(x)=h₀+h₁x+h₂x²+h₃x³+...= 1+x-2x²-8x³-8x⁴+16x⁵+64x⁶+...

Így H(x)=1-x+2xH(x)-4x²H(x). Azaz

H(x)=(1-x)/(1-2x+4x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-2x+4x²=(1-x)²+3x²=(1-x)²-(i gyök(3)x)²= [(1-x)-(i gyök(3)x)][(1-x)+(i gyök(3)x)]= [1-(x+i gyök(3)x)][1-(x-i gyök(3)x)]= [1-(1+i gyök(3))x][1-(1-i gyök(3))x] Legyen N₁=1-(1+i gyök(3))x és N₂=1-(1-i gyök(3))x
N₁ és N₂ segítségével a számláló kifejezhetõ:
N₂+N₁=2-2x,
Azaz 1/2 N₂+1/2 N₁=1-x.
A fenti képletek a generátorfüggvénybe való beírása: H(x)=(1-x)/(1-2x+4x²)=[1/2 N₁+1/2 N₂]/ N₁N₂= 1/2 1/N₂+1/2 1/N₁= 1/2 1/(1-(1-i gyök(3))x)+1/2 1/(1-(1+i gyök(3))x).

* A generátorfüggvénybõl h_n-re vonatkozó képlet kiolvasása:

h_n=[xⁿ]H(x)= [xⁿ](1/2 1/(1-(1-i gyök(3))x)+1/2 1/(1-(1+i gyök(3))x))= 1/2 (1+i gyök(3))ⁿ+1/2 (1-i gyök(3))ⁿ.

A binomiális képletbõl könnyen látható, hogy formulánk egész értéket ad meg. Ezt láthatóbbá tehetjük komplex számaink trigonometrikus formájának használatával. 1+i gyök(3)=2(1/2 + i gyök(3)/2)=2(cos 60^o+i sin 60^o) és 1-i gyök(3)=2(1/2 - i gyök(3)/2)=2(cos 60^o-i sin 60^o). Így (1+i gyök(3))ⁿ=(2(1/2 + i gyök(3)/2))ⁿ= 2ⁿ(cos n60^o+i sin n60^o) és (1-i gyök(3))ⁿ=2_n(cos n60^o-i sin n60^o).

Így h_n= 1/2 (1+i gyök(3))ⁿ+1/2 (1-i gyök(3))ⁿ= 2^n-1((cos n60^o+i sin n60^o)+(cos n60^o-i sin n60^o))= 2ⁿcos n60^o.

cos n60^o egy periodikus sorozat (n=0,1,2,3,...): 1,1/2,-1/2,-1,-1/2,1/2,1,1/2,-1/2,-1,-1/2,1/2,1,1/2,-1/2,-1,-1/2,1/2,... Ezt is beírhatjuk a fenti képletbe.

9. példa Legyen

i_n=6i_n-1-12i_n-2, ha n>₌2

i₀=i₁=1

Érdemes felírni a sorozat elsõ néhány elemét: 1,1,-6,-48,-216,-720,-1728,-1728,10368,...

A generátorfüggvény:

Legyen I(x)=i₀+i₁x+i₂x²+i₃x³+...= 1+x-6x²-48x³-216x⁴-720x⁵-1728x⁶+...

Így I(x)=1-5x+6xI(x)-12x²I(x). Azaz

I(x)=(1-5x)/(1-6x+12x²)

* A generátorfüggvény parciális törtekre bontása:

A generátorfüggvény nevezõjének szorzattá bontása: 1-6x+12x²=(1-3x)²+3x²=(1-3x)²-(i gyök(3)x)²= [(1-3x)-(i gyök(3)x)][(1-3x)+(i gyök(3)x)]= [1-(3x+i gyök(3)x)][1-(3x-i gyök(3)x)]= [1-(3+i gyök(3))x][1-(3-i gyök(3))x] Legyen N₁=1-(3+i gyök(3))x és N₂=1-(3-i gyök(3))x
N₁ és N₂ segítségével a számláló kifejezhetõ:
N₂+ N₁=2-6x,
Azaz 1/2 N₂+1/2 N₁=1-3x.
N₂- N₁=2i gyök(3)x,
Azaz i/gyök(3) N₂-i/gyök(3) N₁=-2x.
Összegezve (1/2 +i/gyök(3)) N₂+(1/2 -i/gyök(3)) N₁=1-5x.
A fenti képletek a generátorfüggvénybe való beírása: I(x)=(1-x)/(1-6x+12x²)=[(1/2 +i/gyök(3)) N₂+(1/2 -i/gyök(3)) N₁]/ N₁N₂= (1/2 +i/gyök(3)) 1/N₁+(1/2 -i/gyök(3)) 1/N₂= (1/2 +i/gyök(3)) 1/1-(3+i gyök(3))x +(1/2 -i/gyök(3)) 1/1-(3-i gyök(3))x.

* A generátorfüggvénybõl i_n-re vonatkozó képlet kiolvasása:

i_n=[xⁿ]I(x)= [xⁿ]((1/2 +i/gyök(3)) 1/1-(3+i gyök(3))x +(1/2 -i/gyök(3)) 1/1-(3-i gyök(3))x)= (1/2 +i/gyök(3)) (3+i gyök(3))ⁿ +(1/2 -i/gyök(3)) (3-i gyök(3))ⁿ.

A binomiális képletbõl látható, hogy formulánk egész értéket ad meg. Ezt láthatóbbá tehetjük komplex számaink trigonometrikus formájának használatával. 3+i gyök(3)=2gyök(3)(gyök(3)/2 + i 1/2)=2gyök(3)(cos 30^o+i sin 30^o) és 3-i gyök(3)=2gyök(3)(gyök(3)/2 - i 1/2)=2gyök(3)(cos 30^o-i sin 30^o) Így (1/2 +i/gyök(3))[2gyök(3)(cos 30^o+i sin 30^o)]ⁿ + (1/2 -i/gyök(3))[2gyök(3)(cos 30^o-i sin 30^o)]ⁿ= (2gyök(3))ⁿ[(1/2 +i/gyök(3))(cos n 30^o+i sin n 30^o)+ (1/2 -i/gyök(3))(cos n 30^o-i sin n 30^o)]= (2gyök(3))ⁿ[cos n 30^o-2/gyök(3) sin n 30^o]. Azaz

i_n=(2gyök(3))ⁿ[cos n 30^o-2/gyök(3) sin n 30^o].

cos n 30^o-2/gyök(3) sin n 30^o egy periodikus sorozat (n=0,1,2,3,...): 1,gyök(3)/6,-1/2,-2gyök(3)/3,-3/2,-5gyök(3)/6, -1,-gyök(3)/6,1/2,2gyök(3)/3,3/2,5gyök(3)/6, 1,gyök(3)/6,-1/2,-2gyök(3)/3,-3/2,-5gyök(3)/6, -1,-gyök(3)/6,1/2,2gyök(3)/3,3/2,5gyök(3)/6,... Ezt is beírhatjuk a fenti képletbe.