Relație de recurență

Î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

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: