Les suites récurrentes jouent un rôle fondamental en mathématiques, notamment dans l’étude des nombres entiers et des applications combinatoires. En ce sens, il arrive souvent que ces suites tombent aux écrits et il peut être intéressant de s’y préparer en connaissant plusieurs de ces suites classiques. Parmi elles : la suite de Jacobsthal.
Introduction
Introduite par Ernst Jacobsthal en 1909, cette suite trouve des applications en théorie des nombres, en informatique et dans les modèles de phénomènes naturels.
La suite de Jacobsthal apparaît en informatique, notamment dans les algorithmes d’ordonnancement et les systèmes de files d’attente. En combinatoire, elle est liée aux chemins dans un graphe où les transitions sont contraintes par des règles binaires. Dans le domaine de la cryptographie, elle est utilisée pour la génération de suites pseudo-aléatoires. En bref, c’est une suite qui possède de multiples champs d’application.
Dans cet article, nous allons définir la suite de Jacobsthal, explorer ses propriétés principales ainsi qu’étudier une variante : la suite de Jacobsthal-Lucas.
Définition de la suite de Jacobsthal
La suite de Jacobsthal est une suite récurrente linéaire d’ordre 2 définie par la relation suivante :
\(J_n = J_{n-1} + 2J_{n-2}, \quad \text{pour} \quad n \geq 2 \)
Avec les conditions initiales :
\(J_0 = 0, \quad J_1 = 1\)
Les premiers termes de la suite sont donc :
\(0,1,1,3,5,11,21,43,85,\dots \)
On observe que chaque terme est construit à partir des deux précédents, avec une pondération de 2 sur le second terme.
Propriétés de la suite de Jacobsthal
Formule explicite
Il est possible d’exprimer sous une forme fermée à l’aide des puissances de 2. La formule explicite est donnée par :
\( \large J_n = \frac{2^n – (-1)^n}{3} \forall n \in \mathbb{N}\)
Cette expression du terme général permet à l’évidence de calculer directement un terme sans passer par le calcul récursif.
On en déduit les formules de récurrence simples :
\(\large J_{n+1} = 2J_n + (-1)^n = 2^n – J_n\)
D’où :
\(\large J_{n+1} = 2^n \sum_{k=0}^{n} \frac{(-1)^k}{2^k} = (-1)^n \sum_{k=0}^{n} (-1)^k 2^k\)
Ces formules ne sont pas à retenir par cœur, mais tu peux simplement noter qu’il existe plusieurs expressions différentes de la suite de Jacobsthal qui permettent chacune de déceler différentes propriétés intéressantes de cette suite.
Démonstration rapide de cette formule avec les outils du programme
On revient d’abord à l’équation caractéristique de la suite à étudier :
\[
r^2 = r + 2
\]
que l’on résout comme inconnu \(r\)
\[
r = \frac{1 \pm \sqrt{1 + 8}}{2} = \frac{1 \pm 3}{2}
\]
Les racines sont :
\[
r_1 = 2 \quad \text{et} \quad r_2 = -1
\]
Il s’ensuit qu’il existe deux réels \(A\) et \(B\) tels que \(\forall n \in \mathbb{N}\) :
\[
J_n = A \cdot 2^n + B \cdot (-1)^n
\]
Déterminons ensuite les constantes en utilisant les conditions initiales \( J_0 = 0 \) et \( J_1 = 1 \) :
\[
J_0 = A \cdot 2^0 + B \cdot (-1)^0 = 0
\]
\[
J_1 = A \cdot 2^1 + B \cdot (-1)^1 = 1
\]
En résolvant ce système, nous obtenons :
\[
A = \frac{1}{3} \quad \text{et} \quad B = -\frac{1}{3}
\]
Ainsi, on obtient bien l’expression annoncée ci-dessus !
\[
J_n = \frac{1}{3} \cdot 2^n – \frac{1}{3} \cdot (-1)^n = \frac{2^n – (-1)^{n+1}}{3}
\]
Relation avec la suite de Fibonacci
La suite de Jacobsthal est intimement liée à la suite de Fibonacci. Dans la formule qui suit, on note \(F_k\) le nombre de Fibonacci d’ordre \(k\). On peut exprimer ainsi le nombre de Jacobsthal d’ordre \(n\) en fonction des nombres de Fibonacci de la manière suivante :
\(J_n = \sum_{k=0}^{\lfloor n/2 \rfloor} F_k 2^{n-2k-1} \)
Cette formule pourra éventuellement être redémontrée par récurrence, mais cela n’est pas l’objet direct de ce présent article.
Parité des termes
On peut observer que les termes de la suite de Jacobsthal alternent en parité. Cela signifie que \(J_k\) est impaire si \(k\) est impaire, et inversement. À partir de la formule explicite de la suite donnée précédemment, il est possible de démontrer cette formule par une récurrence en travaillant à partir des suites extraites \(J_{2n}\) et \(J_{2n+1}\).
En revenant à la définition par formule de récurrence de second ordre de la suite, il est possible de s’apercevoir que cette parité des termes est une conséquence de la présence du facteur \(2J_{n-2}\) dans la relation de récurrence.
Somme des premiers termes
La somme des premiers termes de la suite de Jacobsthal obéit à la relation suivante :
\(\large S_n = \sum_{k=0}^{n} J_k = J_{n+2} – 1\)
Cette propriété peut être également démontrée par récurrence. En calculant les premiers termes de la somme, il aurait été possible de s’apercevoir « à la main » de cette relation.
Suite de Jacobsthal-Lucas
La suite de Jacobsthal-Lucas est une variante de la suite de Jacobsthal, définie par une relation récurrente similaire :
\( C_n = C_{n-1} + 2C_{n-2}, \quad \text{pour} \quad n \geq 2 \)
Jusqu’à présent, on est d’accord que la relation de récurrence ne varie pas par rapport à la suite de Jacobsthal « classique » !
Mais les conditions initiales changent cette fois-ci par rapport à la suite de Jacobsthal (voir la première définition de la suite de Jacobsthal) :
\( C_0 = 2, \quad C_1 = 1\)
Cette suite partage de nombreuses propriétés avec la suite de Jacobsthal, mais commence avec des valeurs différentes, ce qui lui confère une dynamique propre.
Propriétés de la suite de Jacobsthal-Lucas
Cette suite particulière n’est pas directement l’objet de cet article, mais elle est tellement liée à la suite de Jacobsthal que nous nous devons de relever quelques propriétés de cette dernière.
Expression explicite
L’expression explicite de \( C_n \) est :
\[
C_n = 2^n + (-1)^n
\]
Encore une fois, il est possible de démontrer cela en utilisant l’équation caractéristique associée à la suite \(C_n\).
Relation avec la suite de Jacobsthal
La suite de Jacobsthal-Lucas est liée à la suite de Jacobsthal par :
\[
C_n = 2J_n + (-1)^n J_{n-1}
\]
Nous n’effectuerons pas la démonstration ici, mais un calcul direct pourrait faire l’affaire, maintenant que l’on connaît les expressions explicites des deux suites \(C_n\) et \(J_n\).
Conclusion
La suite de Jacobsthal, bien que moins connue que la suite de Fibonacci, présente des propriétés mathématiques remarquables et trouve des applications variées en informatique, en combinatoire et en théorie des nombres. Sa récurrence simple, mais puissante, en fait un outil intéressant pour modéliser divers phénomènes mathématiques et informatiques.
Cette suite n’est pas encore tombée dans un sujet d’écrit ou d’oral de mathématiques en voie appliquée ou approfondie. Néanmoins, celle-ci est très proche de la suite de Fibonacci, qui a déjà fait l’objet de nombreux sujets de concours. Il n’y a plus qu’à espérer que cette notion finisse par tomber !
Tu peux retrouver le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder à toutes nos autres ressources mathématiques !
