Rekurencja, zwana również rekursją (łac. recurrere – przybiec z powrotem), to jedna z najważniejszych metod informatycznych konstruowania rozwiązań i algorytmów. Algorytm rekurencyjny to taki, który korzysta z samego siebie. Podobnie – istotą definicji rekurencyjnej jest odwoływanie się do samej siebie. W takiej definicji ciągu w wyrażeniu definiującym, obok symbolu zmiennej n występuje symbol definiowanego ciągu. Zatem wyraz ciągu zależy nie tylko od zmiennej n, ale też od jednego lub kilku wyrazów poprzednich.

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.

Wzór definiujący ciąg w taki sposób, nazywamy zależnością rekurencyjną.

Aby zapisać zależność rekurencyjną dla ciągu geometrycznego (co najmniej trzywyrazowego), ustalamy najpierw pewną liczbę a (pierwszy wyraz ciągu) i liczbę q (iloraz ciągu).

Wzór rekurencyjny ciągu geometrycznego an:

a1=aan+1=an·q,

gdzie:
a – pierwszy wyraz ciągu,
q – iloraz ciągu,
n=1, 2, 3, 4, ...

Przykład 1

Zapiszemy wzór rekurencyjny ciągu geometrycznegowzór rekurencyjny ciągu geometrycznegowzór rekurencyjny ciągu geometrycznego siedmiowyrazowego an o wyrazach:

14, 12, 1, 2, 4, 8, 16.

Odczytujemy pierwszy oraz drugi wyraz ciągu i określamy iloraz ciągu.

a1=14

q=1214=12·41=2

Zapisujemy wzór

a1=14an+1=2·an, gdzie  n=1, 2, 3, 4, 5, 6, 7.

Przykład 2

Ciąg geometryczny bn określony jest wzorem rekurencyjnym:

b1=-3bn+1=2·bn, gdzie  n=1, 2, 3, 4, 5, 6, 7...

Znajdziemy wzór ogólny tego ciągu.

1 sposób:

Wypisujemy kilka początkowych wyrazów ciągu.

-3, -32, -6, -62, -12, ...

Wnioskujemy, że pierwszy wyraz ciągu to b1=-3, natomiast iloraz ciągu to q=-32-3=2.

Zapisujemy wzór ogólny:

bn=-3·2n-1 dla n = 1 ,   2 , 3, 4, ...

2 sposób:

Na podstawie wzoru rekurencyjnego ustalamy i przekształcamy wyraz bn „cofając się” aż do wyrazu b1 tak, aby uzyskać postać

bn=b1·qn-1

bn=2bn-1=2·2bn-2=2·2·2·bn-3=...

bn=21·bn-1=22·bn-2=23·bn-3=...

Zauważmy, że suma numeru danego wyrazu i wykładnika potęgi 2 jest równa n. Zatem:

bn=21·bn-1=22·bn-2=23·bn-3=...=2n-1·b1=-3·2n-1

Odpowiedź:

Wzór ogólny ciągu: bn=-3·2n-1 dla n = 1 ,   2 , 3, 4, ...

Na podstawie wzoru rekurencyjnego możemy znaleźć dowolny wyraz ciągu, ale procedura jest wtedy znacznie dłuższa, niż przy wykorzystaniu wzoru ogólnego. Gdyż, aby wyznaczyć wyraz k–ty, musimy znać wszystkie wyrazy o numerach mniejszych od k.

Przykład 3

Znajdziemy piąty wyraz ciągu geometrycznego cn określonego wzorem

{ c 1 = 1 c n + 1 = 3 c n , gdzie: n=1, 2, 3, ...

Wyznaczamy kolejne wyrazy ciągu, aż do c5.

c1=1

c2=1·3=3

c3=3·3=9

c4=9·3=27

c5=27·3=81

Odpowiedź:

Piąty wyraz ciągu jest równy 81.

Wzór rekurencyjny ciągu możemy zapisać również w przypadku, gdy znamy co najmniej dwa wyrazy ciągu geometrycznego lub zależności łączące wyrazy ciągu.

Przykład 4

Wyrazy ciągu geometrycznego an, określonego dla n1, spełniają układ równań

a3+a6=420a4+a7=280.

Wyznaczymy wzór rekurencyjny tego ciągu.

Aby zapisać wzór rekurencyjny, na podstawie podanego układu równań, będziemy musieli znaleźć pierwszy wyraz ciągu i iloraz ciągu q.

Zauważmy, że a4=a3·q a 7 = a 6 q .

Układ równań zapisany w treści zadania przyjmuje więc postać:

a3+a6=420a3·q+a6·q=280

Po lewej stronie drugiego równania wyłączamy q przed nawias.

a3+a6=420qa3+a6=280

Na podstawie treści zadania wnioskujemy, że zarówno wyrazy ciągu, jak i iloraz są różne od zera. Możemy więc podzielić drugie równanie przez pierwsze – otrzymujemy iloraz ciągu.

q=280420=23

Zapisujemy wyrazy pierwszego równania za pomocą pierwszego wyrazu i ilorazu ciągu.

a3+a6=420

a1·q2+a1·q5=420

W miejsce q podstawiamy wyznaczoną liczbę.

a1·232+a1·235=420

49·a1+32243·a1=420

Z otrzymanego równania wyznaczamy pierwszy wyraz ciągu.

140243a1=420

a1=729

Zapisujemy wzór rekurencyjny ciągu.

a1=729an+1=23·an, gdzie n=1, 2, 3, ...

Na podstawie ciągu rekurencyjnego, możemy badać własności ciągu geometrycznego.

Przykład 5

Zbadamy monotoniczność ciągu geometrycznego an określonego wzorem:

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

Obliczamy drugi wyraz ciągu i wyznaczymy iloraz ciągu.

a2=3·4=12

q=a2a1

q=12:3=4

Zapisujemy wzór ogólny ciągu.

an=3·4n-1=34·4n

Badamy różnicę dwóch kolejnych wyrazów ciągu.

an+1-an=34·4n+1-34·4n=94·4n>0

Różnica jest liczbą dodatnią. Wnioskujemy, że an+1>an, a to oznacza, że ciąg jest rosnący.

Odpowiedź:

Ciąg an jest ciągiem rosnącym.

Słownik

wzór rekurencyjny ciągu geometrycznego
wzór rekurencyjny ciągu geometrycznego

wzór rekurencyjny ciągu geometrycznego an:

a1=aan+1=an·q

gdzie:
a – pierwszy wyraz ciągu,
q – iloraz ciągu,
n=1, 2, 3, 4, ...