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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wstęp

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



Czasami stosowana jest ogólniejsza notacja , gdzie jest skończonym zbiorem indeksów. Jeśli jest pusty to suma ma
wartość .

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



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 :



Zauważmy, że



Carl Friedrich Gauss (1777-1855)
Zobacz biografię

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



Zatem , czyli obliczana suma jest średnią arytmetyczną pierwszego i ostatniego 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 poznaliśmy w wykładzie o indukcji. Pokazaliśmy tam, że



Tym razem jesteśmy zainteresowani sumami postaci



których pierwsze wartości przedstawia tabela:



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:



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:



Zaburzanie

Gdy interesują nas skończone sumy odcinków początkowych ciągu , czyli sumy postaci . Metoda zaburzania polega na obliczeniu wartości za pomocą na dwa różne sposoby: na ogół wydzielając pierwszy i ostatni składnik sumy tzn.:



Jeśli uda się nam ostatnią sumę wyrazić za pomocą , 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ę skończonego ciągu geometrycznego dla , . Zgodnie z ogólnym schematem zaburzania mamy:



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


dla

Przykład

Tym razem jesteśmy zainteresowani sumą ,która przyjmuje wartości:



Licząc przez zaburzanie dostajemy:



gdzie suma skończonego ciągu geometrycznego została wyliczona w poprzednim przykładzie. Zatem ostatecznie



Przykład

Spróbujmy policzyć jeszcze raz sumę kwadratów ale tym razem przez zaburzanie.



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



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



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 , zdefiniowany jako



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



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

MD1-3.2.swf

Przykład

Dla funkcji mamy

Operator nazywamy n-tą iteracją operatora , gdzie



Przykład

Dla funkcji mamy:

  • \displaystyle ,
  • \displaystyle ,
  • \displaystyle ,
  • \displaystyle .



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

Obserwacja 4.1

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



Różniczkowanie jednomianów, czyli wielomianów typu , jest bardzo proste: dla dowolnego . Własność ta nie przenosi się jednak na operator .

Przykład


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

-ta dolna silnia to wielomian zmiennej , zdefiniowany jako


dla


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


dla


Dodatkowo przyjmujemy, że .

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



Obserwacja 4.2

Dla zachodzi

Dowód



End of proof.gif

Twierdzenie 4.3

Dowolny wielomian -tego stopnia można jednoznacznie przedstawić w postaci , gdzie , , i ogólnie



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 licząc jedynie kolejne różnice . To z kolei dla wielomianu stopnia sprowadza się do policzenia wartości początkowych .

Przykład

Aby policzyć najpierw wyrażamy nasz wielomian jako kombinacje dolnych silni. Do tego potrzebujemy współczynników z Twierdzenia 4.3.



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



by dostać



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


wtedy i tylko wtedy, gdy


Zauważmy, że wychodząc od funkcji i definiując poprzez mamy . Moglibyśmy więc zdefiniować sumę nieoznaczoną jako . Ponieważ dla dowolnej stałej , to - podobnie jak w przypadku całki nieoznaczonej - suma nieoznaczona zdefiniowana jest tylko z dokładnością do stałej addytywnej:


wtedy i tylko wtedy, gdy


Tak więc (podobnie jak ) jest klasą funkcji, których różnica (pochodna) równa jest . Wyrażenie to suma nieoznaczona funkcji . Następujące własności sumy nieoznaczonej wynikają wprost z własności :

Obserwacja 4.4

Dla funkcji oraz zachodzi:

  • ,
  • ,
  • , dla .

Suma oznaczona funkcji o parametrach to



dla funkcji z klasy , tzn. takiej, że , czyli . Zauważmy, ze definicja ta jest poprawna, tzn. nie zależy od wyboru funkcji , 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 zachodzi:

  • ,
  • ,
  • ,
  • ,
  • , o ile tylko .

Dowód

Pierwsze cztery własności wynikają natychmiast z definicji sumy oznaczonej. Dowód piątej poprowadzimy indukcyjnie z uwagi na . Dla jest to pierwszy punkt naszej obserwacji. Nadto , gdzie pierwsza równość jest konsekwencją punktu czwartego, a druga punktu drugiego.

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 to dokładnie , gdzie jest sumą nieoznaczoną funkcji , tzn. . 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 odnotujmy najpierw, że skoro , to . Teraz już oczywiście .
Podobnie przy liczeniu , gdzie , wykorzystujemy fakt, iż i dostajemy .

Przykład

Dla policzenia sumy sześcianów potrzebujemy najpierw znaleźć sumę nieoznaczoną . W tym celu wykorzystujemy najpierw Twierdzenie 4.3 do przedstawienia wielomianu jako kombinacji liniowej dolnych silni, dla których znamy już sumy nieoznaczone. Liczymy więc współczynniki typu :



skąd



a zatem



i wreszcie



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



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


dla


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

  • ,
  • ,
  • , dla .

Dowód tej obserwacji zostawiamy jako ćwiczenie. Zajmiemy się natomiast jedynym przypadkiem, którego nie potrafimy jeszcze sumować, tzn. wyrażeniem . Oczywiście to . Widzieliśmy również, że suma postaci to -sza liczba harmoniczna oraz zachowuję się podobnie do logarytmu:



Z rachunku całkowego wiemy natomiast, że . Następna obserwacja pokazuje, że podobieństwo to nie jest przypadkowe:

Obserwacja 4.7

oraz .

Dowód

Mamy



skąd natychmiast .

End of proof.gif

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

Obserwacja 4.8

Dla liczby rzeczywistej mamy oraz . W szczególności oraz .

Dowód

Istotnie, , skąd (jeśli tylko ) dostajemy natychmiast .

End of proof.gif

Przykład

Używając rachunku różnicowego policzymy teraz sumę skończonego ciągu geometrycznego z ilorazem . Obserwacje 4.4 i 4.8 dają:



A zatem:



Sumowanie przez części

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



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

Obserwacja 4.9

.

Przykład

Dla policzenia sumy , wyznaczamy najpierw (przez części) sumę nieoznaczoną . Jest to łatwe, jako że , więc



Teraz mamy już