Przeczytaj

Ważnym sposobem opisywania ciągów jest podanie wzoru rekurencyjnego. Wzór rekurencyjny tworzymy w ten sposób, że zapisujemy najpierw pierwszy wyraz ciągu lub kilka początkowych wyrazów tego ciągu. Następnie podajemy wzór na wyraz $n$ -ty (lub na wyraz np. $n + 1$ ) wyrażony za pomocą wyrazów poprzednich.

Wzór rekurencyjny uzależnia więc wartość dowolnego (ogólnego) wyrazu tego ciągu od wartości poprzedzających go wyrazów.

definicja rekurencyjna ciągu

Definicja: definicja rekurencyjna ciągu

Mówimy, że ciąg jest zdefiniowany rekurencyjnie, jeżeli:

określony jest pewien skończony zbiór wyrazów tego ciągu (zwykle jest to pierwszy wyraz ciągu lub kilka jego pierwszych wyrazów),
pozostałe wyrazy ciągu są zdefiniowane za pomocą poprzednich wyrazów tego ciągu.

Najbardziej znane przykłady ciągów rekurencyjnychdefinicja rekurencyjna ciąguciągów rekurencyjnych to ciąg arytmetyczny i ciąg geometryczny.

Kolejne początkowe wyrazy ciągu arytmetycznego $(a_{n})$ :

a_{1} = a

a_{2} = a_{1} + r

a_{3} = a_{2} + r

a_{4} = a_{3} + r

Ciąg arytmetyczny $(a_{n})$ , którego kolejne wyrazy (oprócz wyrazu pierwszego) tworzone są poprzez dodanie do wyrazu poprzedniego liczby $r$ , zwanej różnicą ciągu, można w sposób rekurencyjny określić następująco:

\{\begin{cases} a_{1} = a \\ a_{n + 1} = a_{n} + r \end{cases}

, gdzie

n = 1

2

3

4

\dots

Ciąg geometryczny $(a_{n})$

a

a q

a q^{2}

a q^{3}

a q^{4}

\dots

którego kolejne wyrazy (oprócz wyrazu pierwszego) tworzone są poprzez pomnożenie wyrazu poprzedniego przez liczbę $q$ , zwaną ilorazem ciągu, można w sposób rekurencyjny opisać następująco

\{\begin{cases} a_{1} = a \\ a_{n + 1} = a_{n} \cdot q \end{cases}

, gdzie

n = 1

2

3

4

\dots

Podamy teraz przykłady ciągów liczbowych, które odegrały ważną rolę w rozwoju arytmetyki, a szczególnie w poszukiwaniu formuły określającej liczby pierwsze.

Przykład 1

Ciąg Lucasa

Ciąg Lucasa $(L_{n})$ , nazwany tak na cześć dziewiętnastowiecznego matematyka Francoisa Lucasa, zdefiniowany jest w sposób rekurencyjny. Każdy wyraz tego ciągu, począwszy od wyrazu trzeciego, jest sumą dwóch wyrazów go poprzedzających.

L_{n} = \{\begin{cases} 2, n = 0 \\ 1, n = 1 \\ L_{n - 1} + L_{n - 2}, n > 1 \end{cases}

Rn5KS3koqwu4N

Ilustracja przedstawia prostokąt podzielony na kwadraty, których długości boków są kolejnymi wyrazami ciągu Lucasa. Wewnątrz figury znajduje się spirala przypominająca skorupkę ślimaka. Na każdym zakręcie spirali dotykającym krawędzi kwadratu, pojawia się rozbicie na mniejsze kwadraty. Kwadraty mają boki o następujących długościach: 76, 47, 29, 18, 11, 7, 4, ... — Spirala zbudowana w kwadratach, których długości boków są kolejnymi wyrazami ciągu Lucasa

Wyrazy tego ciągu to liczby naturalne, zwane oczywiście liczbami Lucasa. Obecnie ciągi tych liczb znajdują zastosowania w algorytmach szyfrowania.

Obliczymy początkowe wyrazy ciągu Lucasa, korzystając ze wzoru rekurencyjnego.

L_{0} = 2

L_{1} = 1

L_{2} = L_{2 - 1} + L_{2 - 2} = L_{1} + L_{0} = 1 + 2 = 3

L_{3} = L_{3 - 1} + L_{3 - 2} = L_{2} + L_{1} = 3 + 1 = 4

L_{4} = L_{4 - 1} + L_{4 - 2} = L_{3} + L_{2} = 4 + 3 = 7

W tabelce zamieszczamy obliczone wyrazy i jeszcze kilka innych początkowych wyrazów tego ciągu.

Kilka początkowych wyrazów ciągu Lucasa
$L_{0}$	$L_{1}$	$L_{2}$	$L_{3}$	$L_{4}$	$L_{5}$	$L_{6}$	$L_{7}$	$L_{8}$	$L_{9}$	$L_{10}$
$2$	$1$	$3$	$4$	$7$	$11$	$18$	$29$	$47$	$76$	$123$

Przykład 2

Ciąg Jacobsthala

Ciąg Jacobsthala to ciąg $(J_{n})$ liczb naturalnych nazwany tak na cześć niemieckiego matematyka Ernesta Jacobsthala. Wyrazy ciągu tworzone są w podobny sposób jak liczby Lucasa. Początkowe wyrazy ciągu to $0$ i $1$ . Każdy następny wyraz powstaje przez dodanie wyrazu poprzedniego i dwukrotności liczby poprzedzającej wyraz poprzedni.

Wzór rekurencyjny ciągu liczb Jacobsthala to

J_{n} = \{\begin{cases} 0, n = 0 \\ 1, n = 1 \\ J_{n - 1} + 2 J_{n - 2}, n > 1 \end{cases}

Początkowe wyrazy tego ciągu to:

$0$ , $1$ , $1$ , $3$ , $5$ , $11$ , $21$ , $43$ , $85$ , $171$ , $341$ , $683$ , $1365$ , $2731$ , $5461$ , $10923$ , $21845$ , $43691$ , $87381$ , $174763$ , $349525$ , ...

Okazuje się, że ciąg ten można również w inny sposób określić rekurencyjnie.

\{\begin{array}{lc} J_{0} = 0 \\ J_{1} = 1 \\ J_{n + 1} = 2 J_{n} + {(- 1)}^{n}, n \geq 0 \end{array}

Na podstawie tego wzoru określimy wyraz $J_{6}$ i sprawdzimy, czy jest to taka sama liczba, jak znaleziona za pomocą poprzedniego wzoru.

Aby obliczyć wyraz $J_{6}$ , trzeba niestety wyznaczyć aż sześć poprzednich wyrazów. Dwa pierwsze wyrazy przepisujemy bezpośrednio ze wzoru rekurencyjnego, pozostałe obliczymy.

J_{0} = 0

J_{1} = 1

J_{2} = J_{1 + 1} = 2 J_{1} + {(- 1)}^{1} = 2 \cdot 1 - 1 = 1

J_{3} = J_{2 + 1} = 2 J_{2} + {(- 1)}^{2} = 2 \cdot 1 + 1 = 3

J_{4} = J_{3 + 1} = 2 J_{3} + {(- 1)}^{3} = 2 \cdot 3 - 1 = 5

J_{5} = J_{4 + 1} = 2 J_{4} + {(- 1)}^{4} = 2 \cdot 5 + 1 = 11

J_{6} = J_{5 + 1} = 2 J_{5} + {(- 1)}^{5} = 2 \cdot 11 - 1 = 21

Sprawdzamy, że rzeczywiście wyraz $J_{6}$ jest taki sam, jak wyznaczony za pomocą innego wzoru.

Przykład 3

Ciąg Jacobsthal–Lucasa

Ciąg liczbowy Jacobsthal–Lucasa tworzony jest w podobny sposób jak ciąg Jacobsthala, ale ma różne wyrazy początkowe.

j_{n} = \{\begin{cases} 2, n = 0 \\ 1, n = 1 \\ j_{n - 1} + 2 j_{n - 2}, n > 1 \end{cases}

Początkowe wyrazy tego ciągu to:

$2$ , $1$ , $5$ , $7$ , $17$ , $31$ , $65$ , $127$ , $257$ , $511$ , $1025$ , $2047$ , $4097$ , $8191$ , $16385$ , $32767$ , $65537$ , $131071$ , $262145$ , $524287$ , $1048577$ , ...

Własności ciągu trudno jest określić na podstawie wzoru rekurencyjnego. Dlatego warto zapisać ciąg też za pomocą wzoru ogólnego. Aby określić taki wzór, trzeba zauważyć zależności między kolejnymi wyrazami ciągu. W przypadku ciągu Jacobsthal–Lucasa łatwo widać związek między kolejnymi potęgami liczby $2$ , a numerami wskaźników kolejnych wyrazów ciągu.

j_{0} = 2 = 1 + 1 = 2^{0} + {(- 1)}^{0}

j_{1} = 1 = 2 - 1 = 2^{1} + {(- 1)}^{1}

j_{2} = 5 = 4 + 1 = 2^{2} + {(- 1)}^{2}

j_{3} = 7 = 8 - 1 = 2^{3} + {(- 1)}^{3}

j_{4} = 17 = 16 + 1 = 2^{4} + {(- 1)}^{4}

Zapisujemy wzór ogólny ciągu.

j_{n} = 2^{n} + {(- 1)}^{n}

dla

n \geq 0

Przykład 4

Ciąg Padovana

Ciąg Padovana $(P_{n})$ to ciag liczb naturalnych nazwany tak na cześć architekta Richarda Padovana określony w sposób rekurencyjny następująco:

P_{n} = \{\begin{cases} 1, n = 0 \\ 1, n = 1 \\ 1, n = 2 \\ P_{n - 2} + P_{n - 3}, n > 2 \end{cases}

Rysunek przedstawia fragment wykresu tego ciągu.

R12hxDb9NYDpw

Ilustracja przedstawia układ współrzędnych z poziomą osią n od minus dwóch do dziewięciu oraz z pionową osią Pn od minus jeden do dziesięciu. Na płaszczyźnie narysowano wykres, składający się z punktów o następujących współrzędnych: 0;1, 1;1, 2;1, 3;2, 4;2, 5;3, 6;4, 7;5, 8;7, 9;9.

Na podstawie wykresu odczytujemy kilka początkowych wyrazów tego ciągu:

$1$ , $1$ , $1$ , $2$ , $2$ , $3$ , $4$ , $5$ , $7$ , $9$ , $\dots$

Zauważmy, że jest to ciąg niemalejący.

Figury geometryczne, których długości boków są kolejnymi wyrazami ciągu Padovana, wykorzystywane są często we wzorach architektonicznych.

RFUlZj8DLYqG7

Rysunek przedstawia trójkąty ułożone w taki sposób, że każdy następny trójkąt o krótszym boku od poprzedniego trójkąta ma z nim wspólną część boku. Z uwagi na to, że trójkąty są coraz mniejsze, zwiajają się do środka, przypominając skorupkę ślimaka. Trójkąty mają boki o następujących długościach: 16, 12, 9, 7, 5, 4, 3, 2, 2, 1, 1, 1. — Spirala trójkątów równobocznych o długościach boków zgodnych z sekwencją Padovana.

Zauważmy, że sposób rekurencyjny określania ciągu nie jest zbyt wygodny, bo obliczenie na przykład wyrazu dziesiątego, wymaga znalezienia aż dziewięciu wyrazów go poprzedzających.
W praktyce zatem częściej stosuje się wzór ogólny ciągu, gdyż korzystając z takiego wzoru można od razu wyznaczyć żądany wyraz ciągu, w szczególności, gdy jest to wyraz o dużym indeksie.

W Przykładzie 5 pokażemy, że jednak w niektórych przypadkach wzór ogólny jest dość skomplikowany i wyrazy o małych wskaźnikach znacznie łatwiej jest wyznaczyć ze wzoru rekurencyjnego.

Przykład 5

Ciąg Pella

Ciąg Pella to ciąg liczbowy $(P_{n})$ nazwany tak na cześć siedemnastowiecznego angielskiego matematyka Johna Pella, zdefiniowany w sposób rekurencyjny następująco:

P_{n} = \{\begin{cases} 0, n = 0 \\ 1, n = 1 \\ 2 P_{n - 1} + P_{n - 2}, n > 1 \end{cases}

Kilka początkowych wyrazówa ciągu to:

$0$ , $1$ , $2$ , $5$ , $12$ , $29$ , $70$ , $169$ , $408$ , $985$ , $2378$ , $5741$ , $13860$ , ...

Ciąg ten można również określić wzorem ogólnym

P_{n} = \frac{{(1 + \sqrt{2})}^{n} - {(1 - \sqrt{2})}^{n}}{2 \sqrt{2}}

Zauważamy, że w tym przypadku znacznie prościej jest wyznaczyć kolejne liczby Pella ze wzoru rekurencyjnego, niż ze wzoru ogólnego.

Słownik

definicja rekurencyjna ciągu

mówimy, że ciąg jest zdefiniowany rekurencyjnie, jeżeli:

określony jest pewien skończony zbiór wyrazów tego ciągu (zwykle jest to pierwszy wyraz ciągu lub kilka jego pierwszych wyrazów),
pozostałe wyrazy ciągu są zdefiniowane za pomocą poprzednich wyrazów tego ciągu

Wprowadzenie

Animacja

Słownik