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 an:

a1=a
a2=a1+r
a3=a2+r
a4=a3+r

Ciąg arytmetyczny an, 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:

a1=aan+1=an+r, gdzie n=1, 2, 3, 4, ,

Ciąg geometryczny an

a, aq, aq2, aq3, aq4, ,

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

a1=aan+1=an·q, gdzie n=1, 2, 3, 4,

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 Ln, 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.

Ln=2, n=01, n=1Ln-1+Ln-2, n>1
Rn5KS3koqwu4N
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.

L0=2
L1=1
L2=L2-1+L2-2=L1+L0=1+2=3
L3=L3-1+L3-2=L2+L1=3+1=4
L4=L4-1+L4-2=L3+L2=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

L0

L1

L2

L3

L4

L5

L6

L7

L8

L9

L10

2

1

3

4

7

11

18

29

47

76

123

Przykład 2

Ciąg Jacobsthala

Ciąg Jacobsthala to ciąg Jn 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 01. 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

Jn=0, n=01, n=1Jn-1+2Jn-2, n>1

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.

J0=0J1=1Jn+1=2Jn+-1n, n0

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

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

J0=0
J1=1
J2=J1+1=2J1+-11=2·1-1=1
J3=J2+1=2J2+-12=2·1+1=3
J4=J3+1=2J3+-13=2·3-1=5
J5=J4+1=2J4+-14=2·5+1=11
J6=J5+1=2J5+-15=2·11-1=21

Sprawdzamy, że rzeczywiście wyraz J6 jest taki sam, jak wyznaczony za pomocą innego wzoru.

Przykład 3

Ciąg JacobsthalLucasa

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

jn=2, n=01, n=1jn-1+2jn-2, n>1

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 JacobsthalLucasa łatwo widać związek między kolejnymi potęgami liczby 2, a numerami wskaźników kolejnych wyrazów ciągu.

j0=2=1+1=20+-10
j1=1=2-1=21+-11
j2=5=4+1=22+-12
j3=7=8-1=23+-13
j4=17=16+1=24+-14

Zapisujemy wzór ogólny ciągu.

jn=2n+-1n dla n0
Przykład 4

Ciąg Padovana

Ciąg Padovana Pn to ciag liczb naturalnych nazwany tak na cześć architekta Richarda Padovana określony w sposób rekurencyjny następująco:

Pn=1, n=01, n=11, n=2Pn-2+Pn-3, n>2

Rysunek przedstawia fragment wykresu tego ciągu.

R12hxDb9NYDpw

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

1, 1, 1, 2, 2, 3, 4, 5, 7, 9,

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
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 Pn nazwany tak na cześć siedemnastowiecznego angielskiego matematyka Johna Pella, zdefiniowany w sposób rekurencyjny następująco:

Pn=0, n=01, n=12Pn-1+Pn-2, n>1

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

Pn=1+2n-1-2n22

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
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