Relație de recurență

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În matematică, se spune că un șir este definit printr-o relație de recurență dacă fiecare termen al acestuia poate fi scris ca o funcție de termenii anteriori:

Un exemplu de relație de recurență este:

Relația de recurență liniară[modificare | modificare sursă]

Un caz particular îl constituie șirurile ce pot fi definite printr-o recurență liniară finită, care este de forma:

Acesteia îi corespunde ecuația caracteristică:

Teorema 1. Dacă este o soluție a ecuației caracteristice , atunci șirul verifică relația de recurență

Teorema 2. Dacă șirurile îndeplinesc condiția de recurență și sunt liniar independente, atunci orice soluție se exprimă ca o combinație liniară a șirurilor adică există astfel încât:

Teorema 3. Există k șiruri liniar independente ce verifică relația de recurență.

  • Dacă ecuația caracteristică are soluții reale distincte șirurile sunt:

  • Dacă ecuația caracteristică are soluții reale multiple: cu ordinul de multiplicitate cu ordinul de multiplicitate cu ordinul de multiplicitate unde șirurile sunt:


Una dintre cele mai simple relații de recurență liniară definește „Șirul lui Fibonacci”, în care fiecare termen este egal cu suma celor doi termeni precedenți: