Récurrence forte vs simple : choisir le mauvais outil

L'erreur consiste à choisir une récurrence simple là où une récurrence forte est requise, ou inversement, à utiliser une récurrence forte alors qu'une simple suffit amplement. Dans le premier cas, la démonstration échoue. Dans le second, vous gaspillez un temps précieux et une énergie cognitive inutile. Prenons l'exemple de la suite de Fibonacci définie par $F_0=0,F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour $n\ge 2$. Si l'on tente de prouver par récurrence simple que $F_n$ est pair si et seulement si $n$ est un multiple de 3, l'hypothèse de récurrence simple ($P(n)$ vraie) est insuffisante pour établir $P(n+1)$ car $F_{n+1}$ dépend de $F_n$ et $F_{n-1}$.

Inversement, pour démontrer que $2^n>n$ pour tout $n\in \mathbb{N}$, une récurrence simple est parfaitement adéquate. Poser une hypothèse de récurrence forte (supposer $2^k>k$ pour tout $k\le n$) est correct mais inutilement lourd. Cette sur-spécification ne vous apporte rien de plus en termes de puissance de preuve et complexifie la rédaction.

Avant d'initier une preuve par récurrence, analysez attentivement la relation de récurrence elle-même. Observez de combien de termes précédents dépend le terme $P(n+1)$ ou $P(n)$. Si $P(n+1)$ ne dépend que de $P(n)$ (ou $P(n)$ ne dépend que de $P(n-1)$), une récurrence simple est généralement suffisante. Si $P(n+1)$ dépend de $P(n)$ et $P(n-1)$ (ou plus de termes antérieurs), alors la récurrence forte est indispensable.

• Check-list systématique :
• 1. Identifier la relation : Écrivez la relation de récurrence explicitement. Par exemple, $u_{n+1}=f(u_n)$ ou $u_{n+1}=g(u_n,u_{n-1})$.
• 2. Dépendance des termes : Si $u_{n+1}$ ne dépend que de $u_n$, optez pour la récurrence simple.
• 3. Dépendance multiple : Si $u_{n+1}$ dépend de $u_n$ et $u_{n-1}$ (ou plus), optez pour la récurrence forte.
• 4. Cas particulier : Si la propriété $P(n+1)$ ne s'appuie pas directement sur la valeur de $u_n$ mais sur une propriété de $n$ (par exemple, parité de $n$), la récurrence simple suffit si la propriété de $n+1$ peut être déduite de celle de $n$.

Cette distinction est cruciale dans les exercices de suites au BAC SM, notamment lors de l'étude de suites définies par des relations de récurrence d'ordre 2 (par exemple, $u_{n+2}=a{u}_{n+1}+b{u}_n$). Un exemple classique est la démonstration de propriétés de divisibilité ou de parité pour ces suites. En 2018, l'exercice 3 du sujet national de rattrapage demandait de prouver une inégalité sur une suite définie par $u_{n+1}=\frac{u_n^2}{2u_n-1}$. Ici, une récurrence simple était suffisante et attendue.

Les suites de type Fibonacci ou les suites récurrentes linéaires d'ordre 2 sont les terrains privilégiés où la récurrence forte est souvent nécessaire. Ne pas la choisir mène à un blocage immédiat dans la phase d'hérédité. L'examinateur du BAC SM attend une preuve correcte et efficiente. Une récurrence forte inutilement utilisée n'est pas pénalisée en soi si la preuve est juste, mais elle témoigne d'un manque de discernement méthodologique et peut vous faire perdre du temps précieux.