Sumace funkcí
■
Viděli jsme, že k řešení nehomogenních lineárních rekurentních formulí
s konstantními koeficienty potřebujeme umět počítat sumy funkcí. Buď f funkce
definovaná na množině všech nezáporných celých čísel. Sumou Hf funkce f rozumíme funkci g definovanou rovněž na množině všech nezáporných celých čísel takovou, že platí Ag = f. Poněkud podrobněji řečeno, sumou Hf funkce f rozumíme funkci g takovou, že pro všechna nezáporná celá čísla n platí
Je-li h jiná funkce taková, že Ah = f, pak pro funkci h — g a pro všechna nezáporná celá čísla n máme
To znamená, že funkce h — g je konstantní na množině všech nezáporných celých čísel, čili existuje konstanta c taková, že pro všechna nezáporná celá čísla n platí (/? — g)(n) = h(n) — g(n) = c, čili h(n) = g(n) + c. Je tedy suma Hf funkce f určena jednoznačně až na aditivní konstantu c.
Poznamenejme zprvu, že jsou-li /"i,    ..., fk libovolné funkce definované na množině všech nezáporných celých čísel a jsou-li ci, C2,..., Ck libovolné konstanty, pak zřejmě platí
&g(n) = g(n + 1) - g(n) = f(n).
A(h - g)(n) = Ah(n) - Ag(n) = f(n)
f(n) = 0.
T\Y,c,fi{n)J = J>^(n).
Argument n označuje, že zde vystupují funkce jedné nezáporné celočíselné proměnné.
Nalezneme dále sumy některých jednoduchých funkcí. Poněvadž pro identitu, to jest pro funkci n máme Aa? = n + ln = l,je vidět, že platí
Zl = n + c.
Obecněji pro každé kladné celé číslo k a pro klesající faktoriál [n]k máme A[n]/c = [n +     - [a?]/, = (n + - (n - /c + l)M*-i = k[n]k-lt takže
platí ^[a?]^-! = \ [n\k + c. Proto tedy
1
Dále z dřívějška víme, že pro každé kladné celé číslo k a pro mocninnou funkci nk platí nk = Xw=o «S/c,/[fl]/. kde Sk,i jsou Stirlingova čísla 2. druhu. Odtud a z předchozích poznatků vyplývá, že
En* = E S,, ^ + c.
i=0
Odtud pak vychází, že
1
Za? = -n(n — 1) + c,
1 1
Za?2 = -n(n - 1) + -n(n - l)(n - 2) + c,
2 3
a tak dále. Pro každé reálné nebo komplexní číslo a takové, že a ^ 1, a pro exponenciální funkci an máme Aa11 =       — a11 = (a — l)an, takže platí
Tan =-- + c.
a - 1
Zejména pro a = 2 vychází, že Z 2" = 2n + c.
Konečně si všimněme, že pro první diferenci A(/g") součinu fg dvou funkcí f b g a pro každé nezáporné celé číslo n platí
A(fg)(n) = (fg)(n + 1) - (£)(„) = f(n + l)ř(n + 1) - f(n)g(n)
= f(n + l)g(n + 1) - f{n)g(n + 1) + f(n)g(n + 1) - f{n)g(n)
= g{n + l)Af(n) + f(n)Ag(n). Odtud plyne vztah
f(n)Ag(n) = A(fg)(n) - g(n + l)Af(n)
= A(f(n)g(n)) - g(n + l)Af(n), z něhož sumací dostaneme rovnost
T(f{n)Ag{n)) = f{n)g{n) - T(g{n + l)Af(n)).
To je vztah pro takzvanou částečnou sumaci. S jeho pomocí můžeme například vypočítat
Z(a7 2") = n2" - Z2"+1 = n2n - 22" + c = (a7 - 2)2" + c.