Ciąg nazywamy określonym rekurencyjnie, jeśli każdy jego wyraz zdefiniowany jest poprzez odwołanie się do wyrazów poprzednich. Rekurencja bywa także nazywana rekursją.
Najbardziej znanym przykładem ciągu rekurencyjnego jest ciąg Fibonacciego, nazywany tak od nazwiska matematyka, który znalazł ów ciąg badając dynamikę rozmnażania się populacji królików.
\((1,1,2,3,5,8,13,21,34,55,...)\)
W ciągu Fibonacciego każdy następny wyraz jest sumą dwóch wyrazów poprzedzających go.
\(1+1=2\)
\(1+2=3\)
\(2+3=5\)
\(3+5=8\)
\(5+8=13\)
itd.
Zaskakująca jest zwłaszcza mnogość kontekstów, w których w świecie rzeczywistym możemy ów ciąg odnaleźć - ma on związek z cyklem rozwojowym bardzo wielu roślin (np. określa ułożenie ziaren słonecznika) i zwierząt (opisuje np. kształt muszli łodzika), ponadto pojawia się także w zadaniach kombinatorycznych, w których zastanawiamy się na ile sposób można wykonać określoną czynność przy założeniu danych warunków ograniczających.
Wzór rekurencyjny ciągu Fibonacciego ma postać
\( \begin{cases} f_1 = 1\\ f_2 = 1 \\ f_{n+2} = f_n + f_{n+1} \forall n \ge 1\end{cases} \).
Widzimy zatem, że są tutaj określone pierwsze dwa wyrazy, oraz podana jest zasada, w myśli której tworzy się każdy kolejny wyraz w oparciu o dwa poprzednie.
Wyznaczenie wzoru ogólnego ciągu, gdy zadany jest jego wzór rekurencyjny, jest zadaniem trudnym (wymagana jest do tego zdolność rozwiązywania tzw. równań rekurencyjnych). Stosunkowo łatwo można natomiast wyznaczyć wzór rekurencyjny ciągu, gdy znany jest jego wzór ogólny.
Przykład:
Niech dany będzie ciąg o wyrazie ogólnym \(a_n = \frac {n(n+2)}{3}\). Wyznaczyć jego wzór rekurencyjny.
Wyznaczmy najpierw pierwszy wyraz tego ciągu. Łatwo sprawdzić, że \(a_1 = 1\).
Wiemy także, że \(a_{n+1} = \frac {(n+1)(n+3)}{3}\). Stąd możemy policzyć różnicę wyrazów następnego i poprzedniego:
\(a_{n+1} -a_n= \frac {(n+1)(n+3)}{3} - \frac {n(n+2)}{3}= \frac {n^2+n+3n+3-n^2-2n}{3} = \frac {2n+3}{3}\),
stąd zaś wynika, że \(a_{n+1} = a_n +\frac {2n+3}{3}\).
Ostatecznie więc zapisujemy wzór rekurencyjny ciągu w oparciu o jego pierwszy wyraz:
\( \begin{cases} a_1 = 1 \\ a_{n+1} = a_n +\frac {2n+3}{3} \forall n \ge 1 \end{cases} \).
Zadanie:
Określić rekurencyjnie ciąg zadany wzorem \(a_n = \frac {n(n+1)}2\).
Odpowiedź:
\( \begin{cases} a_1 = 1 \\ a_{n+1} = a_n + n +1 \forall n \ge 1 \end{cases} \).