Matematyka dyskretna 1/Ćwiczenia 4: Sumy skończone i rachunek różnicowy

Sumy skończone i rachunek różnicowy

Ćwiczenie 1

Znajdź postać zwartą sumy $\sum _{i=0}^{n-1}\frac{1}{(i+1)(i+2)}$.

Wskazówka

Zauważ, że sumowane czynniki to dolna silnia $i^{\underset{\_}{-2}}$.

Rozwiązanie

Ponieważ $\sum _0^n{x}^{\underset{\_}{-2}}\delta x=-x^{\underset{\_}{-1}}+C$, to mamy:

$\sum _{i=0}^{n-1}\frac{1}{(i+1)(i+2)}=\sum _0^n{x}^{\underset{\_}{-2}}\delta x=-n^{\underset{\_}{-1}}+0^{-1}=1-\frac{1}{n+1}=\frac{n}{n+1}$

Ćwiczenie 2

Znajdź postać zwartą sumy $\sum _{i=0}^n(-1{)}^i{i}^2$.

Wskazówka

Pogrupuj składniki sumy parami.

Rozwiązanie

Załóżmy najpierw, że $n$ jest parzysta wtedy

$\begin{array}{rl}\sum _{i=0}^n(-1{)}^i{i}^2& =\sum _{i=0}^{\frac{n}{2}-1}((2i{)}^2-(2i+1{)}^2)+n^2\\ & =n^2-\sum _{i=0}^{\frac{n}{2}-1}(4i+1)\\ & =n^2-(\frac{n}{2}(n-1))\\ & =\frac{n(n+1)}{2}.\end{array}$

Natomiast wartość sumy dla liczby nieparzystej $n$ to

$\sum _{i=0}^n(-1{)}^i{i}^2=\sum _{i=0}^{n-1}(-1{)}^i{i}^2-n^2=\frac{n(n-1)}{2}-n^2=-\frac{n(n+1)}{2}$

Podsumowując

$\sum _{i=0}^n(-1{)}^i{i}^2=(-1{)}^n\frac{n(n+1)}{2}$

Ćwiczenie 3

Znajdź postać zwartą sumy $\sum _{i=0}^n(-1{)}^i\frac{i}{4i^2-1}$.

Wskazówka

Rozbij $\frac{i}{4i^2-1}$ na sumę ułamków prostych $\frac{i}{4i^2-1}=\frac{1}{4}(\frac{1}{2i-1}+\frac{1}{2i+1})$.

Rozwiązanie

Korzystając z rozbicia $\frac{i}{4i^2-1}=\frac{1}{4}(\frac{1}{2i-1}+\frac{1}{2i+1})$ widzimy, że w naprzemiennej sumie

$\sum _{i=0}^n(-1{)}^i\frac{i}{4i^2-1}=\frac{1}{4}\sum _{i=0}^n(-1{)}^i(\frac{1}{2i-1}+\frac{1}{2i+1})$

wszytkie wyrazy, oprócz pierwszego i ostatniego się znoszą, skąd:

$\sum _{i=0}^n(-1{)}^i\frac{i}{4i^2-1}=\frac{1}{4}(-1+\frac{(-1{)}^n}{2n+1})$

Ćwiczenie 4

Znajdź postać zwartą sumy $\sum _{i=0}^{n-1}i{H}_i$.

Wskazówka

Spróbuj sumować przez części.

Rozwiązanie

Wyznaczmy najpierw sumę nieoznaczoną $\sum x{H}_x\delta x$ korzystając z reguły sumowania przez części dla $f(x)=H_x$ i $(\mathrm{\Delta }g)(x)=x$. Mamy wtedy $(\mathrm{\Delta }f)(x)=x^{\underset{\_}{-1}}$ i $g(x)=\frac{x^{\underset{\_}{2}}}{2}$. A zatem:

$\begin{array}{rl}\sum x{H}_x\delta x& =\frac{x^{\underset{\_}{2}}}{2}{H}_x-\sum \frac{(x+1{)}^{\underset{\_}{2}}}{2}{x}^{\underset{\_}{-1}}\delta x\\ & =\frac{x^{\underset{\_}{2}}}{2}{H}_x-\frac{1}{2}\sum x^{\underset{\_}{1}}\delta x\\ & =\frac{x^{\underset{\_}{2}}}{2}{H}_x-\frac{x^{\underset{\_}{2}}}{4}+C.\end{array}$

Możemy teraz policzyć naszą sumę:

$\sum _{i=0}^{n-1}i{H}_i=\sum _0^{n}x{H}_x\delta x=\frac{n^{\underset{\_}{2}}}{2}(H_n-\frac{1}{2})=\frac{n(n-1)(2H_n-1)}{4}$

Ćwiczenie 5

Znajdź postać zwartą sumy $\sum _{i=0}^{n-1}i(i-1)3^i$.

Wskazówka

Dwukrotnie skorzystaj z reguły sumowania przez części.

Rozwiązanie

Najpierw policzymy sumę nieoznaczoną $\sum x^{\underset{\_}{2}}{3}^x\delta x$:

$\begin{array}{rl}\sum x^{\underset{\_}{2}}{3}^x\delta x& =x^{\underset{\_}{2}}\frac{3^x}{2}-\sum 2x^{\underset{\_}{1}}\frac{3^{x+1}}{2}\delta x\\ & =\frac{1}{2}{x}^{\underset{\_}{2}}{3}^x-3\sum x^{\underset{\_}{1}}{3}^x\delta x\\ & =\frac{1}{2}{x}^{\underset{\_}{2}}{3}^x-3(x\frac{3^x}{2}-\sum \frac{3^{x+1}}{2}\delta x)\\ & =\frac{1}{2}{x}^{\underset{\_}{2}}{3}^x-\frac{3}{2}x{3}^x+\frac{9}{2}\sum 3^x\delta x\\ & =\frac{1}{2}{x}^{\underset{\_}{2}}{3}^x-\frac{3}{2}x{3}^x+\frac{9}{4}{3}^x+C.\end{array}$

A zatem nasza suma wynosi:

$\sum _{i=0}^{n-1}i(i-1)3^i=\sum _0^n{x}^{\underset{\_}{2}}{3}^x\delta x=\frac{1}{2}{n}^{\underset{\_}{2}}{3}^n-\frac{3}{2}n{3}^n+\frac{9}{4}{3}^n-\frac{9}{4}=\frac{3^n(2n^2-8n+9)-9}{4}$

Ćwiczenie 6

Czy warunek $(\mathrm{\Delta }f)(x)=f(x)$ implikuje, że $f(x)=2^x$?

Rozwiązanie

Warunek $(\mathrm{\Delta }f)(x)=f(x)$ oznacza, że $f(x+1)=2f(x)$. Oczywiście ten warunek spełnia funkcja $2^x$, ale także każda inna postaci $c\cdot 2^x$ dla $c\in \mathbb{ℝ}$.

Ćwiczenie 7

Ciąg Golomba $g_1,g_2,g_3,\dots$ to jedyny niemalejący ciąg liczb naturalnych, w którym każda liczba $i$ występuje dokładnie $g_i$ razy. Oto lista kilku początkowych wartości:

$\begin{array}{ccccccccccccccccc}n& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16\\ g_n& 1& 2& 2& 3& 3& 4& 4& 4& 5& 5& 5& 6& 6& 6& 6& 7\end{array}$

Niech $G(n)$ będzie największą liczbą $m$ taką, że $g_m=n$. Pokaż, że:

• $G(n)=\sum _{i=1}^n{g}_i$,
• $G(G(n))=\sum _{i=1}^{n}i\cdot g_i$.

Wskazówka

Rozważ $(\mathrm{\Delta }G)(n)=G(n+1)-G(n)$, a następnie różnicę $G(G(n+1))-G(G(n))$.

Rozwiązanie

Oczywiście $G(1)=g_1=1$. Ponieważ $G(n+1)$ jest ostatnim miejscem, na którym pojawia się $n+1$, a wartość $n+1$ pojawia się $g_{n+1}$ razy, to $G(n+1)=G(n)+g_{n+1}$. To dowodzi pierwszego punktu.

Dla dowodu drugiego punktu, zauważmy, że z pierwszego punktu dostajemy:

$G(G(n+1))-G(G(n))=\sum _{i=G(n)+1}^{G(G(n+1))}{g}_i$

Ale oczywiście dla $G(n)<i⩽G(G(n+1))$ wszystkie wyrazy $g_i$ są równe $n+1$. Zatem

$G(G(n+1))-G(G(n))=\sum _{i=G(n)+1}^{G(G(n+1))}{g}_i=(n+1)\cdot (G(n+1)-G(n))$$=(n+1)\cdot g_{n+1}$,

co daje zależność opisaną w punkcie drugim.