6099520177

Zależności rekurencyjne

Definicja:

Ciąg (a_n)⁽^L₁ jest określony rekurencyjnie, jeżeli wyraz a_n jest pewną funkcją wyrazów poprzednich (i w ogólności również indeksu n):

a_n = f(n, a„_i,...,ao)

Przykład 1: Ciąg Fibbonaciego: a_n = a„_i + a_n_2, gdzie a₀ = ai = 1.

Przykład 2: a„ = T,kZl^k Przykład 3: Silnia: n! = n ■ (n — 1)!

Przykład 4: Potęga naturalna: aⁿ = a ■ a^n_1