Suites récurrentes linéaires : théorie et pratique

Sur les suites récurrentes linéaires (comme Fibonacci). \r\rThéorème : une suite complexe est récurrente linéaire ssi il existe des polynômes et des complexes tels que \r\[\ru_n = \sum_{i=1}^k P_i(n) r_i^n\r\]\r\rLemme : une suite $u_n$ est récurrente linéaire d'ordre au plus $p$ si la matrice $A_n$ définie par $a_{i,j} = u_{i+j-2}$ est de rang au plus $p$.\r\rCe lemme permet en pratique de trouver une relation de récurrence linéaire satisfaite par une suite.