Matematyka dyskretna 1/Wykład 4: Sumy skończone i rachunek różnicowy

Wstęp

Oto dwie konwencje zapisu skończonych sum wyrazów:

$a_1+a_2+\dots +a_n=\sum _{i=1}^n{a}_i.$

Czasami stosowana jest ogólniejsza notacja $\sum _{i\in I}{a}_i$, gdzie $I$ jest skończonym zbiorem indeksów. Jeśli $I$ jest pusty to suma ma wartość $0$.

Często, zamiast określać zbiór indeksów $I$ podaje się pod sumą warunek ten zbiór definiujący. Na przykład:

Parser nie mógł rozpoznać (nieznana funkcja „\scriptsize”): {\displaystyle \sum_{\scriptsize\begin{array} {c}1\leq i\leq n\\ i \textrm{ nieparzysta}\end{array} }a_i }

Częstym zadaniem wobec którego stajemy to sprowadzenie sumy do postaci zwartej lub choćby znacząco prostszej. Ten wykład zawiera krótki przegląd metod i strategii obliczania skończonych sum. Znakomita część wykładu poświęcona jest prezentacji rachunku różnicowego - narzędzia pozwalającego liczyć skończone sumy w sposób systematyczny.

Kilka metod obliczania skończonych sum

Odgadnięcie rozwiązania i udowodnienie go przez indukcję

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.

Przeindeksowanie sumy

Przykład [Uzupelnij]

Rozważmy sumę skończonego ciągu arytmetycznego o parametrach $a,b\in \mathbb{\mathbb{Z}}$:

$\sum _{0\le k\le n}(a+kb)=a+(a+b)+(a+2b)+(a+3b)+\dots +(a+nb)=?$

Zauważmy, że

$\sum _{0\le k\le n}(a+kb)=\sum _{0\le k\le n}(a+(n-k)b)=\sum _{0\le k\le n}(a+nb-kb).$

Dodając odpowiednie równości stronami otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned2\sum_{0\leq k\leq n}(a+kb) &=&\sum_{0\leq k\leq n}((a+kb)+(a+nb-kb))\\ &=&\sum_{0\leq k\leq n}(2a+nb)\\ &=&(2a+nb)\sum_{0\leq k\leq n}1\\ &=&(2a+nb)(n+1). \endaligned}

Zatem $\sum _{0\le k\le 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,

foto, notka

gdy zniecierpliwiony jego pytaniami nauczyciel polecił mu policzyć sumę tysiąca pierwszych liczb naturalnych.

Zmiana kolejności sumowania w sumach wielokrotnych

Przykład

Ciąg harmoniczny $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}\le H_n\le \lfloor \lg n\rfloor +1.$

Tym razem jesteśmy zainteresowani sumami postaci

$\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}{ccccc}n& 1& 2& 3& \dots \\ H_n& 1& \frac{3}{2}& \frac{5}{3}& \dots \\ \sum _{i=0}^n{H}_i& 1& \frac{5}{2}& \frac{25}{6}& \dots \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}{c}1\\ 1& \frac{1}{2}\\ 1& \frac{1}{2}& \frac{1}{3}\\ \dots & \dots & \dots & \dots \\ 1& \frac{1}{2}& \frac{1}{3}& \dots & \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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\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. \endaligned}

Zaburzanie

Gdy interesują nas skończone sumy odcinków początkowych ciągu ${\left\{a_i\right\}}_{i\in \mathbb{\mathbb{N}}}$, czyli sumy postaci $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.:

$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ę $\sum _{i=0}^{n}a{x}^i$ skończonego ciągu geometrycznego dla $a,x\in \mathbb{\mathbb{Z}}$, $x\ne 1$. Zgodnie z ogólnym schematem zaburzania mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\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. \endaligned}

Rozwiązując powyższe równanie dostajemy:

$\sum _{i=0}^{n}a{x}^i=\frac{a-a{x}^{n+1}}{1-x},\text{<mrow data-mjx-texclass="ORD">dla</mrow>}x\ne 1.$

Przykład

Tym razem jesteśmy zainteresowani sumą $\sum _{i=0}^{n}i{2}^i$,która przyjmuje wartości:

$\begin{array}{ccccccc}n& 0& 1& 2& 3& 4& \dots \\ n{2}^n& 0& 2& 8& 24& 64& \dots \\ \sum _{i=0}^{n}i{2}^i& 0& 2& 10& 34& 98& \dots \end{array}$

Licząc przez zaburzanie dostajemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\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), \endaligned}

gdzie suma skończonego ciągu geometrycznego $\sum _{i=0}^n{2}^i$ została wyliczona w poprzednim przykładzie. Zatem ostatecznie

$\sum _{i=0}^{n}i{2}^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 $\sum _{i=0}^n{i}^2,$ ale tym razem przez zaburzanie.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\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 \endaligned}

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 $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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\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). \endaligned}

Rzeczywiście, sumy sześcianów się skracają i możemy wyprowadzić wzór na sumę kwadratów:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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}. \endaligned}