15. Rekurencja 4.

Treści kształcenia. Ciągi zadane rekurencyjnie w informatyce. Granice ciągów, algorytmy obliczania granic (problem zbieżności). Problem stopu w algorytmach. Interpretacja geometryczna (programy). Ciągi monotoniczne i ograniczone. Liczba Eulera.

Efekty kształcenia: Student potrafi operować ciągami rekurencyjnymi, badać ich zbieżność i granice. Potrafi określić podstawowe wady i zalety takich ciągów w zastosowaniach informatycznych.

Wracamy do ogólnych zagadnień dotyczących ciągów, a właściwie do mało docenianego twierdzenia o ciągach monotonicznych i ograniczonych. Oto jego kolejne zastosowania.

Nie wolno sądzić, że omawiane przez nas twierdzenie o ciągach monotonicznych i ograniczonych ma zastosowania wyłącznie dla ciągów rekurencyjnych. Jest o wiele więcej jego zastosowań.

Za każdym razem, gdy symulacja komputerowa daje przypuszczenie, że ciąg jest zbieżny, musimy to sprawdzić i to najlepsze (choć niejedyne) narzędzie.

Podamy tu jedynie najbardziej znane zastosowanie.

Liczba $e$ ¶

Jest taki znany problem z czasów Bernoulliego: czy składając do banku na procent składany pewną kwotę, wypłata może być dowolnie duża (i bank zbankrutuje...) (analogia z ‘‘wdowim groszem’’)? To musiał zbadać matematyk.

Czyli: wpłacamy do banku powiedzmy 1 zł z oprocentowaniem - i tu celowo jaskrawy dobór na $100\%$ . Po roku byłoby to 2 zł, a jeśli dopuścimy wypłaty w dowolnym momencie proporcjonalnie do czasu trzymania pieniędzy w banku, uzyskamy np. po pół roku 1,5 zł, a więc po ponownym złożeniu na pół roku tej kwoty będzie 2,25 zł (czyli: więcej!). Dzieląc na $n$ okresów, mamy po roku:

\left( 1 + \frac{1}{n}\right)^n .

Gdyby dopuścić rosnącą w roku liczbę $n$ wpłat i wypłat, to ILE wypłacimy? Potrzebujemy sprawdzić istnienie i obliczyć

\lim_{n \to \infty} \left( 1 + \frac{1}{n}\right)^n .

Obliczanie procentu składanego:

R=RealField(50)
nmax = 1000
for n in range(1,nmax+1):
    x = 1+R(1)/n
    prod = R(1)
    for i in range(1,n+1):
        prod*=x
    if n>=988:
        print("s[%s] = %s"%(n,prod))

s[988] = 2.7169074548544
s[989] = 2.7169088432311
s[990] = 2.7169102287989
s[991] = 2.7169116115775
s[992] = 2.7169129915712
s[993] = 2.7169143687841
s[994] = 2.7169157432289
s[995] = 2.7169171149188
s[996] = 2.7169184838526
s[997] = 2.7169198500446
s[998] = 2.7169212134999
s[999] = 2.7169225742255
s[1000] = 2.7169239322344

Liczba $e$ nazywana jest także liczbą Nepera (lub: Eulera) i definiowana jest jako granica ciągu $a_n = \left(1+\frac {\displaystyle 1}{\displaystyle n}\right )^n$ . Mamy więc

e = \lim_{n\to\infty}\left(1+\frac{1}{n} \right)^n \ .

Istnienie tej granicy wynika właśnie z faktu, że ten ciąg JEST monotoniczny i ograniczony.

Uwaga: liczba $e$ praktycznie nie powinna być obliczana (również na komputerze) z definicji! To bardzo wolno zbieżny algorytm i pojawią się znacznie lepsze (ale: na analizie matematycznej jako granica ciągu $b_n = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \ldots + \frac{1}{n!}$ ).

Rozważając $x_1 = \dots = x_n = 1+\tfrac{1}{n}$ oraz $x_{n+1} = 1,$ w nierówności Cauchy’ego pomiędzy średnimi otrzymujemy

\frac{1+\frac{1}{n} + \dots + 1+\frac{1}{n} + 1}{n+1} \geq \left((1+\frac{1}{n}) \dots (1+\frac{1}{n}) \cdot 1\right)^{1/(n+1)},

a stąd

\left(\frac{n+2}{n+1}\right)^{n+1} \geq \left(1+\frac{1}{n}\right)^n

więc również

\left(1 + \frac 1 {n+1}\right)^{n+1} \geq \left(1+\frac{1}{n}\right)^n

i $a_{n+1}\geqslant a_n.$ Czyli ciąg $(a_n)$ jest niemalejący.

Połóżmy $b_n = \left(1+\tfrac{1}{n}\right)^{n+1}$ i zauważmy, że $a_n\leqslant b_n = \frac{1}{\left(\tfrac{n}{n+1}\right)^{n+1}} = \frac{1}{\left(1-\tfrac{1}{n+1}\right)^{n+1}}.$

Z nierówności pomiędzy średnimi zastosowanej do $x_1 = \dots = x_{n+1} = 1-\frac{1}{n+1}$ oraz $x_{n+2} = 1$ otrzymujemy, że:

\frac{1-\frac{1}{n+1} + \dots + 1-\frac{1}{n+1} + 1}{n+2} \geq \left(\left(1-\frac{1}{n+1}\right) \dots \left(1-\frac{1}{n+1}\right) \cdot 1\right)^{1/(n+2)}.

Stąd $\left( \tfrac{n+1}{n+2} \right)^{n+2} \geqslant \left(1-\tfrac{1}{n+1}\right)^{n+1},$ a więc też

\left(1-\tfrac{1}{n+2}\right)^{n+2} \geqslant \left(1-\tfrac{1}{n+1}\right)^{n+1}.

Czyli ciąg $\Big( (1-\tfrac{1}{n+1})^{n+1}\Big)_{n\in\mathbb N}$ jest niemalejący. Ponieważ $b_n = \frac{1}{(1-\frac{1}{n+1})^{n+1}},$ to możemy wywnioskować, że ciąg $(b_n)$ jest nierosnący, a stąd

a_1 \leq a_2 \leq \ldots \leq a_n \leqslant b_n \leq \ldots \leq b_2 \leq b_1.

Ciąg $(a_n)$ jest więc niemalejący i ograniczony z góry (np. przez $b_1$ ), a więc jest zbieżny.

Dalsze informacje: np. poz. [1.] strony 146-150.

Skrypt ilustracyjny liczby $e$ .

Można wykazać, że (zrobić wybrane na tablicy):

(a) jeżeli $a_n\underset {n\to\infty}\to \infty$ , to $\left (1+\frac {\displaystyle 1}{\displaystyle {a_n}}\right)^{a_n} \underset {n\to\infty}\to e$ ,

(b) jeżeli $b_n\underset {n\to\infty}\to -\infty$ , to $\left (1+\frac {\displaystyle 1}{\displaystyle {b_n}}\right )^{b_n} \underset {n\to\infty}\to e$ ,

(c) jeżeli $\mid c_n\mid\underset {n\to\infty}\to \infty$ , to $\left (1+\frac {\displaystyle 1}{\displaystyle {c_n}}\right )^{c_n}\underset {n\to\infty}\to e$ .

A teraz: dowodzimy wybranego z tych wzorów.

Zadanie 4.1¶

Obliczyć granicę ciągu

a_n = \left( \frac{n^2 + 3}{n^2 + 1} \right)^{3n^2 + 3} .

Rozwiązanie. Przekształcimy do postaci pozwalającej skorzystać z powyższych własności:

a_n = \left( \frac{n^2 + 3}{n^2 + 1} \right)^{3n^2 + 3} = \left( 1 + \frac{2}{n^2 + 1}\right)^{\left(\frac{n^2 + 1}{2}\right)\cdot 6 } = \left( \left( 1 + \frac{2}{n^2 + 1}\right)^{ \left(\frac{n^2 + 1}{2}\right) }\right)^6 \longrightarrow e^6 ,

gdzie wykorzystaliśmy, że $\left( 1 + \frac{2}{n^2 + 1}\right)^{\left(\frac{n^2 + 1}{2}\right)}\to e$ , gdy $n \to \infty$ .

Zadanie 4.2¶

Oblicz granicę ciągu $\left(\frac{n}{n+1}\right)^n .$

Rozwiązanie: ponieważ $\lim\limits_{n\to \infty}{\frac{n}{n+1}}=1$ , to $\lim\limits_{n\to \infty}{\left(\frac{n}{n+1}\right)^n}=\left[1^{\infty}\right]$ .

Przekształcimy wyraz badanego ciągu tak, aby pozbyć się symbolu nieoznaczonego i w granicy odnaleźć liczbę $e$

\left(\frac{n}{n+1}\right)^n=\left(\frac{n+1}{n}\right)^{-n}=\left[\left(1+\frac{1}{n}\right)^n\right]^{-1} .

Czyli

\lim_{n\to \infty}{\left(\frac{n}{n+1}\right)^n}=e^{-1} .

Zadanie 4.3¶

Oblicz granicę $\lim\limits_{n\to \infty}{\left(1+\frac{1}{n}\right)^{an+b}}$ dla $a\in \mathbb{R}\setminus \{0\}$ .

Rozwiązanie: skoro $\lim\limits_{n\to \infty}{\left(1+\frac{1}{n}\right)^{an+b}}= \left[1^{\pm \infty}\right]$ , gdzie znak w wykładniku zależy od znaku liczby $a$ , spróbujemy wykorzystać liczbę $e$ :

\left(1+\frac{1}{n}\right)^{an+b}=\left[\left(1+\frac{1}{n}\right)^{n}\right]^a \cdot \left(1+\frac{1}{n}\right)^b.

Obliczamy granicę

\lim_{n\to \infty}{\left(1+\frac{1}{n}\right)^{an+b}}=\left[e^a\cdot 1^b\right]=e^a .

Zadanie 4.4¶

Obliczyć granicę ciągu $a_n = \left(\frac{3n-1}{3n+1}\right)^{n+3}$ .

Rozwiązanie: tu również przekształcimy wyraz ciągu

a_n = \left(\frac{3n-1}{3n+1}\right)^{n+3} = \left( \frac{3n-1+2-2}{3n+1} \right)^{n+3} = \left( 1- \frac{2}{3n+1} \right)^{\frac{3n+1}{2} \cdot \frac{2}{3} + \frac{8}{3}} ,

czyli

a_n = \left( \left( 1- \frac{2}{3n+1}\right)^{\frac{3n+1}{2}}\right)^{\frac{2}{3}} \cdot \left( 1- \frac{2}{3n+1}\right)^{\frac{8}{3}} ,

a stąd $a_n \to e^{-\frac{2}{3}}\cdot 1$ , gdy $n \to \infty$ .

Zadanie 4.5¶

Zbadać monotoniczność ciągu $(a_n)$ , gdzie $a_n=\frac {\displaystyle 1}{\displaystyle {\sqrt {n^2+2}}}$ .

Rozwiązanie: jest oczywiste, że dla każdej liczby naturalnej $n$ prawdziwe są nierówności

(n+1)^2+2=(n^2+2)+(2n+1) > n^2+2 \ ,

\frac 1{n^2+2} > \frac 1{(n+1)^2+2} \ ,

a_n > a_{n+1} \ .

Wykazaliśmy więc, że ciąg $(a_n)$ jest malejący.

Zadanie 4.6¶

Obliczyć granicę ciągu $(a_n)$ , gdzie $a_n=\sqrt[n]{n}$ .

Rozwiązanie. Oszacujemy z dołu wyrażenie $\left (1+\frac {\displaystyle 1}{\displaystyle {\sqrt n}}\right )^n$ . Z dwumianu Newtona możemy napisać nierówności,

$\left (1+\frac {\displaystyle 1}{\displaystyle {\sqrt n}}\right )^n > 1+n\frac{\displaystyle 1}{\displaystyle {\sqrt n}} > \sqrt n > 1$ ,

$\left (1+\frac {\displaystyle 1}{\displaystyle {\sqrt n}}\right )^{2n} > n > 1$ ,

$\left (1+\frac {\displaystyle 1}{\displaystyle {\sqrt n}}\right )^2 > \sqrt[n]{n} > 1$ .

Ale $\lim_{n\to\infty}\left(1+\frac {\displaystyle 1}{\displaystyle {\sqrt n}}\right )=1$ , więc po zastosowaniu twierdzenia o trzech ciągach otrzymujemy

\lim_{n\to\infty}\sqrt[n]{n}=1 \ .

Zadanie 4.7¶

Dany jest ciąg $(s_n)$ , gdzie

s_n=1+\frac 1{1!}+\frac 1{2!}+\ldots +\frac 1{n!} \ .

Wykazać, że ciąg $(s_n)$ jest zbieżny.

Rozwiązanie. Ponieważ $s_{n+1}=s_n+\frac {\displaystyle 1}{\displaystyle {(n+1)!}}$ , więc stwierdzamy, że ciąg $(s_n)$ jest rosnący. Aby wykazać, że jest on ograniczony z góry, napiszmy

s_n= 1+\frac 1{1!}+\frac 1{2!}+\ldots+\frac 1{n!}<1+\frac 1{2^0}+\frac 1{2^1} +\frac 1{2^2}+\ldots+\frac 1{2^{n-1}}=

=1+ \frac {1-(\frac 12)^n}{1-\frac 12}=1+2(1-(\frac 12)^n) < 3 \ .

Wykazaliśmy, że ciąg $(s_n)$ jest rosnący i ograniczony z góry, a więc jest zbieżny, czyli istnieje $\lim_{n\to\infty}s_n=s$ .

Zadania samodzielne¶

(1) Oblicz granicę:

(a)

a_n = \left( 1 - \frac{1}{n}\right)^n

(b)

a_n = \left( 1 - \frac{1}{n^2}\right)^n

(c)

a_n = \left( \frac{3n + 5}{3n +2}\right)^n

(d)

a_n = \left( 1 + \frac{1}{n^2 -n + 1}\right)^{n^2 + 2}

(e)

a_n = \left( 1 + \sqrt{n+1} - \sqrt{n}\right)^{\sqrt{n} + 3} .

I jeszcze taki skrypt z kilkoma ciągami o granicy $e$

Liczbę $e$ przyjmuje się jako podstawę tzw. logarytmów naturalnych oznaczanych symbolem $\ln$ .

Korzystając z definicji logarytmów, możemy podać wzory na zamianę znanych ze szkoły średniej logarytmów dziesiętnych $\log_{10} b = \log b$ z logarytmami naturalnymi $\log_e b= \ln b$ . Mamy następujące wzory:

\log b = \frac {\ln b}{\ln 10} \ , \quad\quad \ln b=\frac {\log b}{\log e} \ .

Uwaga: zarówno liczba $e$ jak i logarytmy naturalne są bardzo ważne w matematyce i informatyce. Wspomnijmy tylko, że omawiana przez nas operacja obliczania pierwiastka z liczby w wielu zastosowaniach (np. kalkulatory naukowe) jest obliczana następująco:

\sqrt{a} = e^{\frac{1}{2}\ln{a}} ,

a więc musimy jak najdokładniej obliczyć $e$ (i znać zasady logarytmowania, ale - jak się okaże to bywa prostsze niż obliczanie pierwiastka).

Zbiór zadań¶

Zadanie (1)¶

W pewnym mieście pewien człowiek zachorował na ... grypę. Załóżmy, że każda chora osoba zaraża codziennie 4 zdrowe osoby. Ile będzie chorych po $n$ dniach? Podaj rozwiązanie w postaci jawnej i rekurencyjnej.

Zadanie (2)¶

Pewna cząsteczka porusza się w kierunku poziomym i w każdej sekundzie pokonuje odległość równą podwojonej odległości pokonanej w sekundzie poprzedzającej. Niech $a_n$ oznacza pozycję cząsteczki po $n$ sekundach. Podać rekurencyjną zależność dla $a_n$ , wiedząc, że $a_0 = 3$ , zaś $a_3 = 10$ .

Zadanie (3)¶

Każda poruszająca się piłka wprawia w ruch w ciągu sekundy 3 inne piłki, przy czym po 2 sekundach zatrzymuje się. W chwili ,,zero’’ jest jedna poruszająca się piłka. Niech $p(n)$ oznacza liczbę poruszających się piłek po $n$ sekundach. Podać rekurencyjną definicję ciągu $p(n)$ .

Zadanie (4)¶

Dla każdego $n \geq 1$ niech $t_n$ oznacza liczbę ciągów długości $n$ zbudowanych z symboli 0,1,2, w których żadne dwie jedynki nie występują obok siebie. Znaleźć zależność rekurencyjną dla $t_n$ .

Zadanie (5)¶

Oblicz granicę ciągów (lub wykaż, że nie istnieje).

a) $a_n = \frac{1}{2n+21}$

b) $b_n = \frac{n^3-100n^2-1}{n^2+4}$

c) $c_n = \frac{7n^2-10000n+2}{2n^{2}+256n-7}$

d) $d_n = \left(\frac{1}{7}\right)^{n}$

e) $e_n = \sqrt{2n+9}$

f) $f_n = \sqrt{\frac{10n^2-1}{7n+3}}$

Zadanie (6)¶

Czwarty wyraz ciągu arytmetycznego jest równy 8. Oblicz sumę 7 początkowych wyrazów tego ciągu.

Zadanie (7)¶

Piłka, odbijając się od ziemi, osiąga za każdym razem wysokość wynoszącą $\frac{7}{11}$ poprzedniej wysokości. Jak wysoko wzniosła się po drugim uderzeniu, jeżeli po ósmym odbiła się na wysokość 374 cm?

Zadanie (8)¶

Dany jest ciąg geometryczny postaci:

2, \frac{2}{p-1}, \frac{2}{(p-1)^2},\frac{2}{(p-1)^3}, \ldots

Wyznacz wszystkie wartości $p$ , dla których granicą tego ciągu jest liczba: a) 1, b) 2, c) 0.

Zadanie (9)¶

Okres połowicznego rozpadu pierwiastka to okres, po którym z danej ilości pierwiastka pozostaje jego połowa. Dla radu ( $Ra\ 226$ ) wynosi on około 1600 lat. Ile lat co najmniej trzeba czekać, aby z $1g$ radu zostało mniej niż $0,1 mg$ ?

Zadanie (10)¶

Bezpośrednio za pomocą twierdzenia Cauchy’ego o nierówności pomiędzy średnimi oraz twierdzenia o 3 ciągach wykaż, że $\lim_{n \to \infty}\sqrt[n]{3} = 1.$ Czy tak samo można zbadać granicę $\lim_{n \to \infty}\sqrt[n]{n} = 1$ ?

Zadanie (11)¶

Niech ciągi $(a_n)$ i $(b_n)$ spełniają warunek

a_n + b_n \sqrt{3} = \left( 2 + \sqrt{3}\right)^n .

Obliczyć granicę $\lim_{n \to \infty}\frac{a_n}{b_n}$ .

Zadanie (12)¶

Niech $x > 0$ oraz

a_n = \sqrt{x\cdot a_{n-1}}\quad , \quad a_1 = \sqrt{x} .

Obliczyć granicę ciągu $(a_n)$ .

Zadanie (13)¶

Jeśli istnieje, to znaleźć wartość parametru $t$ , dla którego zachodzi:

\lim_{n \to \infty}\left( \frac{3n-t}{3n+5}\right)^{2n} = e^5.

Zadanie (14)[Sendlewski]¶

Pasek kodu kreskowego tworzą na przemian kreski czarne i białe. Kod ten zawsze zaczyna się i kończy czarną kreską. Każda z kresek (czy to czarna, czy biała) ma grubość 1 albo 2. Ile jest pasków długości $n$ o różnych kodach (kody zawsze czytamy od lewej do prawej strony)?

$===>$ ... kolejne ciekawe przykłady można znaleźć w książce A. Sendlewski - zliczanie rekurencyjne

Zadanie (15)¶

Rozwiązać równania rekurencyjne, przyjmując dowolny wyraz początkowy:

\mbox{(a)}\ x_{n+1} = 5\cdot x_n +1,

\mbox{(b)}\ x_{n+1} = 2\cdot x_n + 3\cdot n,

\mbox{(c)}\ x_{n+1} = 4\cdot x_n +\frac{1}{n+1},

\mbox{(d)}\ x_{n+1} = \frac{x_n}{n+2},

\mbox{(e)}\ x_{n+1} = {x_n}^{2}

\mbox{(f)}\ x_{n+1} = ({x_n})^{n+1}.

Zadanie (16)¶

Zbadać zbieżność ciągów rekurencyjnych i określić ich granice przy zadanym wyborze pierwszego wyrazu:

(a)

a_{n+1} = \sqrt[3]{5a_n^2 + a_n - 5}\quad , \quad a_1 \in \{ 1,3,6,\frac{18}{19}\} ,

(b)

b_{n+1} = \sqrt[3]{7b_n}\quad , \quad b_1 \in [0, +\infty ) ,

(c) $^*$

c_{n+1} = \sin{c_n}\quad , \quad c_1 \in {\mathbb{R}} ,

(d)

d_{n+1} = \sqrt[4]{10d_n^2 - 9}\quad , \quad d_1 \in \{ 2, 4 \} .

Zadanie (17)¶

Rozwiązać równania rekurencyjne:

\begin{array}{ll} \mbox{(a)}\ x_{n+1} = (n+3)^3\cdot x_n,& \mbox{(b)}\ x_{n+1} = \frac{1}{7n}\cdot x_n,\\ \mbox{(c)}\ x_{n+1} = \frac{3}{5n+4}\cdot x_n,& \mbox{(d)}\ x_{n+1} = 2^{2n+2}\cdot x_n,\\ \mbox{(e)}\ x_{n+1} = 5^{2n+1}\cdot x_n,& \mbox{(f)}\ x_{n+1} = \frac{(n+2)^2}{(n+3)^3}\cdot x_n,\\ \mbox{(g)}\ x_{n+1} = 3^{n}\cdot(n+1)\cdot x_n,& \mbox{(h)}\ x_{n+1} = \left(1-\frac{1}{n+3}\right)\cdot x_n,\\ \mbox{(i)}\ x_{n+1} = \sqrt[3]{1+\frac{3}{n+1}}\cdot x_n.\\ \end{array}

Zadanie (18)¶

Rozwinąć w ułamki łańcuchowe: $\frac{5}{3}$ , $\sqrt{2}$ , $\sqrt{7}$ .

Zadanie (19)¶

Przygotuj symulacje (programy) obliczania liczb Fibonacciego metodą rekurencyjną oraz wzorem ogólnym (tu przyjmij $\sqrt{5}$ jako stałą np. $2,236068$ , podobnie można od razu postąpić z $\frac{1+\sqrt{5}}{2}$ ). Dla jakiego najmniejszego kroku $n$ oba wyniki będą się różnić?

Zadanie (20)¶

Dany jest wielomian

w_n(x) = a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0 .

Stosując algorytm Hornera, uzyskujemy wzór

w_n(x) = ( a_n x^{n-1} + a_{n-1} x^{n-2} + \ldots + a_1 )\cdot x + a_0 .

Wyprowadzić wzór rekurencyjny na tę procedurę.

Odp. $v_k (x) = v_{k-1} (x) \cdot x + a_{n-k}$ dla $k = 1, \ldots, n$ i $v_0(x) = a_n$ ; wtedy $w_n(x) = v_n(x)$

Polecana literatura¶

M. Mrozek, ‘‘Analiza matematyczna I. Notatki do wykładu matematyki komputerowej’’, UJ, Kraków, 2013.
P. Strzelecki, ‘‘Analiza matematyczna I’’, UW, Warszawa, 2012.
M. Moszyński, ‘‘Analiza matematyczna dla informatyków’’, UW, Warszawa, 2010.
M. Oberguggenberger, A. Ostermann, ‘‘Analysis for Computer Scientists’’, Springer, London, 2011.
A. Ralston, ‘‘Wstęp do analizy numerycznej’’, PWN, Warszawa, 1983.
D.B. Small, J.M. Hosack, ‘‘Ćwiczenia z analizy matematycznej z zastosowaniem systemów obliczeń symbolicznych’’, WNT, Warszawa, 1995.
A. Sendlewski - zliczanie rekurencyjne
M.M. Sysło, praca z uczniem uzdolnionym
skrypt: prof. Jaworskiego, prof. Palki i prof. Szymańskiego
materiał prof. Strzeleckiego - strony 300-308.

Liczba eee¶