Définir une relation de récurrence mathématiquement. Une relation de récurrence a la forme suivante: An = f (An-1) où Ao = k. Dans cette équation, An est le terme actuel et An-1 est le terme précédent. Ao est le terme zéro et k est une constante.
Résoudre un relation de récurrence simple. Une série géométrique est donnée par An = RAN-1 où Ao = k est la condition initiale. Ainsi, A1 = kr, A2 = kr ^ 2 et A3 = kr ^ 3. En général donc, nous pouvons dire An = kr ^ n. La solution Une kr = ^ n est donc la solution non-récursif pour cette relation de récurrence.
Examiner les relations de récurrence plus complexes de la forme An = P (An-1) + S (An-2). Nous supposons que la solution non-récursif pour cette relation aura la forme An = f (r ^ n) pour certains r. Nous allons ensuite essayer de trouver la solution spécifique pour An.
Déterminer une valeur pour r ^ n. Si n gt; 1, alors nous savons que r ^ n = P (r ^ (n-1)) + S (r ^ (n-2)). Diviser chaque côté de cette équation par r ^ (n-2) pour obtenir r ^ 2 = + Pr S. Ceci fournit l'équation quadratique générale r ^ 2 - Pr - S = 0.
Résoudre l'équation quadratique r ^ 2 - Pr - S = 0 pour l'racines Y1 et Y2. Ceci fournit la solution générale An = C (y1 ^ n) + D (y2 ^ n). Les constantes C et D peuvent être choisis librement afin que cette solution répond à la condition initiale de la relation de récurrence.