Category Archives: am1

Na Święta

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Zadania na Święta:
Z rozdziału III:
6 (wskazówka: użyć zad. 5), 25, 26, 27, 28, 29

z rozdziału IV:
zadania 2, 5 (max. 6 podpunktów), 6, 7.

Poniżej jest przykładowe rozwiązanie części podpunktu 5a).

Wesołych Świąt!!

Zadanie IV 5a (przypadek $a=2$)
Stwierdź, czy istnieje granica:
$$\lim_{x\rightarrow 2} \frac{x^2+x-2}{x^2-3x+2}.$$

Rozwiązanie.
Wiadomo, że wielomiany są funkcjami ciągłymi, tzn. jeżeli funkcja $f:\mathbb R\to \mathbb R$ jest wielomianem, to dla dowolnej liczby rzeczywistej $x_0$,
$$\lim_{x\rightarrow x_0}f(x)=f(x_0).$$

[Podamy tu dowód w przypadku funkcji $f$ mianownikiem, czyli gdy $f(x)=x^2+x-2$, oraz gdy $x_0=2$. Pokażemy, że $\lim_{x\rightarrow 2}f(x)=f(2)=4$. Dla innych wielomianów, dowód jest analogiczny.

Istotnie, na mocy twierdzenia Na mocy Tw. IV.2,
$$\lim_{x\rightarrow 2}(x\cdot x+x-2)=\lim_{x\rightarrow 2}x
\cdot \lim_{x\rightarrow 2}x-\lim_{x\rightarrow 2}x-\lim_{x\rightarrow 2}2$$ $$=
2\cdot 2+2-2=4.$$]

A zatem, gdy $x\rightarrow 2$, to licznik $x^2+x-2$ zbiega do $2^2+2-2=4$, a mianownik zbiega do $2^2-3\times 2+2=0$. Nie mówi nam to jeszcze, do czego zbiega cały iloraz.

Badamy znak mianownika w okolicy liczby $2$.
Zauważmy, że mianownik wynosi $(x-2)(x-1)$.
Na wykresie widać, że $(x-2)(x-1)$ jest ujemne, gdy $x$ jest w przedziale $(1,2)$, a dodatnie, gdy $x$ leży w przedziale $(1,+\infty)$.
Z tego wynika, że granica lewostronna w punkcie $2$ wynosi
$$\lim_{x\rightarrow 2^-} \frac{x^2+x-2}{x^2-3x+2}=-\infty$$
a granica prawostronna wynosi
$$\lim_{x\rightarrow 2^+} \frac{x^2+x-2}{x^2-3x+2}=+\infty.$$
A zatem granica w punkcie $2$ nie istnieje (na mocy wniosku na końcu strony 57 ze skryptu).

Powyżej korzystamy dwukrotnie z następującego faktu (dla $x_0=2$, i raz gdy $D=(1,2)$ a raz gdy $D=(2,3)$.

Fakt.Niech $f,g$ — dwie funkcje określone na zbiorze $D\subseteq \mathbb R$ oraz niech $x_0$ będzie punktem skupienia zbioru $D$. Jeżeli zachodzą następujące warunki:

  1. $g(x)>0$ dla wszystkich $x\in D$
  2. $\lim_{x\rightarrow x_0} g(x)=0$
  3. $\lim_{x\rightarrow x_0} f(x)>0$

to wtedy $$\lim_{x\rightarrow x_0} \frac{f(x)}{g(x)}=+\infty.$$
Dowód.
Oznaczmy $y=\lim_{x\rightarrow x_0} f(x)$.
Niech $a_1,a_2,\ldots$ będzie dowolnym ciągiem elementów $D$, zbieżnym do $x_0$.
Niech $K$ będzie dowolną liczbą. Pokażemy, że $f(a_n)/g(a_n)>K$ dla dostatecznie dużych $n$.

Istotnie, ponieważ $f(a_n)\rightarrow y$, to $f(a_n)>y/2$ dla dostatecznie dużych $n$.
A ponieważ $g(a_n)\rightarrow 0$, to $g(a_n)<\frac{y}{2N}$ dla dostatecznie dużych $n$. A zatem, dla dostatecznie dużych $N$, $$\frac{f(a_n)}{g(a_n)}>\frac{y/2}/{y/2N}=N.$$

Tak więc, $f(a_n)/g(a_n)\rightarrow+\infty$. Wobec dowolności ciągu $a_n$, to dowodzi faktu.

Zadania przygotowawcze do kolokwium

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Z listy zadań która znajduje się tutaj
następujące zadania:

  • str. 4
  • zad 1 ze str. 9
  • zad 1 ze str. 11
  • zad 1,2 str 12
  • zad 1,2 str 13

Ponadto:
zadania z rozdziału III ze skryptu: zad. 3, 5, 19
A także wszystkie zadania z rozdziałów I i II.

Dodatkowo, następujące zadania:

Zadanie 1
Niech $T$ będzie liczbą naturalną. Powiemy, że ciąg $\{b_n\}$ ma okres $T$, jeżeli $b_{n+T}=b_n$ dla wszystkich $n\in\mathbb N$. (Np. ciąg $-1,1,-1,1,\ldots$ ma okres 2).

Znajdź wszystkie takie ciągi okresowe o okresie $T$, które “nadają się do celów kryterium Dirichleta”, tzn. ciąg sum częściowych dla szeregu o wyrazach $b_n$ jest ograniczony.
(Np. ciąg $-1,1,\ldots$ ma tę własność). Sformułuj przy użyciu powyższego wyniku odpowiednie uogólnienie kryterium Leibnitza.

Zadanie 2
Znajdź przykład ciągu $\{a_n\}_{n\geq n_0}$ zbieżnego do 0, o wyrazach dodatnich, ale takiego, że dla każdego $p\geq n_0$ ciąg “obcięty, od p” $\{a_n\}_{n\geq p}$ nie jest monotoniczny.

Zbieżność i bezwzględna zbieżność

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Poniżej jest opis rozwiązania zadania III.3a ze skryptu.

Zadanie Zbadać zbieżność i bezwzględną zbieżność szeregu
$$\sum_{n=1}^{\infty}\frac{n^2-3}{n^4+3n}.$$
Zauważmy, że poza pierwszym wyrazem szeregu, wszystkie wyrazy są dodatnie.
A zatem ciąg sum częściowych jest monotonicznie rosnący, więc albo zbiega do $+\infty$, albo ma granicę skończoną.
Żeby wykluczyć pierwszą możliwość, wystarczy oszacować nasz szerego z góry przez inny szereg, o którym wiemy, że jest zbieżny:
$$\frac{n^2-3}{n^4+3n}\le \frac{n^2}{n^4}=\frac{1}{n^2}.$$
A zatem, możemy napisać:
$$\sum_{n=1}^{\infty}\frac{n^2-3}{n^4+3n}\le\sum_{n=1}^{\infty}\frac{1}{n^2}<\infty.$$ (Tu korzystamy z faktu, że szereg $\sum_{n}1/n^2$ jest zbieżny -- zob. przykład na stronie 42). Tak więc, szereg ten jest zbieżny. Teraz zastanówmy się nad bezwzględną zbieżnością naszego szeregu. Bezwzględna zbieżność jest równoważna zbieżności szeregu wartości bezwzględnych: $$\sum_{n=1}^\infty |\frac{n^2-3}{n^4+3n}|.$$ Wartości bezwzględne "zmieniają" tylko pierwszy wyraz szeregu, reszta była i tak dodatnia. Skorzystamy z następującego, prostego faktu: Niech $a_n$ będzie ciągiem oraz $k\ge 1$ liczbą naturalną.
Wówczas $\sum_{n=1}^\infty a_n$ jest zbieżny wtedy, i tylko wtedy, gdy
$\sum_{n=k}^\infty a_n$ jest zbieżny. Jeżeli oba szeregi są zbieżne, to
$$\sum_{n=1}^\infty a_n=a_1+a_2+\ldots+a_{k-1}+\sum_{n=k}^\infty a_n.$$

A zatem,
\begin{multline*}
\sum_{n=1}^\infty |\frac{n^2-3}{n^4+3n}|=
|\frac{1^2-3}{1^4+3}|+\sum_{n=2}^\infty |\frac{n^2-3}{n^4+3n}|=\\
|\frac{1^2-3}{1^4+3}|+\sum_{n=2}^\infty \frac{n^2-3}{n^4+3n}<\infty\qquad\qquad\qquad \end{multline*} A zatem, szereg jest bezwzględnie zbieżny.

Zadanie przygotowawcze z am1 (na sup i inf).

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Zadanie.
Obliczyć $\sup$ oraz $\inf$ zbioru
$$X=\set{\frac {|3^n-k|}{n!+k+30}:\quad k,n\in\mathbb N, 3^n-k\neq 0}.$$
Rozwiązanie.
Oczywiście, wszystkie elementy zbioru $X$ są nieujemne.
Gdyby nie warunek, że $3^n-k\neq 0$ w definicji zbioru $X$, to $0$ by należało do zbioru, więc byśmy mieli, że $0=\inf X$.
Po dodaniu warunku $3^n-k\neq 0$, zero przestaje należeć do zbioru, ale nadal możemy podejrzewać, że $0=\inf X$.
Spróbujemy to właśnie wykazać.

Ponieważ $0$ jest ograniczeniem dolnym zbioru $X$, to wystarczy pokazać, że nie istnieje większe ograniczenie dolne zbioru $X$;
to będzie znaczyło że $0$ jest największym ograniczeniem dolnym zbioru $X$.

Niech $m$ będzie liczbą naturalną. Pokażemy, że $1/m$ nie jest ograniczeniem dolnym zbioru $X$.
W tym celu, zauważmy, że biorąc $k=3^m-1$ oraz $n=m$, otrzymujemy
$$X\ni\frac {|3^n-k|}{n!+k+30}=\frac 1 {m!+3^m-1+30}<1/m.$$ A zatem, $\frac 1 m$ nie jest ograniczeniem dolnym zbioru $X$, dla dowolnej liczby naturalnej $m$. Z tego wynika, że dla dowolnej rzeczywistej liczby $\eps>0$, liczba $\eps$ nie jest ograniczeniem dolnym zbioru $X$.
W przeciwnym razie, biorąc $m$ takie, że $1/m<\eps$, dostalibyśmy, że $1/m$ też jest ograniczeniem dolnym zbioru $X$, a tak być nie może. Zatem żadna liczba $\eps>0$ nie jest ograniczeniem dolnym zbioru $X$. Stąd $\inf X=0$.

Teraz obliczymy $\sup X$.
Zauważmy, że (*) $$\frac {|3^n-k|}{n!+k+30}<\frac {|3^n-1|}{n!+31}.$$ Z tego wynika, że $\sup X=\sup Y$, gdzie $$Y=\set{\frac {3^n-1}{n!+31}:\quad n\in\mathbb N}.$$ Istotnie, $\sup X\ge \sup Y$ zachodzi, ponieważ $Y\subseteq X$ (więc każde górne ograniczenie zbioru $X$ jest też górnym ograniczeniem zbioru $Y$). Z drugiej strony, $\sup X\le \sup Y$, bo jeżeli $u$ jest ograniczeniem górnym zbioru $Y$, to jest też ograniczeniem górnym zbioru $X$ -- to wynika natychmiast z (*). A zatem, wystarczy obliczyć $\sup Y$. Pomocna obserwacja
Nietrudno zobaczyć (przynajmniej intuicyjnie), że ciąg $\frac {3^n-1}{n!+31}$ jest zbieżny do $0$ (bo $n!$ rośnie “szybciej” niż $3^n$. Formalny dowód tego faktu wymaga argumentu indukcyjnego, np. że $n!>(n/3)^n$).
Z tego wynikałoby, że ciąg $\frac {3^n-1}{n!+31}$ jest ograniczony z góry przez swój największy element (każdy ciąg zbieżny jest ograniczony z góry przez swój największy element). Pozostaje więc znaleźć największy element tego ciągu.

Sprawdzamy kolejne elementy tego ciągu:
$$1/16, 8/33, 26/37, 16/11, 242/151, 728/751, 2186/5071$$
Na oko widać, że w okolicach trzeciego lub czwartego elementu jest “górka”.

Próbujemy zatem dowodzić, że ciąg ten jest monotonicznie malejący od pewnego momentu.
Jeśli to udowodnimy, to nie musimy wcale pokazywać, że ciąg ten jest zbieżny do zera; była to jedynie obserwacja przydatna do wysnucia odpowiedniej hipotezy.

Formalnie, wystarczy, że wykażemy następujący lemat.
Lemat
Istnieje $n_0$ takie, że dla $n>n_0$ zachodzi nierówność:
$$\frac {3^n-1}{n!+31}>\frac {3^{n+1}-1}{(n+1)!+31}.$$
Dowód
Powyższa nierówność jest równoważna nierówności:
$$ {(3^n-1)}{((n+1)!+31)}> {(3^{n+1}-1)}{(n!+31)}.$$
Wykonując podstawowe rachunki łatwo sprawdzić, że dla $n>5$ powyższa nierówność zachodzi.
Zatem wystarczy wziąć $n_0=5$.

Wniosek.
$$\sup X=\sup Y=242/151.$$
Dowód.
Od szóstego wyrazu, ciąg $\frac {3^n-1}{n!+31}$ jest malejący, a spośród pierwszych sześciu wyrazów największy jest wyraz $242/151$.

Wzór Newtona

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Wzór Newtona to wzór na rozwinięcie potęgi $(a+b)^n$, który uogólnia znany wzór “skróconego mnożenia” $(a+b)^2=a^2+2ab+b^2$.
Dla skupienia uwagi, rozważmy przypadek $n=5$. Wtedy:
\begin{multline*}(a+b)^5=(a+b)(a+b)(a+b)(a+b)(a+b)\\=a^5+5\cdot a^4 b+ x\cdot a^3 b^2+y\cdot a^2 b^3+ 5\cdot a b^4+b^5,\\
\end{multline*}
dla pewnych współczynników $x,y$. Faktycznie, wyraz $a^5$ można otrzymać jedynie wybierając z każdego nawiasu $(a+b)$ wyraz $a$,
zatem w wyniku $a^5$ pojawi się tylko raz; podobnie z wyrazem $b^5$. Wyraz $a^4 b$ można otrzymać wybierając z jednego (z pięciu możliwych) wyrazów $(a+b)$ wyraz $b$, a z pozostałych biorąc wyraz $a$. Dlatego $a^4 b$ pojawi się w wyniku pięciokrotnie. Jak można otrzymać wyraz $a^3 b^2?$ Należy wybrać dokładnie z dwóch wyrazów wyraz $b$ (a z pozostałych wyraz $a$). To można zrobić na $10$ sposobów: $$\set{1,2}, \set{1,3}, \set{1,4}, \set{1,5}, \set{2,3}, \set{2,4}, \set{2,5}, \set{3,4}, \set{3,5}, \set{4,5}$$ (gdzie $\set{i,j}$ oznacza, że z $i$-tego oraz $j$-tego wyrazu wybraliśmy wyraz $b$, a z pozostałych wyraz $a$).
Zauważmy, że ta liczba sposobów jest równa liczbie $2$-elementowych podzbiorów zbioru $\set{1,2,3,4,5}$.
Zatem we wzorze na $(a+b)^5$, współczynnik $x$ przy $a^3 b^2$ wynosi $10$.
Przez symetrię, współczynnik przy $a^2b^3$ też musi wynieść $10$ (bo wzór jest taki sam jak się zamieni rolami zmienne $a$ i $b$).

Teraz uogólnimy powyższą obserwację dla dowolnego $n$.
\begin{multline*}
(a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)(a+b)}_{n \text{ razy}}\\=a^n+n\cdot a^{n-1} b+ {n\choose 2}\cdot a^{n-2} b^2+{n\choose 3}\cdot a^{n-3} b^2+ \ldots+{n\choose k}\cdot a^{n-k}b^k+\ldots+b^n,\\=
\sum_{k=0}^n{n\choose k}a^{n-k} b^{k}.\\
\end{multline*}
gdzie $n \choose k$ oznacza liczbę $k$-elementowych podzbiorów zbioru $\set{1,2,3,\ldots,n}$.
Istotnie, jak możemy otrzymać wyraz $a^{n-k}b^k$? Należy wybrać wyraz $b$ dokładnie z $k$ (spośród $n$) wyrazów $(a+b)$.
Na ile sposobów można to zrobić? Na tyle, co wynosi liczba $k$-elementowych podzbiorów zbioru $\set{1,2,3,\ldots,n}$.

Dostaliśmy powyżej wzór Newtona. Pojawia się pytanie, jak obliczyć liczbę $n \choose k$?
To znaczy, ile jest $k$-elementowych podzbiorów zbioru $n$-elementowego?

Fakt.Niech $n,k\ge 0$ będą dwiema liczbami całkowitymi. Wtedy
$${n\choose k}=\frac {n^{\underline k}}{k!}=\frac {n!}{k!(n-k)!},$$
gdzie $n^{\underline k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$ oznacza iloczyn kolejnych $k$ wyrazów, z których największy to $n$.
Dowód.
Powiemy, że ciąg $a_1,a_2,\ldots,{a_k}$ elementów zbioru $\set{1,2,\ldots,n}$ jest różnowartościowy jeżeli jego wyrazy są parami różne.
Ile jest ciągów różnowartościowych długości $k$?
Pierwszy wyraz może być dowolnym spośród $n$ możliwych. Drugi wyraz może być dowolnym, różnym od pierwszego, czyli jest $n-1$ możliwości.
Trzeci wyraz może być dowolnym różnym od pierwszego i drugiego (które są od siebie różne), czyli jest $n-2$ możliwości. I tak dalej.
Dla ostatniego wyrazu jest $n-k+1$ możliwości.
Zatem ciągów różnowartościowych długości $k$ jest $$n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)=n^{\underline k}.$$

Każdy ciąg różnowartościowy $a_1,a_2,a_3,\ldots,a_k$ wyznacza zbiór $k$-elementowy, mianowicie $\set{a_1,a_2,\ldots,a_k}.$
Odwrotnie, każdy zbiór $k$-elementowy $\set{a_1,\ldots,a_k}$ jest wyznaczony przez pewien ciąg różnowartościowy, np. przez ciąg $a_1,a_2,\ldots,a_k$.
A dokładniej, jest też wyznaczony przez $k!$ takich ciągów — otrzymanych ze wszystkich permutacji ciągu $a_1,a_2,\ldots,a_k$
(zauważmy, że każde dwie permutacje tego ciągu są różne, ponieważ ciąg jest różnowartościowy), a permutacji ciągu $k$-elementowego jest $k!$.

Z tego wynika, że zbiorów $k$-elementowych jest $\frac {n^{\underline k}}{k!}=\frac {n!}{k!(n-k)!}$.

Poniższa obserwacja pozwala obliczyć $n \choose k$ jako $k$-ty element w $n$-tym wierszu trójkąta Pascala
Fakt. Niech $n,k$ będą nieujemnymi liczbami całkowitymi.

  • Jeżeli $k=0$ to ${n\choose k}=1$.
  • Jeżeli $k>0$ to $${n\choose k}={n-1\choose k-1}+{n-1\choose k}.$$

Dowód.
Pierwszy punkt jest oczywisty, bo $n\choose k$ to liczba podzbiorów zbioru $n$-elementowego mocy $0$, a jest jeden tak podzbiór — zbiór pusty.

Przypuśćmy, że $k>0$.
Zauważmy, że
$$(a+b)^n=(a+b)(a+b)^{n-1}.$$
Stosując wzoru Newtona po obu stronach powyższej równości, dostajemy:
\begin{multline*}\sum_{k=0}^n{n\choose k}a^{n-k} b^{k}=(a+b)\cdot\sum_{k=0}^{n-1}{n-1\choose k}a^{n-1-k} b^{k}\\
=\sum_{k=0}^{n-1}{n-1\choose k}a^{n-k} b^{k}+\sum_{k=0}^{n-1}{n-1\choose k}a^{n-1-k} b^{k+1}.\\
\end{multline*}
Porównując obie strony równości, widzimy, że współczynnik przy $a^{n-k}b^k$ to z jednej strony $n\choose k$, a z drugiej strony ${n-1\choose k}+{n-1\choose k-1}$.

Powyższy fakt pozwala obliczyć wartość $n\choose k$ na podstawie trójkąta Pascala:

  • W pierwszym wierszu tego trójkąta znajduje się jeden (“zerowy”) wyraz, o wartości 1; kolejne wyrazy (pierwszy, drugi, trzeci, itd.) w tym wierszu są równe zero (ale nie zaznaczamy ich w trójkącie).
  • W $n$-tym wierszu, $k$-ty wyraz jest otrzymany przez dodanie $k$-tego wyrazu w poprzednim wierszu do $(k-1)$-ego wyrazu w poprzednim wierszu.

$$\begin{array}{llllll}
1&&&&&\\
1&1&&&\\
1&2&1&&\\
1&3&3&1&\\
1&4&6&4&1\\
.&.&.&.&.\quad.\\
\end{array}$$
Liczba $n\choose k$ to dokładnie $k$-ty wyraz w $n$-tym wierszu trójkąta Pascala, ponieważ, na mocy faktu powyżej, dokładnie spełnia te same reguły co wartości w trójkącie Pascala.

Proste zadanie teoretyczne

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Zadanie.

Niech $\{a_n\}_{\mathbb N}$ oraz $\{b_n\}_{\mathbb N}$ będą dwoma ciągami liczb rzeczywistiych.

Pokazać, że jeżeli te ciągi są zbieżne do granic  $g$ oraz $h$ odpowiednio,

to ciąg $\{a_n+b_n\}_{\mathbb N}$ jest zbieżny do granicy $g+h$. Pokazać, że odwrotna implikacja nie musi zachodzić.

Zadanie.

Pokazać fakt analogiczny do powyższego, tylko z mnożeniem zamiast dodawania (tzn. o ciągu iloczynów $\{a_n\cdot b_n\}$).

Rozwiązanie pierwszego zadania.

Niech $\varepsilon>0$ będzie dowolną liczbą. Wskażemy liczbę naturalną $n_0$ taką, że $|(a_n+b_n)-(g+h)|<\varepsilon$ dla $n>n_0$.

Definiujemy $n_0$ jako taką liczbę, że $|a_n-g|<\varepsilon/2$ oraz $|b_n-h|<\varepsilon/2$ dla $n>n_0$.

Wiadomo, że taka liczba istnieje, na mocy założeń o zbieżności odpowiednich ciągów.

Wówczas, na mocy nierówności trójkąta, $|(a_n+b_n)-(g+h)|=|(a_n-g)+(b_n-h)|\le |a_n-g|+|b_n-h|< \varepsilon/2+\varepsilon/2=\varepsilon.$

To pokazuje, że ciąg $\{a_n+b_n\}$ jest zbieżny do granicy $g+h$.

 

Zadanie teoretyczne

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Niech $A$ będzie dowolnym niepustym podzbiorem $\mathbb R$.

Pokazać, że istnieje ciąg $a_1,a_2,\ldots$ elementów zbioru $A$ który spełnia obydwa poniższe warunki:

  1. $a_1\le a_2\le a_3\le \ldots$
  2. $\lim_{n\rightarrow\infty} a_n=\sup A$.

Dowód. Dla liczby $u\in \mathbb R$ piszemy $A\le u$ jeżeli $a\le u$ dla każdej liczby $a\in A.$

Niech $s=\sup A$. Z definicji, oznacza to, że 

  • $A\le s$ ($s$ jest ograniczeniem górnym $A$)
  • Dla każdej liczby $s’$ takiej, że $A\le s’$ zachodzi nierówność $s\le s’$ ($s$ jest najmniejszym ograniczeniem górnym).

Skonstruujemy teraz ciąg $a_n$. Niech $a_1$ bedzie dowolnym elementem zbioru $A$ (korzystamy z niepustości $A$).

Rozważamy dwie możliwości.

Możliwość 1. $s\in A$, czyli $A$ ma element największy (jest nim wtedy $s$).

Wtedy możemy zdefiniować $a_1=a_2=a_3=\ldots=s$.
Ciąg ten wtedy spełnia warunki zadania.

 

Możliwość 2. $s\not\in A$. Zatem $A$ nie ma elementu największego.

Niech $a_1$ będzie dowolnym elementem $A$ (korzystamy z niepustości $A$). Wiadomo, że $a_1$ nie jest elementem największym zbioru $A$

(w przeciwnym razie $s=a_1\in A$, wbrew założeniu $s\not\in A$).

Zatem istnieje $a_2\in A$ takie, że $a_2>a_1$.

Ponownie, $a_2$ nie jest elementem największym zbioru $A$, więc istnieje $a_3\in A$ takie, że $a_3>a_2$.

I tak dalej. W ten sposób konstruujemy ciąg $a_1,a_2,\ldots$ elementów zbioru $A$, który jest ściśle rosnący.

UWAGA. Powyższe rozwiązanie to podpucha. Ten ciąg wcale nie musi być zbieżny do $s$.

Przykład: $A=[0,2]$. Wtedy $s=2$. Ale powyższa konstrukcja może skonstruować ciąg $0,0.1,0.11,0.111,0.1111,\ldots$ który jest zbieżny do $1<2.$   Dlatego trzeba uważać. Rozwiązanie 2. Znowu rozważamy możliwość 2, czyli że $A$ nie ma elementu największego. Tym razem postępujemy ostrożniej.

Załóżmy wpierw, że $s<\infty$, czyli że $A$ jest ograniczony z góry. Rozważmy $s_1=s-1$. Wtedy $s_1s_1$.

Teraz rozważmy $s_2=s-1/2 $. Podobnie jak poprzednio, $s_2$ nie jest ograniczeniem górnym zbioru $A$. Musi więc istnieć $a_3\in A$ takie, że $a_3>s_2$ oraz $a_3>a_2$.

I tak dalej.

Konstruujemy w ten sposob nieskończony ciąg $a_1,a_2,\ldots$ taki, że

  • $a_1
  • $a_n>s_n=s-1/n$.

Oczywiście, $\lim_{n\rightarrow\infty} (s-1/n)=s$, więc możemy zastosować twierdzenie o trzech ciągach (tw. II.3):
$$\begin{array}{ccc}
s-1/n&

zadania przygotowawcze

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Polecam dobrze zapoznać się z podrozdziałami 1,2,3 rozdziału 2 ze skryptu, a także ćwiczyć zadania z rodziałów 1 i 2.

Poniżej jest przykładowe rozwiązanie zadania I.1.f.
Zadanie. Obliczyć granicę ciągu $\{(0.9999+\frac 1 n)^n\}_{n\in\mathbb N}$.

Rozwiązanie. 

Niech $\alpha={0.9999}$.

\begin{multline*}
\lim_{n\rightarrow\infty}(\alpha+\frac 1 n)^n=
\lim_{n\rightarrow\infty}\left(\alpha\cdot(1+\frac 1 {\alpha\cdot n})\right)^n=\\
\lim_{n\rightarrow\infty}\left[\alpha^n\cdot(1+\frac 1 {\alpha\cdot n})^n\right]=\\
=\lim_{n\rightarrow\infty}\alpha^n\cdot\lim_{n\rightarrow\infty}\left((1+\frac 1 {\alpha\cdot n})\right)^{n}=\quad\\
%\lim_{n\rightarrow\infty}\left[\alpha^n\cdot\left(\left((1+\frac 1 {\alpha\cdot n})\right)^{n\alpha}\right)^{1/\alpha}\right]=\quad\\
=\lim_{n\rightarrow\infty}\alpha^n\cdot\left(\lim_{n\rightarrow\infty}\left((1+\frac 1 {\alpha\cdot n})\right)^{n\alpha}\right)^{1/\alpha}=\quad\\=
0\cdot e^{1/\alpha}=0\qquad\\\qquad\qquad
\end{multline*}

Powyżej skorzystaliśmy z trzech faktów.

Fakt 1. Jeżeli $\lim_{n\rightarrow\infty}a_n=g$ oraz $\lim_{n\rightarrow\infty}b_n=h$, to $\lim_{n\rightarrow\infty}(a_n\cdot b_n)=g\cdot h.$

Ten fakt był sformułowany na wykładzie.

Fakt 2. Jeżeli $\beta\in\mathbb R$ oraz $\lim_{n\rightarrow\infty}a_n=g$ to $\lim_{n\rightarrow\infty}(a_n^\beta)=g^\beta.$

Ten fakt dopiero będzie na wykładzie, więc powyższe rozwiązanie jest niekompletne.

Fakt 3. Jeżeli $0<\alpha<1$ to $\lim_{n\rightarrow\infty}\alpha^n=0$.

Ten fakt był na wykładzie (przykład b, strona 29).

 

Poniżej jest inny, kompletny dowód zbieżności do $0$.

Rozwiązanie 2.

Rozwiązanie to naśladuje oszacowanie $(1+\frac 1 n)^n\le 3$ (pokazane tutaj).

Korzysta ono ze wzoru Newtona. Przez $n^{\underline k}$ oznaczam iloczyn $n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$, składający się z $k$ kolejnych czynników, z których największy wynosi $n$. Jest to wygodne do zapisu dwumianu Newtona: ${n\choose k}=\frac {n^{\underline k}}{k!}$.

\begin{multline*}
(\alpha+\frac 1 n)^n=\sum_{k=0}^n {n\choose k} \frac {\alpha^{n-k}} {n^k}\\
=\alpha^n\cdot\sum_{k=0}^n \frac {n^{\underline k}} {k!\alpha^k n^k}\\
\le\alpha^n\cdot\sum_{k=0}^n \frac {n^k} {k!\alpha^k n^k}\\
=\alpha^n\cdot\sum_{k=0}^n \frac {1} {k!\alpha^k }\\
\le\alpha^n\cdot\sum_{k=0}^n \frac {1} {2^{k-1}\alpha^k }\\
=2\alpha^n\cdot\sum_{k=0}^n \frac {1} {2^{k}\alpha^k }\\
\le2\alpha^n\cdot \frac {1}{1-1/(2\alpha)}\qquad\qquad\qquad
\end{multline*}
Zatem oszacowaliśmy wyrazy naszego ciągu z góry przez $\alpha^n\cdot c$ dla pewnej stałej $c$ (niezależnej od $n$); z dołu możemy je oszacować przez $0$.
Ponieważ $\alpha<1$, to $\alpha^n\longrightarrow 0$ (zob. Fakt 3 powyżej).
Z tego (oraz z tw. o trzech ciągach, Tw. II.3) wynika, że $\lim_{n\rightarrow\infty} (\alpha+\frac 1 n)^n=0$.

O liczbie e

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Definiujemy $e= \lim_{n\rightarrow \infty} (1+\frac 1 n)^n$.

Nie jest jasne, że powyższa granica w ogóle istnieje. Dowód tego faktu pozostawimy na poźniej.

Skąd taka definicja?

Motywacja finansowa.

Wyobraźmy sobie, że wkładamy do konta bankowego na jeden rok 1000 zł, oraz że rata wynosi 10% w skali rocznej.

Jeżeli rata jest rozliczana co miesiąc, to każdego miesiąca przybędzie (10/12)%, czyli 10/1200 dotychczasowej kwoty, a po 12 miesiącach wartość będzie wynosiła $1000\cdot(1+0.1/12)^{12}\approx 1104.71.$

Jeżeli rata jest rozliczana co tydzień, to każdego tygodnia przybędzie (około) (10/52)%, czyli 10/5200 dotychczasowej kwoty, a po 52 tygodniach wartość będzie wynosiła  $1000\cdot(1+0.1/52)^{52}\approx 1105.06.$

Jeżeli rata jest rozliczana codziennie, to każdego dnia przybędzie (10/365)%, czyli 10/36500 dotychczasowej kwoty, a po 365 dniach wartość będzie wynosiła $1000\cdot(1+0.1/365)^{365}\approx 1105.15.$

Widać, że zwiększanie częstości rozliczeń już nie bardzo ma sens, bo zysk jest niewielki. Intuicyjnie, jasne jest, że większa rozdzielczość rozliczania jest dla nas korzystna, ale zysk jest już bardzo mały przy podziale na 365 częśći. Inaczej mówiąc, ciąg tych wartości jest zbieżny (na oko).

Ale jaka jest graniczna wartość? Niech $K$ to będzie początkowa kwota, a $c$ będzie takie, że $1/c$ to odsetek w skali rocznej; np. dla 10%=1/10 bierzemy $c=10$. Niech $K_n$ to będzie końcowa kwota po roku, jeżeli naliczanie jest dokonywane $n$ razy do roku (w równych odstępach). Wtedy $$K_n=K\cdot(1+\frac 1{cn})^n=K\cdot((1+\frac 1{cn})^{nc})^{1/c}{\longrightarrow}K\cdot e^{{1}/{c}}.$$

Biorąc $K=1000$ oraz $c=10$ dostaniemy w granicy $K\cdot e^{{1}/{c}}=1105.17$, co zgadza się z powyższymi wartościami.

 

Teraz uzasadnimy, że jeżeli granica $e$ ciągu $(1+1/n)^n$ istnieje, to $2\le e\le 3$.

Lemat. Dla dowolnej liczby naturalnej $n$,

$$2\le (1+\frac 1 n)^n\le 1+1/1!+1/2!+\ldots+1/n!< 3.$$

Dowód. Korzystamy ze wzoru Newtona (tu jest o tym wzorze):

\begin{multline*}
(1+\frac 1 n)^n=\sum_{k=0}^n {n\choose k} \frac 1 {n^k}=\\
=1+{n\choose 1} \frac 1 n+{n\choose 2} \frac 1 {n^2}+{n\choose 3} \frac 1 {n^3}+\ldots+{n\choose n} \frac 1 {n^n}=\\
=1+\frac n 1\cdot \frac 1 n+\frac {n(n-1)}{1\cdot 2} \cdot\frac 1 {n^2}+\\+\frac{n(n-1)(n-2)}{1\cdot 2\cdot 3}\cdot \frac 1 {n^3}+\ldots+\frac{ n!}{n!}\cdot \frac 1 {n^n}\le\\
=1+1+\frac {n^2}{1\cdot 2} \cdot\frac 1 {n^2}+\frac{n^3}{1\cdot 2\cdot 3}\cdot \frac 1 {n^3}+\ldots+\frac{ n^n}{n!}\cdot \frac 1 {n^n}=\\
=1+1+\frac {1}{1\cdot 2} +\frac{1}{1\cdot 2\cdot 3}+\ldots+\frac{ 1}{n!}<\\
=1+1+\frac {1}{1\cdot 2} +\frac{1}{1\cdot 2\cdot 2}+\ldots+\frac{ 1}{2^{n-1}}=\\=1+\frac{1-1/2^{n}}{1-1/2}<1+2=3\\
\end{multline*}

gdzie pod koniec użyliśmy wzoru na sumę ciągu geometrycznego o współczynniku $1/2$.

Bardzo łatwo z powyższych obliczeń uzyskać lepsze oszacowanie.

Ćwiczenie. Pokazać, że dla $n\ge 2$ zachodzi oszacowanie $2\frac 1 4< (1+1/n)^n<2 \frac {11}{12}$.

Wniosek. Jeżeli granica $e$ ciągu $(1+1/n)^n$ istnieje, to $2\le e\le 3$.

Dowód. Przypuśćmy, że $e>3$. Wówczas, biorąc $\varepsilon=e-3>0$, z definicji zbieżności do granicy $e$ otrzymujemy, że $(1+1/n)^n\in (e-\varepsilon,e+\varepsilon)$ dla dostatecznie dużych $n$. W szczególności, $(1+1/n)^n>e-\varepsilon=e-(e-3)=3$ dla dostatecznie dużych $n.$ Jednak to jest sprzeczne z lematem. Zatem $e\le 3$.

Podobnie dowodzimy, że $e\ge 2$.

Żeby udowodnić, że ciąg $(1+1/n)^n$ jest zbieżny, wystarczy wykazać, że jest on niemalejący.
Istotnie, na mocy Twierdzenia II.4, każdy niemalejący ciąg posiada granicę.
To, że ciąg jest rosnący jest zgodne z intuicją finansową przedstawioną powyżej.
Nietrudno jest to wykazać przez indukcję.

Lemat 2. Niech $n\in\mathbb N$ będzie liczbą naturalną. Wówczas
$(1+\frac 1 n)^n<(1+\frac 1 {n+1})^{n+1}$. Dowód.
Powyższa nierówność równoważna jest nierówności (*):
$$\left(\frac {1+\frac 1 n}{1+\frac 1 {n+1}}\right)^n<1+\frac{1}{n+1}.$$ Przemnażając w lewym ułamku licznik i mianownik przez $n+1$ dostajemy: \begin{multline*} \left(\frac {1+\frac 1 n}{1+\frac 1 {n+1}}\right)^n =\left(\frac {n+1+\frac {n+1} n}{n+1+ 1 }\right)^n\\ =\left(\frac {n+2+\frac {1} n}{n+2}\right)^n\\ =\left(1+\frac 1{n(n+2)}\right)^n\qquad\qquad \end{multline*} Stosując podobne oszacowania co w Lemacie 1, dostajemy: \begin{multline*} \left(1+\frac 1{n(n+2)}\right)^n =\sum_{k=0}^n\frac {n^{\underline k}}{k!(n(n+2))^k}\\ \le 1+\sum_{k=1}^n\frac {n^k}{2^{k-1}(n(n+2))^k}\\ =1+2\sum_{k=1}^n\frac 1{2^k(n+2)^k}\\ =1+\frac{1}{n+2}\cdot \sum_{k=0}^{n-1}\frac 1{2^k(n+2)^k}\\ \le 1+\frac {1}{n+2}\cdot\frac{1}{1-\frac 1 {2(n+2)}}\\ = 1+\frac1 {n+2-\frac 1 2}= 1+\frac1 {n+1.5}<1+\frac 1{n+1},\\ \end{multline*} co dowodzi nierówności (*). Wniosek. Ciąg $(1+1/n)^n$ jest monotonicznie rosnący i ma granicę $e\le 3$.