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 $\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}^{n}x^{\underline {-2}}\delta x=-x^{\underline {-1}}+C$, to mamy:

$\displaystyle \sum _{i=0}^{n-1}{\frac {1}{(i+1)(i+2)}}=\sum _{0}^{n}x^{\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)^{i}i^{2}$.

Wskazówka

Pogrupuj składniki sumy parami.

Rozwiązanie

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

$\displaystyle {\begin{aligned}\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}-\left({\frac {n}{2}}(n-1)\right)\\&={\frac {n(n+1)}{2}}.\end{aligned}}$

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)^{i}i^{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 {\begin{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.\end{aligned}}$

Możemy teraz policzyć naszą sumę:

$\displaystyle \sum _{i=0}^{n-1}iH_{i}=\sum _{0}^{n}xH_{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 {\begin{aligned}\sum x^{\underline {2}}3^{x}\delta x&=x^{\underline {2}}{\frac {3^{x}}{2}}-\sum 2x^{\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.\end{aligned}}$

A zatem nasza suma wynosi:

$\displaystyle \sum _{i=0}^{n-1}i(i-1)3^{i}=\sum _{0}^{n}x^{\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\cdot 2^{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}^{n}g_{i}$,
• $\displaystyle G(G(n))=\sum _{i=1}^{n}i\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.