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

From Studia Informatyczne

Spis treści

Wstęp

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


\displaystyle a_1+a_2+\ldots+a_n=\sum_{i=1}^{n} a_i.


Czasami stosowana jest ogólniejsza notacja \displaystyle \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:


\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



MD1-3.1.swf

Przykład

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


\displaystyle \sum_{0\leq k\leq n}(a+kb)=a+(a+b)+(a+2b)+(a+3b)+\ldots+(a+nb)=\quad?


Zauważmy, że


\displaystyle \sum_{0\leq k\leq n}(a+kb)=\sum_{0\leq k\leq n}(a+(n-k)b)=\sum_{0\leq k\leq n}(a+nb-kb).


Carl Friedrich Gauss (1777-1855)Zobacz biografię
Enlarge
Carl Friedrich Gauss (1777-1855)
Zobacz biografię

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


\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 \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.

Zmiana kolejności sumowania w sumach wielokrotnych

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{\left\lfloor \lg{n}\right\rfloor+1}{2} \leq H_n \leq \left\lfloor \lg{n}\right\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:


\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{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:


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


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


\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 \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.


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


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


\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


Rachunek różnicowy

Żadna z przedstawionych metod obliczania skończonych sum nie jest niezawodnym kompletnym algorytmem. Są to raczej wskazówki bądź zestaw sztuczek, które czasem działają. Zaprezentujemy teraz podstawy rachunku różnicowego - dobrego narzędzia do obliczania skończonych sum.

Rachunek różnicowy powstał przez analogię do rachunku różniczkowego - działu matematyki zajmującego się badaniem funkcji rzeczywistych i zespolonych, przy użyciu ich pochodnych i całek. Podstawą rachunku różniczkowego jest operator pochodnej D, zdefiniowany jako


\displaystyle (Df)(x)=\lim_{h\rightarrow0}\frac{f(x+h)-f(x)}{h}.


Przyporządkowuje on funkcję Df funkcji rzeczywistej f. Odpowiednikiem operatora pochodnej w rachunku różnicowym jest operator różnicowy \Delta, zdefiniowany jako


(\Delta f)(x)=f(x+1)-f(x).


Przyporządkowuje on funkcję \Delta f funkcji rzeczywistej f. Będziemy go jednak rozważać tylko dla funkcji określonych na zbiorze liczb naturalnych (czyli dla ciągów). Operator \Delta to "skończony odpowiednik" operatora D. Rozważając funkcję liczb całkowitych f nie mamy możliwości badać granicy występującej w definicji D. W zamian za to rozważamy stosowny iloraz \frac{f(x+1)-f(x)}{1} przy najmniejszej możliwej wartości h.



MD1-3.2.swf

Przykład

Dla funkcji f(x)=x^2-4x+10 mamy

\aligned(\Delta f)(x)&=f(x+1)-f(x)=(x+1)^2-4(x+1)+10-(x^2-4x+10)\\ &=2x-3. \endaligned

\begin{array} {|c||c|c|c|c|c|c|c} \hline n&0&1&2&3&4&5&\ldots\\ \hline f(n)&10&7&6&7&10&15&\ldots\\ \hline (\Delta f)(n)&-3&-1&1&3&5&\ldots&\ldots\\ \hline \end{array}

Operator \Delta^n nazywamy n-tą iteracją operatora \Delta, gdzie


\aligned\Delta^0f&=f,\\ \Delta^{k+1}f&=\Delta(\Delta^k f). \endaligned


Przykład

Dla funkcji \displaystyle f(x)=\sum_{i=0}^x i^2 mamy:

  • \displaystyle (\Delta f)(x)=f(x+1)-f(x)=\sum_{i=0}^{x+1}i^2-\sum_{i=0}^x i^2=(x+1)^2,
  • \displaystyle (\Delta^2 f)(x)=(\Delta f)(x+1)-(\Delta f)(x)=(x+1)^2-x^2=2x+1,
  • \displaystyle (\Delta^3 f)(x)=(\Delta^2 f)(x+1)-(\Delta^2 f)(x)=2(x+1)+1-(2x+1)=2,
  • \displaystyle (\Delta^4 f)(x)=(\Delta^3 f)(x+1)-(\Delta^3 f)(x)=2-2=0.


\begin{array} {|c||c|c|c|c|c|c|c} \hline x&0&1&2&3&4&5&\ldots\\ \hline\hline f(x)&0&1&5&14&30&55&\ldots\\ \hline (\Delta f)(x)&1&4&9&16&25&\ldots\\ \hline (\Delta^2 f)(x)&3&5&7&9&\ldots\\ \hline (\Delta^3 f)(x)&2&2&2&\ldots\\ \hline (\Delta^4 f)(x)&0&0&\ldots\\ \hline \end{array}


Bardzo łatwo jest sprawdzić własności opisane w następnej obserwacji.

Obserwacja 4.1

Operator różnicowy \Delta jest operatorem liniowym, tzn.:


\aligned\Delta (c\cdot f)&=c\cdot\Delta f,\\ \Delta(f+g)&=\Delta f+\Delta g. \endaligned


Różniczkowanie jednomianów, czyli wielomianów typu x^k, jest bardzo proste: Dx^k=kx^{k-1} dla dowolnego k\geqslant1. Własność ta nie przenosi się jednak na operator \Delta.

Przykład

\aligned\ Dx^2&=2x,\\ \Delta x^2&=(x+1)^2-x^2=2x+1,\\ Dx^3&=3x^2,\\ \Delta x^3&=(x+1)^3-x^3=3x^2+3x+1, \endaligned


Na szczęście dla operatora różnicowego \Delta istnieją odpowiedniki jednomianów, czyli wielomianów o dowolnie dużych potęgach, które łatwo zróżnicować.

m-ta dolna silnia x to wielomian zmiennej x, zdefiniowany jako


x^{\underline{m}}=x(x-1)\ldots(x-m+1), dla m\geq 1


m-ta górna silnia x to wielomian zmiennej x, zdefiniowany jako


x^{\overline{m}}=x(x+1)\ldots(x+m-1), dla m\geq 1.


Dodatkowo przyjmujemy, że x^{\underline{0}}=x^{\overline{0}}=1.

Zauważmy, że w odróżnieniu od zwykłego potęgowania mamy tu


x^{\underline{m+n}} =x^{\underline{m}}(x-m)^{\underline{n}} =(x-n)^{\underline{m}}x^{\underline{n}}.


Obserwacja 4.2

Dla m\geq 1 zachodzi \Delta x^{\underline{m}}=mx^{\underline{m-1}}.

Dowód


\aligned\Delta x^{\underline{m}}&=(x+1)^{\underline{m}}-x^{\underline{m}}\\ &=(x+1)x(x-1)\ldots(x-m+2)-x(x-1)\ldots(x-m+1)\\ &=mx(x-1)\ldots(x-m+2)\\ &=mx^{\underline{m-1}}. \endaligned


image:End_of_proof.gif

Twierdzenie 4.3

Dowolny wielomian k-tego stopnia p(x) można jednoznacznie przedstawić w postaci \displaystyle \sum_{i=0}^ka_ix^{\underline{k}}, gdzie a_0=p(0), a_1=(\Delta p)(0), a_2=(\Delta^2 p)(0)/2 i ogólnie


\displaystyle p(x)=\sum_{i=0}^k\frac{(\Delta^i p)(0)}{i!}x^{\underline{i}}.


Twierdzenie to jest analogią Twierdzenia Taylora dla wielomianów. Dowód pomijamy w tym wykładzie. Korzysta on z faktu, iż ciąg dolnych silni jest bazą przestrzeni liniowej wielomianów.

Wykorzystując Twierdzenie 4.3 możemy szybko różnicować dowolny wielomian p(x) licząc jedynie kolejne różnice (\Delta^i p)(0). To z kolei dla wielomianu stopnia k sprowadza się do policzenia k+2 wartości początkowych p(0),\ldots, p(k+1).

Przykład

Aby policzyć \Delta (x^3-5x+13) najpierw wyrażamy nasz wielomian jako kombinacje dolnych silni. Do tego potrzebujemy współczynników z Twierdzenia 4.3.


\begin{array} {|c||c|c|c|c|c|c} \hline n&0&1&2&3&4&\ldots\\     \hline\hline n^3-5n+13&13&9&16&25&57&\ldots\\ \hline \Delta(n^3-5n+13)&-4&5&9&22&\ldots\\ \hline \Delta^2(n^3-5n+13)&9&4&11&\ldots\\ \hline \Delta^3(n^3-5n+13)&-5&\ldots\\ \hline \end{array}


Potem różnicujemy wykorzystując podstawowe własności \Delta.


n^3-5n+13 =\frac{-5}{6}n^{\underline{3}} +\frac{9}{2}n^{\underline{2}} +\frac{-4}{1}n^{\underline{1}} +\frac{13}{1}n^{\underline{0}} =-\frac{5}{6}n^{\underline{3}} + \frac{9}{2}n^{\underline{2}} -4n^{\underline{1}}+13,


by dostać


\aligned\Delta(n^3-5n+13)&=\Delta(-\frac{5}{6}n^{\underline{3}}+ \frac{9}{2}n^{\underline{2}}-4n^{\underline{1}}+13)\\ &=-\frac{5}{6}\cdot3n^{\underline{2}}+\frac{9}{2}\cdot2n^{\underline{1}}-4\cdot1\\ &=-\frac{5}{2}n^{\underline{2}}+9n^{\underline{1}}-4. \endaligned


W rachunku różniczkowym operator pochodnej D ma operator odwrotny - jest nim operator całki \displaystyle{\int}. Te dwa operatory powiązane są własnością:


g=Df wtedy i tylko wtedy, gdy \int g(x)dx=f(x)+C.


Zauważmy, że wychodząc od funkcji g:\mathbb{N}\longrightarrow\mathbb{R} i definiując f:\mathbb{N}\longrightarrow\mathbb{R} poprzez \displaystyle f(n) = \sum_{i=0}^{n-1} g(i) mamy \Delta f = g. Moglibyśmy więc zdefiniować sumę nieoznaczoną jako \displaystyle \sum g(x)\delta x = \sum_{i=0}^{n-1} g(i). Ponieważ \Delta f = \Delta(f+C) dla dowolnej stałej C, to - podobnie jak w przypadku całki nieoznaczonej - suma nieoznaczona zdefiniowana jest tylko z dokładnością do stałej addytywnej:


g=\Delta f wtedy i tylko wtedy, gdy \sum g(x)\delta x=f(x)+C.


Tak więc \sum g(x)\delta x (podobnie jak \displaystyle{\int g(x)dx}) jest klasą funkcji, których różnica (pochodna) równa jest g(x). Wyrażenie \sum g(x)\delta x to suma nieoznaczona funkcji g(x). Następujące własności sumy nieoznaczonej wynikają wprost z własności \Delta:

Obserwacja 4.4

Dla funkcji f, g : \mathbb{N} \longrightarrow \mathbb{R} oraz c \in \mathbb{R} zachodzi:

  • \sum c\cdot g(x)\delta x=c\cdot\sum g(x)\delta x,
  • \sum(f(x)+g(x))\delta x=\sum f(x)\delta x+\sum g(x)\delta x,
  • \sum x^{\underline{m}}\delta x=\frac{1}{m+1}x^{\underline{m+1}}, dla m\geqslant0.

Suma oznaczona funkcji g(x) o parametrach a,b\in\mathbb{N} to


\displaystyle \sum_a^b g(x)\delta x=f(b)-f(a),


dla funkcji f z klasy \sum g(x)\delta x, tzn. takiej, że g=\Delta f, czyli g(x)=f(x+1)-f(x). Zauważmy, ze definicja ta jest poprawna, tzn. nie zależy od wyboru funkcji f, jako stała, o którą dwie takie funkcje się różnią zniesie się przy przy odejmowaniu. Nie będzie to bardzo zaskakujące po udowodnieniu poniższych własności sumy oznaczonej, które są analogiami własności całki oznaczonej.

Obserwacja 4.5

Dla dowolnych całkowitych a,b,c zachodzi:

  • \displaystyle \sum_a^a g(x)\delta x=0,
  • \displaystyle \sum_a^{a+1} g(x)\delta x=g(a),
  • \displaystyle \sum_a^b g(x)\delta x=-\sum_b^ag(x)\delta x,
  • \displaystyle \sum_a^b g(x)\delta x+\sum_b^cg(x)\delta x=\sum_a^cg(x)\delta x,
  • \displaystyle \sum_a^b g(x)\delta x=\sum_{a\leq i<b}g(i), o ile tylko a\leq b.

Dowód

Pierwsze cztery własności wynikają natychmiast z definicji sumy oznaczonej. Dowód piątej poprowadzimy indukcyjnie z uwagi na b \geq a. Dla b=a jest to pierwszy punkt naszej obserwacji. Nadto \displaystyle \sum_a^{b+1} g(x)\delta x =\sum_a^{b} g(x)\delta x + \sum_b^{b+1} g(x)\delta = \sum_{a\leq i<b}g(i) + g(b) =\sum_{a\leq i<b+1}g(i), gdzie pierwsza równość jest konsekwencją punktu czwartego, a druga punktu drugiego.

image:End_of_proof.gif

Rachunek różnicowy w liczeniu sum skończonych

Wracamy teraz do rozważań o sumach skończonych. Zobaczymy, jak rachunek różnicowy może być pomocny w ich obliczaniu. Widzieliśmy już, że suma \displaystyle \sum_{a\leq i<b}g(i)to dokładnie f(b)-f(a), gdzie f jest sumą nieoznaczoną funkcji g, tzn. g(x)=f(x+1)-f(x). Wystarczy więc wyliczyć sumę nieoznaczoną. A proces ten jest bardzo podobny jak liczenie całek nieoznaczonych. W kolejnych przykładach zobaczymy, jak to można zrobić w praktyce.

Przykład

Dla policzenia sumy dolnych silni \displaystyle \sum_{i=0}^n i^{\underline{2}} odnotujmy najpierw, że skoro \Delta x^{\underline{3}}=3x^{\underline{2}}, to \displaystyle \sum x^{\underline{2}}\delta x=\frac{x^{\underline{3}}}{3}+C. Teraz już oczywiście \displaystyle \sum_{i=0}^n i^{\underline{2}} =\sum_0^{n+1}x^{\underline{2}}\delta x =\frac{(n+1)^{\underline{3}}}{3}-\frac{0^{\underline{3}}}{3} =\frac{(n+1)^{\underline{3}}}{3}.
Podobnie przy liczeniu \displaystyle \sum_{i=0}^n i^{\underline{k}}, gdzie k\geq 0, wykorzystujemy fakt, iż \Delta x^{\underline{k+1}}=(k+1)x^{\underline{k}} i dostajemy \displaystyle \sum_{i=0}^n i^{\underline{k}} =\sum_0^{n+1}x^{\underline{k}}\delta x =\frac{(n+1)^{\underline{k+1}}}{k+1}.

Przykład

Dla policzenia sumy sześcianów \displaystyle \sum_{i=0}^n i^3 potrzebujemy najpierw znaleźć sumę nieoznaczoną \displaystyle \sum x^3\delta x. W tym celu wykorzystujemy najpierw Twierdzenie 4.3 do przedstawienia wielomianu x^3 jako kombinacji liniowej dolnych silni, dla których znamy już sumy nieoznaczone. Liczymy więc współczynniki typu \frac{(\Delta^i x^3)(0)}{i!}:


\begin{array} {|c||c|c|c|c|c|c} \hline x&0&1&2&3&4&\ldots\\ \hline\hline x^3&0&1&8&27&64&\ldots\\ \hline \Delta x^3&1&7&19&37&\ldots\\ \hline \Delta^2 x^3&6&12&18&\ldots\\ \hline \Delta^3 x^3&6&6&\ldots\\ \hline \end{array}


skąd


x^3= \frac{6}{3!}x^{\underline{3}}+\frac{6}{2!}x^{\underline{2}}+\frac{1}{1!}x^{\underline{1}}+0 =x^{\underline{3}}+3x^{\underline{2}}+x^{\underline{1}},


a zatem


\sum x^3 =\sum (x^{\underline{3}}+3x^{\underline{2}}+x^{\underline{1}})\delta x =\frac{x^{\underline{4}}}{4}+x^{\underline{3}}+\frac{x^{\underline{2}}}{2}+C,


i wreszcie


\displaystyle \sum_{i=0}^n i^3 = \sum_0^{n+1}x^3\delta x  = \sum_{0}^{n+1} (x^{\underline{3}}+3x^{\underline{2}}+x^{\underline{1}})\delta x  = \frac{(n+1)^{\underline{4}}}{4}+(n+1)^{\underline{3}}+\frac{(n+1)^{\underline{2}}}{2}.


Uwalniając się teraz od dolnych silni dostajemy, że to ostatnie wyrażenie wynosi


\frac{(n+1)n(n-1)(n-2) + 4(n+1)n(n-1) + 2(n+1)n}{4}= \frac{(n+1)^2 n^2}{4}.


Rozszerzymy teraz pojęcie dolnej silni na ujemne wykładniki kładąc :


\displaystyle x^{\underline{-m}}=\frac{1}{(x+1)(x+2)\ldots(x+m)}, dla m>0.


Prawa dla dolnej silni, które odnotowaliśmy dla wykładników naturalnych są zachowane. W szczególności mamy:

Obserwacja 4.6

Dla dowolnych m,n\in \mathbb{Z} zachodzi:

  • x^{\underline{m+n}}=x^{\underline{m}}(x-m)^{\underline{n}},
  • \Delta x^{\underline{m}}=m\cdot x^{\underline{m-1}},
  • \sum x^{\underline{m}}\delta x=\frac{x^{m+1}}{m+1}+C, dla m\neq-1.

Dowód tej obserwacji zostawiamy jako ćwiczenie. Zajmiemy się natomiast jedynym przypadkiem, którego nie potrafimy jeszcze sumować, tzn. wyrażeniem \sum x^{\underline{-1}}\delta x. Oczywiście x^{\underline{-1}} to \frac{1}{x+1}. Widzieliśmy również, że suma postaci \displaystyle \sum_{i=0}^n \frac{1}{i+1} to (n+1)-sza liczba harmoniczna H_{n+1} oraz zachowuję się podobnie do logarytmu:


\frac{\left\lfloor \lg{n}\right\rfloor+1}{2} \leq H_n \leq \left\lfloor \lg{n}\right\rfloor+1.


Z rachunku całkowego wiemy natomiast, że \int x^{-1}dx=\ln{x}+C. Następna obserwacja pokazuje, że podobieństwo to nie jest przypadkowe:

Obserwacja 4.7

\Delta H_x=x^{\underline{-1}} oraz \sum x^{\underline{-1}}\delta x=H_x+C.

Dowód

Mamy


\Delta H_x =\Delta(1+\frac{1}{2}+\ldots+\frac{1}{x}) =(1+\ldots+\frac{1}{x}+\frac{1}{x+1})-(1+\ldots+\frac{1}{x}) =\frac{1}{x+1}=x^{\underline{-1}},


skąd natychmiast \sum x^{\underline{-1}}\delta x=H_x+C.

image:End_of_proof.gif

Z kolei dyskretnym odpowiednikiem funkcji wykładniczej e^x, która nie zmienia się przy różniczkowaniu, jest funkcja 2^x:

Obserwacja 4.8

Dla liczby rzeczywistej c\neq1 mamy \Delta c^x=(c-1)c^x oraz \sum c^x\delta x=\frac{c^x}{c-1}+C. W szczególności \Delta 2^x=2^x oraz \sum 2^x\delta x= 2^x+C.

Dowód

Istotnie, \Delta c^x=c^{x+1}-c^x=(c-1)c^x, skąd (jeśli tylko c\neq1) dostajemy natychmiast \sum c^x\delta x=\frac{c^x}{c-1}+C.

image:End_of_proof.gif

Przykład

Używając rachunku różnicowego policzymy teraz sumę skończonego ciągu geometrycznego \sum_{i=0}^n abq^i z ilorazem q\neq 1. Obserwacje 4.4 i 4.8 dają:


\displaystyle \sum aq^x\delta x=a\sum q^x\delta x=a\frac{q^x}{q-1}+C.


A zatem:


\displaystyle \sum_{i=0}^n aq^i=a\frac{q^n}{q-1}-a\frac{q^0}{q-1}=a\frac{q^n-1}{q-1}.


Sumowanie przez części

Poprzez analogię do rachunku różnicowego zastosujmy operator różnicowy do iloczynu funkcji


\aligned\Delta(f(x)g(x))&=f(x+1)g(x+1)-f(x)g(x)\\ &=f(x+1)g(x+1)-f(x)g(x+1)+f(x)g(x+1)-f(x)g(x)\\ &=g(x+1)\Delta f+f(x)\Delta g(x). \endaligned


Dostajemy stąd natychmiast następującą regułę sumowania przez części

Obserwacja 4.9

\displaystyle \sum f(x)\cdot\Delta g(x)\delta x = f(x)\cdot g(x)-\sum (\Delta f)(x)\cdot g(x+1)\delta x.

Przykład

Dla policzenia sumy \displaystyle \sum_{i=0}^n i2^i, wyznaczamy najpierw (przez części) sumę nieoznaczoną \displaystyle \sum (x2^x)\delta x. Jest to łatwe, jako że 2^x=\Delta 2^x, więc


\aligned\sum (x2^x)\delta x &=x2^x-\sum ((\Delta x)2^{x+1})\delta x \\ &=x2^x-\sum (1 \cdot 2^{x+1})\delta x\\ &=x2^x-2^{x+1}+C=(x-2)2^x+C. \endaligned


Teraz mamy już


\displaystyle \sum_{i=0}^ni2^i=\sum_0^{n+1}x2^x\delta x=(n+1-2)2^{n+1}-(0-2)2^0=(n-1)2^{n+1}-2.