Metoda czynnika sumacyjnego pozwala na rozwiązywanie równań rekurencyjnych postaci
a
n
T
n
=
b
n
T
n
−
1
+
c
n
{\displaystyle a_{n}T_{n}=b_{n}T_{n-1}+c_{n}}
poprzez sprowadzenie ich do postaci
U
n
=
U
n
−
1
+
w
n
,
{\displaystyle U_{n}=U_{n-1}+w_{n},}
gdzie
a
n
,
b
n
,
c
n
,
w
n
{\displaystyle a_{n},b_{n},c_{n},w_{n}}
to ciągi współczynników.
Zakładamy, że spełnione są warunki
a
n
≠
0
{\displaystyle a_{n}\neq 0}
dla
n
⩾
0
,
{\displaystyle n\geqslant 0,}
oraz
b
n
≠
0
{\displaystyle b_{n}\neq 0}
dla
n
>
0.
{\displaystyle n>0.}
Aby dojść do oczekiwanej postaci definiujemy czynnik sumacyjny , czyli ciąg
s
n
,
n
=
0
,
1
,
…
{\displaystyle s_{n},\;n=0,1,\dots }
spełniający równanie
s
n
b
n
=
s
n
−
1
a
n
−
1
,
{\displaystyle s_{n}b_{n}=s_{n-1}a_{n-1},}
lub inaczej
s
n
=
s
n
−
1
a
n
−
1
b
n
.
{\displaystyle s_{n}=s_{n-1}{\frac {a_{n-1}}{b_{n}}}.}
Przez pomnożenie równania wyjściowego obustronnie przez
s
n
{\displaystyle s_{n}}
pozbywamy się zależności od
b
n
{\displaystyle 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
.
{\displaystyle 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
,
{\displaystyle 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
,
{\displaystyle U_{n}=U_{n-1}+s_{n}c_{n},}
i dalej w postaci sumy
U
n
=
∑
k
=
0
n
s
k
c
k
.
{\displaystyle U_{n}=\sum _{k=0}^{n}s_{k}c_{k}.}
Uwzględniając definicję
U
n
,
{\displaystyle U_{n},}
otrzymujemy
s
n
a
n
T
n
=
∑
k
=
0
n
s
k
c
k
=
U
0
+
∑
k
=
1
n
s
k
c
k
=
s
0
a
0
T
0
+
∑
k
=
1
n
s
k
c
k
=
s
1
b
1
T
0
+
∑
k
=
1
n
s
k
c
k
.
{\displaystyle 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
{\displaystyle T_{n}}
ma postać
T
n
=
1
s
n
a
n
(
s
1
b
1
T
0
+
∑
k
=
1
n
s
k
c
k
)
.
{\displaystyle 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
.
{\displaystyle s_{n}.}
Z określenia
możemy wyznaczyć
s
n
{\displaystyle s_{n}}
dla
n
>
0.
{\displaystyle n>0.}
Musimy przyjąć warunek na zakończenie
rekurencji – możemy to zrobić, wybierając
s
0
=
1.
{\displaystyle s_{0}=1.}
Wówczas otrzymujemy ciąg
s
0
=
1
,
{\displaystyle s_{0}=1,}
s
1
=
a
0
b
1
,
{\displaystyle s_{1}={\frac {a_{0}}{b_{1}}},}
s
2
=
s
1
a
1
b
2
=
a
0
a
1
b
1
b
2
{\displaystyle s_{2}=s_{1}{\frac {a_{1}}{b_{2}}}\ ={\frac {a_{0}a_{1}}{b_{1}b_{2}}}}
i ogólnie
s
n
=
a
0
a
1
…
a
n
−
1
b
1
b
2
…
b
n
=
∏
k
=
0
n
−
1
a
k
∏
k
=
1
n
b
k
.
{\displaystyle 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}}}.}