Résoudre toutes les suites récurrentes linéaires

Ce sont les suites du type : aU_n+bU_n+1+cU_n+1+dU_n+3+...=0

On utilise comme pour les équations différentielles linéaires un résultat des noyaux de polynômes d'endomorphismes avec ici l'endomorphisme translation T tel que T(U_n)=U_n+1, T²(U_n)=T(U_n+1)=U_n+2, ...

Exemple : la suite de Fibonacci U_n+2=U_n+1+U_n avec U0=1 et U1=1.
Le terme d'après est la somme des deux termes précédents. On a donc 1 1 2 3 5 8 13 21 ...

T²(U_n)-T(U_n)-U_n=0, c'est à dire (X²-X-1)(T)(U_n)=0 (1)
Factoriser ce polynôme en polynômes premiers entre eux donnera des solutions dont la somme sera la solution générale.

Il faut factoriser le polynôme caractéristique X²-X-1 :
Δ =5
x₁=(1-√5)/2 
x₂=(1+√5)/2 

d'où X²-X-1=(X-x₁)(X-x₂)

(1)⇔ (X-x₁)(X-x₂)(T)(U_n)=0
⇔(X-x₁)(T)(U_n)=0 ou (X-x₂)(T)(U_n)=0

Nous pouvons résoudre ces deux équations plus simples séparément.
En posant U_n=x₁ⁿU(n) avec U(n) polynôme en n.

T(x₁ⁿU(n))-x₁ⁿU(n)=0
⇔ x₁ⁿ⁺¹U(n+1)-x₁×x₁ⁿU(n)=0
⇔ x₁ⁿ⁺¹(U(n+1)-U(n))=0
⇔ U(n+1)-U(n)=0
⇔ U(n)=K₁
⇔ U_n=K₁x₁ⁿ

De même (X-x₂)(T)(U_n)=0 ⇔ U_n=K₂x₂ⁿ

D'où U_n=K₁x₁ⁿ + K₂x₂ⁿ avec K₁ et K₂ vérifiant U₀=1 et U₁=1

Après résolution du système et simplifications, nous trouvons :
Un=1/√5 (x₂ⁿ⁺¹ - x₁ⁿ⁺¹)

Addendum : Dans notre exemple, nous avons eu la chance d'avoir une factorisation avec des racines simples, c'est à dire que les polynômes de la factorisation étaient de la forme (X-k)¹ donc de degré 1.

Prenons le cas : U_n+2=6U_n+1-9U_n.
Nous obtenons : T²(U_n)-T(U_n)-9U_n=0 ⇔ (X²-6X+9)(T)(U_n)=0 ⇔(X-3)²(T)(U_n)=0 (2)

On pose U_n=3ⁿU(n) avec U(n) polynôme en n.
(2) ⇔(X-3)²(T)(3ⁿU(n))=0

Le degré d°(U(n+1)-U(n)) est un cran au dessous de d°(U(n)).
Si  V(n)=U(n+1)-U(n) et V(n+1)-V(n)=0, V(n)=a, U(n)=bn+c etc...

D'où (2) ⇔(X-3)(T)(T(3ⁿU(n))-3×3ⁿU(n))=0
             ⇔(X-3)(T)((3ⁿ⁺¹U(n+1))-3ⁿ⁺¹U(n))=0
             ⇔(X-3)(T)(3ⁿ⁺¹(U(n+1)-U(n))=0
             ⇔(X-3)(T)(3ⁿ⁺¹(V(n))=0
             ⇔3ⁿ⁺²(V(n+1)-V(n))=0
             ⇔(V(n+1)-V(n))=0
             ⇔V(n)=0 et U(n)=bn+c
             ⇔U_n=(bn+c)×3ⁿ.

Avec U₀=1 et U₁=1, on a :
(0+c)=1 et (b+c) × 3=1
c=1 et (b+1) × 3=1
c=1 et b=-2/3

Nous obtenons : U_n=(-2/3×n +1)×3ⁿ.
Si nous calculons les premiers termes avec la relation de récurrence, nous trouvons :
U₀=1 U₁=1
U₂=6-9=-3
U₃=6U₂-9U₁=-18-9=-27
U₄=6U₃-9U₂=-162+27=-135
La formule générale donne :
U₀=(-2/3×0 +1)×3⁰=1
U₁=(-2/3×1 +1)×3¹=1
U₂=(-2/3×2 +1)×3²=-1/3×9=-3
U₃=(-2/3×3 +1)×3³= -1×27=-27
U₄=(-2/3×4 +1)×3⁴= -5/3×3⁴=-5×3³=-135

Cela correspond ! Fou, non ?

Addendum 2 :
Lorsque l'on a
aU_n+bU_n+1+cU_n+1+dU_n+3+...=C, avec C constante, il faut ajouter à la solution de aU_n+bU_n+1+cU_n+1+dU_n+3+...=0 la solution constante A vérifiant
P(X)(T)(U_n)=C tel que P(X) soit un des facteurs choisis pour résoudre la solution.

Si P(X)=X-1, alors (X-1)(T)(U_n)=C correspond à
U_n+1=U_n+C, c'est une suite arithmétique de solution U_n=B+C×n.