Rachunek różnicowy w obliczaniu sum.

Zbiór informacji o elementarnych zagadnieniach matematyki, klasyfikowanych najczęściej jako "ciekawostki" właśnie...
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Rachunek różnicowy w obliczaniu sum.

Post autor: »

RACHUNEK RÓŻNICOWY
Rachunek różnicowy to bardzo silne narzędzie do obliczania sum (tzn. przedstawiania ich w postaci zwartej). Metody rachunku różnicowego są zaczerpnięte przez analogię z analizy matematycznej: odpowiednikiem całkowania jest sumowanie, a odpowiednikiem liczenia pochodnych jest operator różnicowy.

0. Wstępne pojęcia.
Dolna silnia (potęga ubywająca)
Dla \(\displaystyle{ n>0}\) definiujemy:
\(\displaystyle{ x^{\underline{n}}=x \cdot (x-1) \cdot \ldots \cdot (x-n+1)}\)
\(\displaystyle{ x^{\underline{-n}}=\frac{1}{(x+1) \cdot (x+2) \cdot \ldots \cdot (x+n)}}\)
oraz \(\displaystyle{ x^{\underline{0}}=1}\)

Liczba harmoniczna
Dla \(\displaystyle{ n>0}\) definiujemy:
\(\displaystyle{ H_n=1+\frac 12 +\frac 13 +\ldots \frac 1n}\)
oraz \(\displaystyle{ H_0=0}\)
1. Operator różnicowy.
W analizie pochodną definiujemy jako \(\displaystyle{ Df(x)=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}}\). W matematyce dyskretnej "możliwie małym" \(\displaystyle{ h}\) jest \(\displaystyle{ h=1}\), dlatego definiujemy operator różnicowy jako:
\(\displaystyle{ \boxed{\boxed{\Delta f(x)=f(x+1)-f(x)}}}\)
Tabela wartości operatora \(\displaystyle{ \Delta}\)
\(\displaystyle{ \begin{array}{|c|c|c|}\hline
\textrm{funkcja} & \textrm{wartość operatora } \Delta &\textrm{odpowiednik \\ w analizie}\\ \hline
x^{\underline{n}}&nx^{\underline{n-1}}&Dx^n=nx^{n-1}\\ \hline
H_x & x^{\underline{-1}}=\frac{1}{x+1}&D\ln x = x^{-1}=\frac 1x\\ \hline
2^x & 2^x & De^x=e^x\\ \hline
c^x & (c-1)c^x&Da^x=\ln a \cdot a^x\\ \hline
{x \choose k} & {x \choose k-1}& \textrm{brak}\\ \hline
\end{array}}\)
Dowody wzorów z tabeli:    
2. Sumowanie w rachunku różnicowym.
Będziemy oznaczać:
\(\displaystyle{ \sum_{k=a}^{b-1}f(k)=\sum_{a}^{b}f(k)\delta k}\)
przy czym symbol \(\displaystyle{ \delta k}\) najczęściej będziemy pomijać (podobnie jak przy całkowaniu często pomija się symbol \(\displaystyle{ \mbox{d}x}\)).
Warto zwrócić uwagę, że w nowym zapisie górny zakres sumowania jest o jeden większy niż w zapisie tradycyjnym.
Zasadnicze twierdzenie rachunku różnicowego
\(\displaystyle{ \boxed{\boxed{\sum_{a}^{b}\Delta f(k)=f(k)|_a^b=f(b)-f(a)}}}\)
Dowód:    
Analogiczny wzór w analizie to \(\displaystyle{ \int_a ^bf'(x)=f(x)|_a^b}\).
Widać zatem, że tak jak w analizie operacją odwrotną do liczenia pochodnych jest całkowanie, tak w rachunku różnicowym operacją odwrotną do \(\displaystyle{ \Delta}\) jest sumowanie. Podobnie jak w analizie tabelę całek funkcji elementarnych dostajemy przez "odwrócenie" tabeli pochodnych, tak w rachunku różnicowym tabelę sum otrzymamy przez odwrócenie tablicy wartości operatora \(\displaystyle{ \Delta}\)
Tabela sum (funkcji pierwotnych operatora \(\displaystyle{ \Delta}\))
\(\displaystyle{ \begin{array}{|c|c|c|}\hline
\textrm{funkcja} & \textrm{wartość sumy } \Sigma &\textrm{odpowiednik \\ w analizie}\\ \hline
x^{\underline{n}}&\frac{x^{\underline{n+1}}}{n+1} \textrm{ dla } n\neq -1&\int x^n=\frac{x^{n+1}}{n+1}\\ \hline
x^{\underline{-1}}&H_x&\int \frac 1x = \ln x\\ \hline
2^x & 2^x & \int e^x=e^x\\ \hline
c^x & \frac{c^x}{c-1}&\int a^x=\frac{a^x}{\ln a}\\ \hline
{x \choose k} & {x \choose k+1}& \textrm{brak}\\ \hline
\end{array}}\)
Przykłady zastosowań:
  • \(\displaystyle{ \sum_{k=0}^{n}q^k=\sum_{0}^{n+1}q^k=\frac{q^k}{q-1}|_0^{n+1}=\frac{q^{n+1}}{q-1}-\frac{q^0}{q-1}=\frac{q^{n+1}-1}{q-1}\\}\)
  • \(\displaystyle{ \sum_{k=1}^n\frac{1}{k(k+1)}=\sum_{k=0}^{n-1}\frac{1}{(k+1)(k+2)}=\sum_{0}^{n}k^{\underline{-2}}=}\)
    \(\displaystyle{ =\frac{k^{\underline{-1}}}{-1}|_0^n=\frac{-1}{k+1}|_0^n=-\frac{1}{1+n}-(-1)=\frac{n}{n+1}}\)
  • \(\displaystyle{ \sum_{k=0}^{n}k^2=\sum_{k=0}^{n}(k(k-1)+k)=\sum_{0}^{n+1}(k^{\underline{2}}+k^{\underline{1}})=\left( \frac{k^{\underline{3}}}{3}+\frac{k^{\underline{2}}}{2}\right)|_0^{n+1}=}\)
    \(\displaystyle{ =\left( \frac{k(k-1)(k-2)}{3}+\frac{k(k-1)}{2}\right)|_0^{n+1}=
    \left( \frac{k(k-1)(2k-1)}{6}\right)|_0^{n+1}=\frac{n(n+1)(2n+1)}{6}}\)
3. Sumowanie przez części.
W analizie wzór na całkowanie przez części \(\displaystyle{ \int fg'=fg-\int f'g}\) dostajemy przez wykorzystanie wzoru na pochodną iloczynu \(\displaystyle{ (fg)'=f'g+fg'}\). Przeprowadźmy podobny rachunek dla operatora różnicowego:
\(\displaystyle{ \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)= \\ =
(f(x+1)-f(x))\cdot g(x+1) +f(x)\cdot (g(x+1)-g(x))= \\ =\Delta f(x) \cdot g(x+1) + f(x) \cdot \Delta g(x)}\)

Jeśli wprowadzimy operator przesunięcia \(\displaystyle{ Eg(x):=g(x+1)}\), to otrzymany wzór można zapisać jako:
\(\displaystyle{ \Delta f(x)g(x)=\Delta f(x) \cdot Eg(x)+f(x)\cdot \Delta g(x)}\)
skąd po zsumowaniu:
\(\displaystyle{ f(x)g(x)|_a^b=\sum_a^b\Delta f(x) \cdot Eg(x)+\sum_a^bf(x)\cdot \Delta g(x)}\)
i przeniesieniu na drugą stronę otrzymujemy:
Wzór na sumowanie przez części
\(\displaystyle{ \boxed{\boxed{\sum_a^bf(k)\Delta g(k)=f(k)g(k)|_a^b - \sum_a^b\Delta f(k)Eg(k)}}}\)
Przykłady zastosowań:
  • \(\displaystyle{ \sum_{k=0}^{n}k2^k=\sum_{0}^{n+1}k^{\underline{1}}2^k= \ldots}\)

    \(\displaystyle{ \begin{array}{|cc|}
    f(k)=k^{\underline{1}} &\Delta f(k)= 1\\
    \Delta g(k)=2^k & g(k)=2^k\\
    & Eg(k)=2^{k+1}\end{array}}\)


    \(\displaystyle{ \ldots = k2^k|_0^{n+1}- 2\sum_{0}^{n+1}2^k= (n+1)2^{n+1}-2 \cdot 2^k|_0^{n+1}= \\ =(n+1)2^{n+1}-2 \cdot \left( 2^{n+1}-1 \right)=(n-1)2^{n+1}+2}\)
  • \(\displaystyle{ \sum_{k=1}^{n}H_k=\sum_{1}^{n+1}1\cdot H_k =\ldots}\)

    \(\displaystyle{ \begin{array}{|cc|}
    f(k)=H_k &\Delta f(k)= \frac{1}{k+1}\\
    \Delta g(k)=1 & g(k)=k\\
    & Eg(k)=k+1\end{array}}\)


    \(\displaystyle{ \ldots = kH_k|_1^{n+1}-\sum_{1}^{n+1}1=(n+1)H_{n+1}-1-n=\\ =
    (n+1)\left( H_n+\frac{1}{n+1}\right) -n-1=(n+1)H_n-n}\)
  • \(\displaystyle{ \sum_{k=0}^{n} {k \choose m} H_k=\sum_{0}^{n+1}{k \choose m} H_k=\ldots}\)

    \(\displaystyle{ \begin{array}{|cc|}
    f(k)=H_k &\Delta f(k)= \frac{1}{k+1}\\
    \Delta g(k)= {k \choose m} & g(k)={k\choose m+1}\\
    & Eg(k)={k+1\choose m+1}\end{array}}\)


    \(\displaystyle{ \ldots = {k\choose m+1}H_k|_{0}^{n+1}-\sum_{0}^{n+1}\frac{1}{k+1}{k+1\choose m+1}= \\ = {n+1\choose m+1}H_{n+1}-\sum_{0}^{n+1}\frac{1}{m+1}{k\choose m}= \\ =
    {n+1\choose m+1}H_{n+1}-\frac{1}{m+1}\cdot {k \choose m+1}|_0^{n+1}= \\ =
    {n+1\choose m+1}\left( H_{n}+\frac{1}{n+1}\right) -\frac{1}{m+1}\cdot {n+1\choose m+1}= \\ =
    {n+1\choose m+1}\left( H_n+\frac{1}{n+1}-\frac{1}{m+1}\right)}\)

    (skorzystano ze wzoru \(\displaystyle{ q\cdot {p\choose q}=p\cdot {p-1\choose q-1}}\))
    Dla \(\displaystyle{ m=0}\) dostajemy poprzedni przykład.
4. Kilka praktycznych rad.
  • Zawsze należy pamiętać o dodaniu jedynki do górnego wskaźnika sumowania (gdy przechodzimy na zapis różnicowy) oraz o policzeniu \(\displaystyle{ \underline{Eg(k)}}\) w sumowaniu przez części!
  • Zawsze (a już na pewno w bardziej skomplikowanych sumach) warto sprawdzić czy wynik zgadza się dla małych \(\displaystyle{ n}\). Przykładowo suma \(\displaystyle{ \sum_{k=0}^nk2^k}\) powinna dawać wynik \(\displaystyle{ 2}\) dla \(\displaystyle{ n=1}\) oraz \(\displaystyle{ 10}\) dla \(\displaystyle{ n=2}\). Takie same wyniki daje otrzymany wzór \(\displaystyle{ (n-1)2^{n+1}+2}\), a zatem (najprawdopodobniej) nie został nigdzie zrobiony błąd rachunkowy.
  • Jeśli w jakiejś sumie nie wiadomo jak zastosować sumowanie przez części, można napisać sobie analogiczną całkę i zobaczyć jak się ją liczy przez części (to rada dla biegłych w całkowaniu). Na przykład przy liczeniu sumy \(\displaystyle{ \sum_{k=1}^{n}H_k}\) można napisać sobie całkę \(\displaystyle{ \int \ln x}\) (bo ciągłym odpowiednikiem liczby harmonicznej jest logarytm naturalny, co wynika z tabel). I sprawdzić jak liczy się tę całkę: \(\displaystyle{ f=\ln x, f'=\frac 1x, g'=1, g=x}\), więc całka to \(\displaystyle{ \int \ln x = x\ln x-\int 1}\). Tak więc w sumie należy analogicznie przyjąć \(\displaystyle{ f(k)=H_k,\Delta g(k)=1}\).
  • W przypadku sumy \(\displaystyle{ \sum_{k=0}^nk^2}\) skorzystaliśmy z tego, że \(\displaystyle{ k^2=k^{\underline{2}}+k^{\underline{1}}}\). Analogiczny wzór na \(\displaystyle{ k^n}\) można by wyprowadzić dla dowolnego \(\displaystyle{ n}\), ale jeśli znów robilibyśmy to na piechotę, to moglibyśmy zaliczyć się na śmierć (jak ktoś ma dużo wolnego czasu, może ręcznie policzyć ile będzie równe \(\displaystyle{ k^5}\), by się przekonać). Na szczęście nie trzeba tego robić na piechotę, bowiem prawdziwy jest wzór:
    \(\displaystyle{ k^n= \sum_{i=0}^{n}\left\{ \begin{matrix}n\\i\\\end{matrix}\right\} k^{\underline{i}}}\)
    gdzie \(\displaystyle{ \left\{ \begin{matrix}n\\i\\\end{matrix}\right\}}\) to liczba Stirlinga drugiego rodzaju.
    Stąd na przykład:
    \(\displaystyle{ k^5=k^{\underline{5}}+10k^{\underline{4}}+25k^{\underline{3}}+15k^{\underline{2}}+k^{\underline{1}}}\)
(C) by Qń

Wszelkie uwagi, komentarze i pytania proszę przesyłać w wiadomości prywatnej
ODPOWIEDZ