Raisonner par récurrence

Calculer les premiers termes d’une suite peut faire apparaître une régularité. Mais une propriété vérifiée pour cent entiers pourrait être fausse au suivant. Le raisonnement par récurrence permet de démontrer une proposition pour tous les entiers à partir d’un rang donné, en justifiant un point de départ et un passage d’un rang au suivant. Il ne remplace pas la recherche de l’idée ; il donne à cette idée une preuve générale.

On note P(n) la proposition à établir pour un entier n. L’initialisation vérifie P(n₀) au premier rang annoncé. L’hérédité montre que, pour un entier n quelconque au moins égal à n₀, si P(n) est vraie, alors P(n + 1) l’est aussi. La conclusion invoque ces deux étapes pour affirmer P(n) pour tout entier n ≥ n₀. Le premier rang peut être zéro, un ou un autre entier : il dépend de la propriété.

Dans l’hérédité, on suppose P(n) vraie à un rang fixé mais arbitraire. Cette hypothèse n’affirme pas déjà la propriété pour tous les rangs ; elle sert à construire une implication. Il faut ensuite obtenir exactement la proposition attendue au rang n + 1, avec les indices et les bornes modifiés. Supposer directement le résultat au rang suivant serait un raisonnement circulaire.

Le dessin suggère la preuve parce que la couche ajoutée contient 2n + 1 cases autour d’un carré de côté n. Mais une seule figure de côté quatre ne traite pas chaque entier. La démonstration algébrique précise ce que l’image généralise : une identité remarquable décrit l’augmentation de l’aire. Les deux représentations se complètent sans remplacer la justification par une impression visuelle.

Pour une somme, écris d’abord la somme au rang n + 1 comme la somme au rang n plus son dernier terme. Ce geste isole exactement l’expression à laquelle l’hypothèse de récurrence s’applique. L’erreur fréquente est de remplacer une partie qui ressemble à l’hypothèse mais qui ne contient pas les mêmes termes. Vérifier le nombre de termes et les premiers indices aide à l’éviter.

Une récurrence peut établir une inégalité plutôt qu’une identité. L’hypothèse doit alors être utilisée dans un sens qui rapproche du résultat cherché. Multiplier les deux membres par une quantité positive conserve le sens ; multiplier par une quantité négative le renverse. Cette vérification doit être explicite lorsque le facteur dépend d’un paramètre ou du rang.

Cette preuve garde a fixé pendant toute la récurrence. Le rang n change, le paramètre a ne change pas. L’inégalité montre notamment que, lorsque a > 0, les puissances de 1 + a sont supérieures ou égales à 1 + na. L’inégalité est une égalité aux rangs zéro et un, puis devient stricte pour n ≥ 2. Son utilisation pour les limites sera développée dans le chapitre suivant. Si a = 0, l’inégalité est une égalité à chaque rang.

Pour une suite définie par une relation uₙ₊₁ = f(uₙ), une propriété portant sur uₙ peut fournir des informations sur uₙ₊₁. Il faut vérifier que la relation est utilisable : par exemple, une racine carrée exige un nombre positif ou nul et une division un dénominateur non nul. Une borne peut donc servir à prouver simultanément que les termes existent et qu’ils restent dans un intervalle.

La borne supérieure deux et la croissance sont deux propriétés distinctes. On a d’abord démontré la borne par récurrence, puis utilisé cette borne pour étudier la différence. Une figure ne montre qu’un nombre fini de points ; elle ne prouve pas à elle seule que tous les termes suivants restent inférieurs à deux. La question de la limite nécessite un théorème et une justification supplémentaires.

Une initialisation seule ne transmet rien ; une hérédité seule ne démarre rien. Par exemple, la proposition n ≥ 1 est bien transmise du rang n au rang n + 1, mais elle est fausse au rang zéro. Sans initialisation correcte, on pourrait annoncer à tort une propriété dès zéro. À l’inverse, constater plusieurs débuts vrais ne fournit aucune implication générale.

Pour auditer une preuve, distingue la propriété annoncée, les faits déjà établis et ce qui est admis provisoirement. À la fin de l’hérédité, souligne mentalement P(n + 1) : si tu n’as obtenu qu’un cas particulier ou une inégalité différente, le passage n’est pas terminé. La conclusion doit reprendre le premier rang réellement vérifié et la quantification sur tous les entiers concernés.