Informatyka MIMUW

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 \rightarrow 0}\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$.

Przykład

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

$\begin{align*}(\Delta f)(x) & =f(x+1)-f(x)=(x+1)^2-4(x+1)+10-(x^2-4x+10) \\ & =2x-3. \end{align*}$

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

$\begin{align*}\Delta^0f & =f, \\ \Delta^{k+1}f & =\Delta(\Delta^k f). \end{align*}$

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

$\begin{align*}\Delta (c\cdot f) & =c\cdot\Delta f, \\ \Delta(f+g) & =\Delta f+\Delta g. \end{align*}$

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

Przykład

$\begin{align*}\ 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, \end{align*}$

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

$\begin{align*}\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}}. \end{align*}$

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ć

$\begin{align*}\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. \end{align*}$

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

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.

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

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

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

$\begin{align*}\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). \end{align*}$

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

$\begin{align*}\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. \end{align*}$
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.$