W wykładach o indukcji i rekurencji analizowaliśmy kilka przykładów tą metodą. Analogicznie rozwiązywaliśmy też równania rekursywne. Indukcja sprawdza się gdy intuicje odnośnie sumy, którą chcemy policzyć, pozwalają nam na wysuwanie hipotez co do jej wartości. Jest to też dobra metoda sprawdzenia wyników (w celu wychwycenia ewentualnych błędów) otrzymanych inną metodą. Niestety, najczęściej gdy chcemy wskazać wzór na sumę, nie jesteśmy w stanie go zgadnąć. Wtedy trzeba posłużyć się innymi metodami.
Przykład
Rozważmy sumę skończonego ciągu arytmetycznego o parametrach \( a,b\in\mathbb{Z} \):
Zauważmy, że
Dodając odpowiednie równości stronami otrzymujemy:
Zatem \( \displaystyle \sum_{0\leq k\leq n}(a+kb)=(a+\frac{1}{2}nb)(n+1) \), czyli obliczana suma jest średnią arytmetyczną pierwszego \( a \) i ostatniego \( a+bn \) składnika sumy pomnożoną przez liczbę składników sumy. Takiej metody użył młody Gauss, gdy zniecierpliwiony jego pytaniami nauczyciel polecił mu policzyć sumę tysiąca pierwszych liczb naturalnych.
Przykład
Ciąg harmoniczny \( \displaystyle H_n=\sum_{i=1}^n\frac{1}{i} \) poznaliśmy w wykładzie o indukcji. Pokazaliśmy tam, że
\( \frac{\lfloor \lg{n}\rfloor+1}{2} \leq H_n \leq \lfloor \lg{n}\rfloor+1. \)
Tym razem jesteśmy zainteresowani sumami postaci
\( \displaystyle \sum_{i=1}^n H_i=\sum_{i=1}^n\sum_{j=1}^i\frac{1}{j}, \)
których pierwsze wartości przedstawia tabela:
\( \begin{array} {|c||c|c|c|c} \hline n & 1 & 2 & 3 & \ldots \\ \hline H_n & 1 & \frac{3}{2} & \frac{5}{3} & \ldots \\ \hline \displaystyle \sum_{i=0}^nH_i & 1 & \frac{5}{2} & \frac{25}{6} & \ldots \\ \hline \end{array} \)
W tym przypadku zamienimy kolejność wyrazów w sumie po czym okaże się, że nowa postać jest prosta do przeliczenia. Wypiszmy więc wszystkie wyrazy w naszej podwójnej sumie, tak by kolejne wiersze były składnikami liczb harmonicznych:
\( \begin{array} {ccccc} 1 \\ 1 & \frac{1}{2} \\ 1 & \frac{1}{2} & \frac{1}{3} \\ \ldots & \ldots & \ldots & \ldots \\ 1 & \frac{1}{2} & \frac{1}{3} & \ldots & \frac{1}{n} \end{array} \)
Zauważmy, że oryginalny zapis nakazuje najpierw sumować wiersze, a później wartości tych wierszy. Zmieńmy zatem kolejność sumowania aby najpierw sumować kolumny:
\( \begin{align*}\sum_{i=1}^nH_i=\sum_{i=1}^n\sum_{j=1}^i\frac{1}{j} & =\sum_{i=1}^n\frac{1}{i}\cdot (n-i+1) \\ & =n\sum_{i=1}^n\frac{1}{i}-\sum_{i=1}^n1+\sum_{i=1}^n\frac{1}{i} \\ & =(n+1)H_n-n. \end{align*} \)
Gdy interesują nas skończone sumy odcinków początkowych ciągu \( {\{ {a_i} \}\ }_{i\in\mathbb{N}} \), czyli sumy postaci \( \displaystyle S_n=\sum_{i=0}^n a_i \). Metoda zaburzania polega na obliczeniu wartości \( S_{n+1} \) za pomocą \( S_n \) na dwa różne sposoby: na ogół wydzielając pierwszy i ostatni składnik sumy tzn.:
\( \displaystyle {S_n+a_{n+1}=a_0+\sum_{i=0}^n a_{i+1}}. \)
Jeśli uda się nam ostatnią sumę wyrazić za pomocą \( S_n \), to otrzymamy równanie, którego rozwiązanie jest poszukiwaną sumą. Niestety, metoda zaburzania dalece nie zawsze działa. Jednak w wielu sytuacjach bywa elegancka i skuteczna.
Przykład
Policzmy sumę \( \displaystyle \sum_{i=0}^n ax^i \) skończonego ciągu geometrycznego dla \( a,x\in\mathbb{Z} \), \( x\neq1 \). Zgodnie z ogólnym schematem zaburzania mamy:
\( \begin{align*}\sum_{i=0}^n ax^i+ax^{n+1} & =ax^0+\sum_{i=0}^n ax^{i+1} \\ & =a+x\sum_{i=0}^n ax^i. \end{align*} \)
Rozwiązując powyższe równanie dostajemy:
\( \displaystyle \sum_{i=0}^nax^i=\frac{a-ax^{n+1}}{1-x},\ \) dla \( x\neq 1. \)
Przykład
Tym razem jesteśmy zainteresowani sumą \( \displaystyle \sum_{i=0}^n i2^i \),która przyjmuje wartości:
\( \begin{array} {|c||c|c|c|c|c|c} \hline n & 0 & 1 & 2 & 3 & 4 & \ldots \\ \hline n2^n & 0 & 2 & 8 & 24 & 64 & \ldots \\ \hline \displaystyle \sum_{i=0}^n i2^i & 0 & 2 & 10 & 34 & 98 & \ldots \\ \hline \end{array} \)
Licząc przez zaburzanie dostajemy:
\( \begin{align*}\sum_{i=0}^n i2^i+(n+1)2^{n+1} & =0\cdot2^0+\sum_{i=0}^n (i+1)2^{i+1} \\ & =2\sum_{i=0}^n i2^i+2\sum_{i=0}^n2^i \\ & =2\sum_{i=0}^n i2^i+2\cdot(2^{n+1}-1), \end{align*} \)
gdzie suma skończonego ciągu geometrycznego \( \displaystyle{\sum_{i=0}^n2^i} \) została wyliczona w poprzednim przykładzie. Zatem ostatecznie
\( \displaystyle \sum_{i=0}^n i2^i=(n+1)2^{n+1}-2(2^{n+1}-1)=(n-1)2^{n+1}+2. \)
Przykład
Spróbujmy policzyć jeszcze raz sumę kwadratów \( \displaystyle \sum_{i=0}^ni^2, \) ale tym razem przez zaburzanie.
\( \begin{align*}\sum_{i=0}^n i^2 + (n+1)^2 & =0^2+\sum_{i=0}^n(i+1)^2 \\ & =\sum_{i=0}^n i^2+2\sum_{i=0}^n i+\sum_{i=0}^n 1 \\ & =\sum_{i=0}^n i^2+2\sum_{i=0}^n i+n \end{align*} \)
Niestety okazuje się, że sumy kwadratów się skracają. Zaburzanie okazało się w tym przypadku nieskuteczne. Zauważmy jednak, iż z otrzymanej równości \( \displaystyle 2\sum_{i=0}^n i=(n+1)^2-(n+1) \) dostajemy wzór na sumę kolejnych liczb naturalnych (a nie kwadratów jak chcieliśmy). Nasuwa się podejrzenie, że aby otrzymać wzór na sumę kwadratów trzeba zaburzyć sumę sześcianów. Spróbujmy:
\( \begin{align*}\sum_{i=0}^n i^3+(n+1)^3 & =0^3+\sum_{i=0}^n(i+1)^3 \\ & =\sum_{i=0}^n i^3+3\sum_{i=0}^n i^2+3\sum_{i=0}^n i+\sum_{i=0}^n 1 \\ & =\sum_{i=0}^n i^3+3\sum_{i=0}^n i^2+3\frac{n(n+1)}{2}+(n+1). \end{align*} \)
Rzeczywiście, sumy sześcianów się skracają i możemy wyprowadzić wzór na sumę kwadratów:
\( \begin{align*} 3\sum_{i=0}^n i^2 & =(n+1)^3-\frac{3}{2}n(n+1)-(n+1)= (n+1)((n+1)^2-\frac{3}{2}n -1), \\ \sum_{i=0}^n i^2 & =\frac{(n+1)(n^2+2n+1-\frac{3}{2}n-1)}{3}=\frac{n(n+\frac{1}{2})(n+1)}{3}. \end{align*} \)