Metoda czynnika sumacyjnego

Metoda czynnika sumacyjnego pozwala na rozwiązywanie równań rekurencyjnych postaci $a_n{T}_n=b_n{T}_{n-1}+c_n$ poprzez sprowadzenie ich do postaci $U_n=U_{n-1}+w_n,$ gdzie $a_n,b_n,c_n,w_n$ to ciągi współczynników.

Zakładamy, że spełnione są warunki

$a_n\ne 0$ dla $n⩾0,$ oraz $b_n\ne 0$ dla $n>0.$

Cel metody

Celem jest sprowadzenie tej wyjściowej rekurencji do postaci

$U_n=U_{n-1}+w_n.$

Taka postać mówi nam, że wyraz o numerze $n$ powstaje z wyrazu o numerze $n-1$ przez dodanie do niego elementu $w_n.$ Oznacza to zatem, że $U_n$ można zapisać jako sumę

$U_n=\sum _{k=0}^n{w}_k.$

Opis metody

Aby dojść do oczekiwanej postaci definiujemy czynnik sumacyjny, czyli ciąg $s_n,n=0,1,\dots$ spełniający równanie

$s_n{b}_n=s_{n-1}{a}_{n-1},$

lub inaczej

$s_n=s_{n-1}\frac{a_{n-1}}{b_n}.$

Przez pomnożenie równania wyjściowego obustronnie przez $s_n$ pozbywamy się zależności od $b_n$ po prawej stronie równania:

$s_n{a}_n{T}_n=s_{n-1}{a}_{n-1}{T}_{n-1}+s_n{c}_n.$

Wprowadzamy teraz nową funkcję

$U_n=s_n{a}_n{T}_n,$

co pozwala nam zapisać poprzednie równanie jako

$U_n=U_{n-1}+s_n{c}_n,$

i dalej w postaci sumy

$U_n=\sum _{k=0}^n{s}_k{c}_k.$

Uwzględniając definicję $U_n,$ otrzymujemy

$s_n{a}_n{T}_n=\sum _{k=0}^n{s}_k{c}_k=U_0+\sum _{k=1}^n{s}_k{c}_k=s_0{a}_0{T}_0+\sum _{k=1}^n{s}_k{c}_k=s_1{b}_1{T}_0+\sum _{k=1}^n{s}_k{c}_k.$

Zatem równanie na $T_n$ ma postać

$T_n=\frac{1}{s_n{a}_n}(s_1{b}_1{T}_0+\sum _{k=1}^n{s}_k{c}_k).$

Ostatnim krokiem jest wyznaczenie wyrazów ciągu $s_n.$ Z określenia możemy wyznaczyć $s_n$ dla $n>0.$ Musimy przyjąć warunek na zakończenie rekurencji – możemy to zrobić, wybierając $s_0=1.$ Wówczas otrzymujemy ciąg

$s_0=1,$

$s_1=\frac{a_0}{b_1},$

$s_2=s_1\frac{a_1}{b_2}=\frac{a_0{a}_1}{b_1{b}_2}$

i ogólnie

$s_n=\frac{a_0{a}_1\dots a_{n-1}}{b_1{b}_2\dots b_n}=\frac{\prod _{k=0}^{n-1}{a}_k}{\prod _{k=1}^n{b}_k}.$

Literatura

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2002, Szablon:ISBN.