Intégrité de suites récurrentes linéaires

Soient $p$ un entier naturel non nul, $t_{1}, \ldots, t_{p}$ des entiers deux à deux distincts et $\lambda_{1}, \ldots, \lambda_{p}$ des nombres complexes.

On définit la suite $(u_n)_{n \in \mathbb{N}}$ par la relation suivante :

\forall n \in \mathbb{N},   u_n = \sum_{i=1}^{p} \lambda_{i} t_{i}^{n}

On suppose que pour tout $k \in \{0, \ldots, p-1\}$ , on a $u_k \in \mathbb{Z}$ .

Démontrer que pour tout $n \in \mathbb{N}$ , l'élément $u_n$ est un entier.

1.

Introduire le polynôme unitaire dont les racines sont les entiers $t_1, \dots, t_p$ .

2.

Justifier que les coefficients de ce polynôme sont des entiers.

3.

Établir une relation de récurrence linéaire vérifiée par la suite $(u_n)$ et conclure par récurrence.

Idées clés

•

Lien entre les racines d'un polynôme et les suites récurrentes linéaires.

•

Propriété de stabilité de $\mathbb{Z}$ par combinaison linéaire à coefficients entiers.

1. Construction d'un polynôme annulateur à coefficients entiers.

Considérons le polynôme $P$ défini par :

P(X) = \prod_{i=1}^p (X - t_i)

Ce polynôme est unitaire de degré $p$ .

Puisque les $t_i$ sont des entiers, les coefficients de ce polynôme (qui sont, au signe près, les fonctions symétriques élémentaires des racines $t_i$ ) sont également des entiers.

On peut donc écrire :

P(X) = X^p - \sum_{k=0}^{p-1} a_k X^k   \text{avec}   \forall k \in \{0, \dots, p-1\}, \ a_k \in \mathbb{Z}

2. Établissement de la relation de récurrence.

Pour chaque $i \in \{1, \dots, p\}$ , $t_i$ est une racine de $P$ , donc $P(t_i) = 0$ . Ceci implique :

t_i^p = \sum_{k=0}^{p-1} a_k t_i^k

Multiplions cette égalité par $\lambda_i t_i^n$ pour un entier naturel $n$ quelconque :

\lambda_i t_i^{n+p} = \sum_{k=0}^{p-1} a_k \lambda_i t_i^{n+k}

En sommant sur l'indice $i$ allant de $1$ à $p$ , nous obtenons :

\sum_{i=1}^p \lambda_i t_i^{n+p} = \sum_{k=0}^{p-1} a_k \left( \sum_{i=1}^p \lambda_i t_i^{n+k} \right)

On reconnaît alors l'expression de la suite $(u_n)$ , ce qui nous donne la relation de récurrence linéaire suivante :

\boxed{\forall n \in \mathbb{N},   u_{n+p} = \sum_{k=0}^{p-1} a_k u_{n+k}}

3. Conclusion par récurrence.

Procédons par récurrence forte sur $n$ pour montrer que $u_n \in \mathbb{Z}$ .

Initialisation : Par hypothèse, pour tout $k \in \{0, \dots, p-1\}$ , $u_k \in \mathbb{Z}$ . L'initialisation est donc vérifiée pour les $p$ premiers termes.

Hérédité : Soit $n \ge 0$ . Supposons que $u_k \in \mathbb{Z}$ pour tout $k \in \{0, \dots, n+p-1\}$ .

D'après la relation de récurrence établie précédemment :

u_{n+p} = a_{p-1} u_{n+p-1} + a_{p-2} u_{n+p-2} + \dots + a_0 u_n

Comme les coefficients $a_k$ sont des entiers et que, par hypothèse de récurrence, les termes $u_{n}, \dots, u_{n+p-1}$ sont des entiers, alors par stabilité de $\mathbb{Z}$ par addition et multiplication :

\boxed{u_{n+p} \in \mathbb{Z}}

Par principe de récurrence, nous avons bien démontré :

\forall n \in \mathbb{N},   u_n \in \mathbb{Z}

Ne pas essayer de calculer explicitement les $\lambda_i$ via un système de Vandermonde. Bien que cela soit possible, les $\lambda_i$ ne sont généralement pas des entiers (ce sont des rationnels), ce qui compliquerait inutilement la preuve.