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}\neq 0$ dla $n\geqslant 0,$ oraz $b_{n}\neq 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}}}\left(s_{1}b_{1}T_{0}+\sum _{k=1}^{n}s_{k}c_{k}\right).$

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}\ldots a_{n-1}}{b_{1}b_{2}\ldots b_{n}}}={\frac {\prod \limits _{k=0}^{n-1}a_{k}}{\prod \limits _{k=1}^{n}b_{k}}}.$

Literatura

• Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa 2002, ISBN 83-01-13906-4.