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

Sur les suites récurrentes linéaires (comme Fibonacci). Théorème : une suite complexe est récurrente linéaire ssi il existe des polynômes et des complexes tels que \[ u_n = \sum_{i=1}^k P_i(n) r_i^n \] Lemme : 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$. Ce lemme permet en pratique de trouver une relation de récurrence linéaire satisfaite par une suite.