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ń dotyczacych ciągów, a właściwie do mało docenianego twierdzenia o ciagach 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\mathrm{\%}$. 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:

$${(1+\frac{1}{n})}^n.$$

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

$$\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^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={(1+\frac{{\displaystyle 1}}{{\displaystyle n}})}^n$. Mamy więc

$$e=\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^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!}+\dots +\frac{1}{n!}$).

Rozważając $x_1=\cdots =x_n=1+\frac{1}{n}$ oraz $x_{n+1}=1,$ w nierówności Cauchyego pomiędzy średnimi otrzymujemy

$$\frac{1+\frac{1}{n}+\cdots +1+\frac{1}{n}+1}{n+1}\ge {((1+\frac{1}{n})\dots (1+\frac{1}{n})\cdot 1)}^{1/(n+1)},$$

a stąd

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

więc również

$${(1+\frac{1}{n+1})}^{n+1}\ge {(1+\frac{1}{n})}^n$$

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

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

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

$$\frac{1-\frac{1}{n+1}+\cdots +1-\frac{1}{n+1}+1}{n+2}\ge {((1-\frac{1}{n+1})\dots (1-\frac{1}{n+1})\cdot 1)}^{1/(n+2)}.$$

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

$${(1-\frac{1}{n+2})}^{n+2}⩾{(1-\frac{1}{n+1})}^{n+1}.$$

Czyli ciąg $((1-\frac{1}{n+1}{)}^{n+1}{)}_{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\le a_2\le \dots \le a_n⩽b_n\le \dots \le b_2\le 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 \mathrm{\infty }}{\to }\mathrm{\infty }$, to ${(1+\frac{{\displaystyle 1}}{{\displaystyle a_n}})}^{a_n}\underset{n\to \mathrm{\infty }}{\to }e$,

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

(c) jeżeli $\mid c_n\mid \underset{n\to \mathrm{\infty }}{\to }\mathrm{\infty }$, to ${(1+\frac{{\displaystyle 1}}{{\displaystyle c_n}})}^{c_n}\underset{n\to \mathrm{\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}={(1+\frac{2}{n^2+1})}^{\left(\frac{n^2+1}{2}\right)\cdot 6}={\left({(1+\frac{2}{n^2+1})}^{\left(\frac{n^2+1}{2}\right)}\right)}^6⟶e^6,$$

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

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

Rozwiązanie: ponieważ $\underset{n\to \mathrm{\infty }}{lim}\frac{n}{n+1}=1$, to $\underset{n\to \mathrm{\infty }}{lim}{\left(\frac{n}{n+1}\right)}^n=\left[1^{\mathrm{\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[{(1+\frac{1}{n})}^n\right]}^{-1}.$$

Czyli

$$\underset{n\to \mathrm{\infty }}{lim}{\left(\frac{n}{n+1}\right)}^n=e^{-1}.$$

Zadanie 4.3. Oblicz granicę $\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^{an+b}$ dla $a\in \mathbb{R}\setminus \{0\}$.

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

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

Obliczamy granicę

$$\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^{an+b}=[e^a\cdot 1^b]=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}={(1-\frac{2}{3n+1})}^{\frac{3n+1}{2}\cdot \frac{2}{3}+\frac{8}{3}},$$

czyli

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

a stąd $a_n\to e^{-\frac{2}{3}}\cdot 1$, \ gdy $n\to \mathrm{\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 ${(1+\frac{{\displaystyle 1}}{{\displaystyle \sqrt{n}}})}^n$. Z dwumianu Newtona możemy napisać nierówności,

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

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

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

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

$$\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{n}=1.$$

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

$$s_n=1+\frac{1}{1!}+\frac{1}{2!}+\dots +\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!}+\dots +\frac{1}{n!}<1+\frac{1}{2^0}+\frac{1}{2^1}+\frac{1}{2^2}+\dots +\frac{1}{2^{n-1}}=$$

$$=1+\frac{1-(\frac{1}{2}{)}^n}{1-\frac{1}{2}}=1+2(1-(\frac{1}{2}{)}^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 $\underset{n\to \mathrm{\infty }}{lim}{s}_n=s$.

Zadania samodzielne.

(1) Oblicz granicę:

(a)

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

(b)

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

(c)

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

(d)

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

(e)

$$a_n={(1+\sqrt{n+1}-\sqrt{n})}^{\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},\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 $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\ge 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ę 12 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},\dots$$

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 ($Ra226$) wynosi on 1560 lat. Ile lat co najmniej trzeba czekać, aby z $1g$ radu zostało mniej niż $0,1mg$?

Zadanie (10). Bezpośrednio za pomocą twierdzenia Cauchyego o nierówności pomiędzy średnimi oraz twierdzenia o 3 ciągach wykaż, że $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{3}=1.$ Czy tak samo można zbadać granicę $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{n}=1$?

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

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

Obliczyć granicę $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}$.

Zadanie (12). Niech $x>0$ oraz

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

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

Zadanie (13). Jeśli istnieje, to znaleźć wartość parametru $t$, dla którego zachodzi:

$$\underset{n\to \mathrm{\infty }}{lim}{\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:

$$\text{(a)}{x}_{n+1}=5\cdot n+1,$$

$$\text{(b)}{x}_{n+1}=2\cdot x_n+3\cdot n,$$

$$\text{(c)}{x}_{n+1}=4\cdot x_n+\frac{1}{n+1},$$

$$\text{(d)}{x}_{n+1}=\frac{x_n}{n+2},$$

$$\text{(e)}{x}_{n+1}={x_n}^2$$

$$\text{(f)}{x}_{n+1}=(x_n{)}^{n+1}.$$

Zadanie (16). Zbadać zbieżność ciagów rekurencyjnych i określić ich granice przy zadanym wyborze pierwszego wyrazu:

(a)

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

(b)

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

(c)${}^{\ast }$

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

(d)

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

Zadanie (17). Rozwiązać równania rekurencyjne:

$$\begin{array}{r}\begin{array}{ll}\text{(a)}{x}_{n+1}=(n+3{)}^3\cdot x_n,& \text{(b)}{x}_{n+1}=\frac{1}{7n}\cdot x_n,\\ \text{(c)}{x}_{n+1}=\frac{3}{5n+4}\cdot x_n,& \text{(d)}{x}_{n+1}=2^{2n+2}\cdot x_n,\\ \text{(e)}{x}_{n+1}=5^{2n+1}\cdot x_n,& \text{(f)}{x}_{n+1}=\frac{(n+2{)}^2}{(n+3{)}^3}\cdot x_n,\\ \text{(g)}{x}_{n+1}=3^n\cdot (n+1)\cdot x_n,& \text{(h)}{x}_{n+1}=(1-\frac{1}{n+3})\cdot x_n,\text{(i)}{x}_{n+1}=\sqrt[3]{1+\frac{3}{n+1}}\cdot x_n.\end{array}\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}+\dots +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}+\dots +a_1)\cdot x+a_0.$$

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

Odp. $w_n(x)=w_{n-1}(x)\cdot x+a_0$ dla $n⩾1$ i $w_0(x)=a_0$

Polecana literatura:

1. M. Mrozek, ‘’Analiza matematyczna I. Notatki do wykładu matematyki komputerowej’’, UJ, Kraków, 2013.

2. P. Strzelecki, ‘’Analiza matematyczna I’’, UW, Warszawa, 2012.

3. M. Moszyński, ‘’Analiza matematyczna dla informatyków’’, UW, Warszawa, 2010.

4. M. Oberguggenberger, A. Ostermann, ‘’Analysis for Computer Scientists’’, Springer, London, 2011.

5. A. Ralston, ‘’Wstęp do analizy numerycznej’’, PWN, Warszawa, 1983.

6. D.B. Small, J.M. Hosnack, ‘’Ćwiczenia z analizy matematycznej z zastosowaniem systemów obliczeń symbolicznych’’, WNT, Warszawa, 1995.

7. A. Sendlewski - zliczanie rekurencyjne

8. M.M. Sysło, praca z uczniem uzdolnionym

9. skrypt: prof. Jaworskiego, prof. Palki i prof. Szymańskiego

10. materiał prof. Strzeleckiego - strony 300-308.