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

From Studia Informatyczne

Sumy skończone i rachunek różnicowy

Ćwiczenie 1

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

Wskazówka

Zauważ, że sumowane czynniki to dolna silnia \displaystyle i^{\underline{-2}}.

Rozwiązanie

Ponieważ \displaystyle \sum_0^nx^{\underline{-2}}\delta x=-x^{\underline{-1}}+C, to mamy:


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


Ćwiczenie 2

Znajdź postać zwartą sumy \displaystyle \sum_{i=0}^n(-1)^ii^2.

Wskazówka

Pogrupuj składniki sumy parami.

Rozwiązanie

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


\displaystyle \aligned \sum_{i=0}^n(-1)^ii^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-\left( \frac{n}{2}(n-1) \right)\\ &=\frac{n(n+1)}{2}. \endaligned


Natomiast wartość sumy dla liczby nieparzystej \displaystyle n to


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


\displaystyle \sum_{i=0}^n(-1)^ii^2=(-1)^n\frac{n(n+1)}{2}.


Ćwiczenie 3

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

Wskazówka

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

Rozwiązanie

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


\displaystyle \sum_{i=0}^n(-1)^i\frac{i}{4i^2-1}  = \frac{1}{4}\sum_{i=0}^n (-1)^i\left( \frac{1}{2i-1}+\frac{1}{2i+1} \right)


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


\displaystyle \sum_{i=0}^n(-1)^i\frac{i}{4i^2-1} =\frac{1}{4}\left( -1+\frac{(-1)^n}{2n+1} \right).


Ćwiczenie 4

Znajdź postać zwartą sumy \displaystyle \sum_{i=0}^{n-1}iH_i.

Wskazówka

Spróbuj sumować przez części.

Rozwiązanie

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


\displaystyle \aligned \sum xH_x\delta x&=\frac{x^{\underline{2}}}{2}H_x-\sum\frac{(x+1)^{\underline{2}}}{2}x^{\underline{-1}}\delta x\\ &=\frac{x^{\underline{2}}}{2}H_x-\frac{1}{2}\sum x^{\underline{1}}\delta x\\ &=\frac{x^{\underline{2}}}{2}H_x-\frac{x^{\underline{2}}}{4}+C. \endaligned


Możemy teraz policzyć naszą sumę:


\displaystyle \sum_{i=0}^{n-1}iH_i =\sum_0^nxH_x\delta x =\frac{n^{\underline{2}}}{2}(H_n-\frac{1}{2}) =\frac{n(n-1)(2H_n-1)}{4}.


Ćwiczenie 5

Znajdź postać zwartą sumy \displaystyle \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ą \displaystyle \sum x^{\underline{2}}3^x\delta x:


\displaystyle \aligned \sum x^{\underline{2}}3^x\delta x &=x^{\underline{2}}\frac{3^x}{2}-\sum2x^{\underline{1}}\frac{3^{x+1}}{2}\delta x\\ &=\frac{1}{2}x^{\underline{2}}3^x-3\sum x^{\underline{1}}3^x\delta x\\ &=\frac{1}{2}x^{\underline{2}}3^x-3\left( x\frac{3^x}{2}-\sum \frac{3^{x+1}}{2}\delta x \right)\\ &=\frac{1}{2}x^{\underline{2}}3^x-\frac{3}{2}x3^x+\frac{9}{2}\sum 3^x\delta x\\ &=\frac{1}{2}x^{\underline{2}}3^x-\frac{3}{2}x3^x+\frac{9}{4}3^x+C. \endaligned


A zatem nasza suma wynosi:


\displaystyle \sum_{i=0}^{n-1}i(i-1)3^i =\sum_0^nx^{\underline{2}}3^x\delta x =\frac{1}{2}n^{\underline{2}}3^n-\frac{3}{2}n3^n+\frac{9}{4}3^n-\frac{9}{4} =\frac{3^n\left( 2n^2-8n+9 \right)-9}{4}.


Ćwiczenie 6

Czy warunek \displaystyle (\Delta f)(x)=f(x) implikuje, że \displaystyle f(x)=2^x?

Rozwiązanie

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

Ćwiczenie 7

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


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


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

  • \displaystyle G(n)=\sum_{i=1}^ng_i,
  • \displaystyle G(G(n))=\sum_{i=1}^ni\cdot g_i.

Wskazówka

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

Rozwiązanie

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

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


\displaystyle G(G(n+1))-G(G(n))=\sum_{i=G(n)+1}^{G(G(n+1))}g_i.


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


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