[Rekurencje i algorytmika] Rozwiązywanie rekurencyjnych równań za pomocą sumy.

[librusss]

Przykład:
$$T(n) = T(n-1) + n + 2$$

Natknąłem się ostatnio na dosyć ciekawy, a przy okazji niemożliwy dla mnie do wytłumaczenia dlaczego on działa, sposób. Prosiłbym o zerknięcie pod podany link:

Kod: Zaznacz cały

https://math.stackexchange.com/questions/1995079/solving-recurrence-relation-tn-tn-1-n-2

Najlepsza spośród odpowiedzi, twierdzi, że mając po lewej stronie postać \(\displaystyle{ T(n) - T(n-1) }\), zaś po prawej jakąś funkcję (w tamtym przykładzie n+2), możemy to sprowadzić do:
$$T(n) = \sum_{k=0}^{n} (k+2)$$
$$T(n) = \frac{n^2+5n}{2}+C$$
Co jest odpowiedzią poprawną. Może ktoś wytłumaczyć skąd wzięła się zamiana \(\displaystyle{ T(n) - T(n-1) }\) na taką sumę po prawej stronie? Jej obliczenie to oczywiście już żaden problem.

[Dasio11]

Dodając stronami równości \(\displaystyle{ T(k) - T(k-1) = k+2}\) dla \(\displaystyle{ k=1, 2, \ldots, n}\) mamy

\(\displaystyle{ \big( T(1)-T(0) \big) + \big( T(2) - T(1) \big) + \big( T(3) - T(2) \big) + \ldots + \big( T(n) - T(n-1) \big) = \sum_{k=1}^n (k+2)}\).

W sumie po lewej stronie większość składników się skróci: \(\displaystyle{ T(1)}\) w pierwszym nawiasie z \(\displaystyle{ -T(1)}\) w drugim, \(\displaystyle{ T(2)}\) w drugim nawiasie z \(\displaystyle{ -T(2)}\) w trzecim, i tak dalej. Po skróceniu zostaje

\(\displaystyle{ T(n) - T(0) = \sum_{k=1}^n (k+2)}\)

czyli

\(\displaystyle{ T(n) = \sum_{k=1}^n (k+2) + T(0) = \frac{n^2+5n}{2} + T(0)}\).