Démonstration par récurrence

Lycée

Le raisonnement par récurrence est un grand classique de la spécialité maths au lycée. Mais c’est quoi la récurrence ? Et comment je peux m’entrainer ?

Demain comme aujourd’hui

Un phénomène récurrent est un phénomène qui se répète. La quasi-totalité des suites mathématiques vues au lycée sont définies par récurrence. Un exemple simple ? La suite \((1 ; 3 ; 5 ; 7 ; 9 ; 11 ; …)\) peut se résumer ainsi : “Prends le dernier nombre obtenu et ajoute 2. Puis recommence. Autant de fois que tu veux.”

Avec les notations mathématiques, cela s’écrit \(u_{n+1} = u_n + 2\), ce qui signifie “le terme suivant est le terme actuel plus deux”.

Les nombres n et n+1 ne sont pas propres aux mathématiques. En comptabilité on parle de l’année “n” pour l’année étudiée (par exemple 2025), de l’année “n+1” pour l’année suivante, de l’année “n-1” pour l’année précédente. Le jour “J” est un classique également pour parler de la date d’un évènement. Le jour “J-1” est la veille de l’évènement, le jour “J+1” sera le lendemain.

Pourquoi tant de n ?

La lettre n est aux nombres entiers ce que x est aux nombres réels. Pour toi ce peut être un espace de liberté : tu remplaces n par le nombre entier de ton choix. Ou alors une forte contrainte : tu dois montrer qu’une propriété est vraie pour tous les nombres entiers, de zéro jusqu’à … l’infini !

exemple 1 : montre qu’il existe un entier n tel que 3n+2 est supérieur ou égal à 10
exemple 2 : montre que pour tout entier n le nombre (n+2) + (n-1) + (n+8) est un multiple de 3

Dans le premier exemple, il te suffit de trouver un entier. Essaye avec n=0, ou n=2, ou n=5, peu importe. Du moment que l’un de tes essais donne un résultat plus grand que 10. Le deuxième exemple se traite différemment ; pendant la phase de recherche tu peux remplacer n par n’importe quelle valeur pour comprendre comment fonctionne la formule. Mais, dans la démonstration, n restera … n. Pas 0, ni 2, ni 5, simplement n.

démonstration : pour tout entier \(n\text{, }(n+2) + (n-1) + (n+8) = 3n + 9 = 3\times(n+3)\) est un multiple de 3

Passage à n+1, de quoi parle-t-on ?

Le nombre de diagonales d’un polygone régulier à n côtés est \(d_n=\large{n\times(n-3)\over2}\).
Combien de diagonales a le polygone régulier à (n+1) côtés ?

Pour n+1 côtés : \(d_{n+1}={\large{(n+1)\times(n+1-3)\over2}}={\large{(n+1)(n-2)\over2}}\)
Il a suffi de remplacer tous les “n” de la formule par n+1 ou (n+1)

On peut vraiment remplacer n par n+1 ???

Euh, oui, mais, euh … il faut faire attention tout de même…

Tu as sans doute remarqué que ton prof prenait parfois des précautions de rédaction qui semblent un peu exagérées, avec des “il existe un entier n” et “pour tout entier n”. Eh bien, je dois dire qu’il a raison.

As-tu déjà noté la différence entre \((x+3)(x-3)=x^2-9\) et \(x(x-3)=x^2-9\) ?
La première égalité est une identité remarquable, valable quelle que soit la valeur de x.
La deuxième est une équation, qui n’est vraie que lorsque x est égal à 3.

Dans l’identité, tu peux remplacer x par n’importe quel nombre, y compris par x+1 ; l’égalité reste vraie.
Dans l’équation, l’égalité est généralement fausse. Seule la valeur 3 permet de la rendre vraie.

Pour faire simple, tu as le droit de remplacer n par n+1, mais seule la lecture de l’énoncé te permet de dire si le résultat obtenu est vrai, ou est à démontrer.

exemple 3 : pour tout n supérieur ou égal à 3, \(d_n=\large{n\times(n-3)\over2}\) ; montre que la suite \(\left(d_n\right)\) est croissante ;
exemple 4 : démontre par récurrence que pour tout n supérieur ou égal à 3, \(d_n=\large{n\times(n-3)\over2}\)

Dans l’exemple 3, la démonstration commencera par “pour tout n supérieur ou égal à 3, \(d_{n+1}={\large{(n+1)(n-2)\over2}}\)” et finira par \(\text{pour tout }n\geq3, d_{n+1}-d_n>0\)“.
Dans l’exemple 4, la démonstration commencera par “soit un entier n tel que \(d_n=\large{n\times(n-3)\over2}\), on va montrer que \(d_{n+1}={\large{(n+1)(n-2)\over2}}\)” et finira par “on en déduit que pour tout n supérieur ou égal à 3, \(d_n={\large{n(n-3)\over2}}\)”

“Initialisation, hérédité, conclusion”, la devise de la démonstration par récurrence

Cet article commençait par la suite \((1 ; 3 ; 5 ; 7 ; 9 ; 11 ; …)\) et son principe : “Prends le dernier nombre obtenu et ajoute 2. Puis recommence. Autant de fois que tu veux.”

C’est bien gentil de permettre de prendre le dernier nombre obtenu, mais pour commencer, comment fait-on ?
Il faut ajouter l’information : “Le premier terme est 1”.

C’est un peu le même principe dans les démonstrations par récurrence. Tu as le droit d’écrire “soit un entier n tel que \(d_n=\large{n\times(n-3)\over2}\)…” mais il faudra bien à un certain moment donner un exemple d’entier pour lequel l’égalité est vraie.

Par exemple, pour les diagonales, tu peux utiliser le carré, donc n=4. Le carré a deux diagonales, et la formule donne \({\large{4\times(4-3)\over2}}=2\)

Le schéma de la démonstration par récurrence sera alors

initialisation : la relation est vraie pour le polygone à 4 côtés
hérédité : si la relation est vraie pour 4 côtés elle sera vraie pour 5 côtés ; si elle est vraie pour 5 côtés, elle sera vraie pour 6 côtés ; si elle est vraie pour 6 côtés … etc
conclusion : la relation est vraie pour tous les polygones réguliers à 4 côtés ou plus

Et le triangle équilatéral ?
La démonstration par récurrence permet de montrer que toutes les égalités sont vraies, à partir du rang de l’initialisation. D’où l’intérêt de commencer par la plus petite valeur possible de n.
Si tu as oublié le cas n = 3, inutile de reprendre la démonstration à zéro, tu peux simplement traiter ce cas à part : un triangle équilatéral n’a pas de diagonale, et la formule donne \({\large{3\times(3-3)\over2}}=0\) donc l’égalité est vraie également pour n = 3.

Un exemple de démonstration complète

La suite des tours de Hanoï — voir sur Wikipedia — est définie par \(\begin{cases}u_{n+1}=2u_n+1\text{ pour tout }n\geq1\\u_1=1\end{cases}\)

7 déplacements pour la tour de 3 étages, 1 déplacement pour l’étage supplémentaire, 7 nouveaux déplacements pour poser la tour de 3 étages sur cet étage supplémentaire, donc 2 x 7 + 1 mouvements pour les 4 étages

\(u_n\) est le nombre de déplacements nécessaires pour déplacer une tour de \(n\) étages.
Ainsi \(u_1=1\) signifie qu’une tour n’ayant qu’un étage peut être déplacée en un seul mouvement.

Démontrer par récurrence que la suite est croissante

Il s’agit de montrer que chaque terme de la suite est plus grand que celui qui le précède. Ce qui pourrait s’écrire \(u_n\geq{}u_{n-1}\) mais que l’on préfère écrire sous la forme \(u_{n+1}\geq{}u_n\) pour éviter de s’embêter avec le cas \(n=1\) ; que vaudrait alors \(u_{n-1}\) ?

Tu dois démontrer la propriété suivante : \(\text{pour tout }n\geq1\text{, }u_{n+1}\geq u_n\).

1. recherche, au brouillon

\(u_2=2u_1+1=2\times1+1=3\) et \(u_3=2\times{}u_2+1=2\times3+1=7\)
\(u_2\geq{}u_1\) et \(u_3\geq{}u_2\)
en calculant les premiers termes, on observe que la suite est effectivement croissante jusqu’à \(n=3\)
tu ne peux pas calculer tous les termes, il y en a une infinité
comment pourrais-tu passer de la relation \(u_3\geq{}u_2\) à \(u_4\geq{}u_3\) sans calculer \(u_4\) ?
tu es passé d’un terme à l’autre en multipliant par 2 et en ajoutant 1
utilise le même procédé avec les inégalités
\(u_3\geq{}u_2 => 2u_3\geq 2u_2 =>2u_3+1\geq 2u_2+1 =>u_4\geq u_3\)
tu viens d’écrire l’hérédité au rang \(n = 3\), il ne te reste plus qu’à généraliser avec \(n\) quelconque

2. rédaction

initialisation :
- \(u_1=1\) et \(u_2=3\)
- \(u_2\geq u_1\)
- la propriété \(u_{n+1}\geq u_n\) est vraie au rang \(n=1\)
hérédité :
- soit un entier \(n\) tel que la propriété \(u_{n+1}\geq u_n\) soit vraie
- je vais montrer que cette propriété reste vraie au rang suivant, c’est-à-dire que \(u_{n+2}\geq u_{n+1}\)
- \(u_{n+1}\geq u_n => 2u_{n+1}\geq 2u_n =>2u_{n+1}+1\geq 2u_n+1 =>u_{n+2}\geq u_{n+1}\)
conclusion :
- la propriété \(u_{n+1}\geq u_n\) est vraie au rang \(n=1\) et héréditaire
- j’en déduis qu’elle est vraie pour tout rang supérieur ou égal à 1

Démontrer par récurrence que, pour tout n, \(u_n=2^n-1\)

1. recherche, au brouillon

\(u_1=1\) et \(2^1-1=2-1=1\) donc \(u_1\) est égal à \(2^1-1\)
\(u_2=3\) et \(2^2-1=4-1=3\) donc \(u_2\) est égal à \(2^2-1\)
\(u_3=7\) et \(2^3-1=8-1=7\) donc \(u_3\) est égal à \(2^3-1\)
comment pourrais-tu vérifier la propriété au rang 4, sans calculer \(u_4\) ?
\(u_4=2u_3+1\)
il est tentant de remplacer \(u_3\) par \(7\), mais cela reviendrait à calculer \(u_4\)
remplace plutôt \(u^3\) par \(2^3-1\)
\(u_4=2\left(2^3-1\right)+1\)
distribue le coefficient 2 sans calculer la puissance
\(u_4=2^4-2+1\)
\(u_4=2^4-1\) ; c’est la propriété recherchée
passe à la rédaction en généralisant

2. rédaction

initialisation :
- \(u_1=1\) et \(2^1-1=2-1=1\) donc \(u_1=2^1-1\)
- la propriété \(u_n=2^n-1\) est vraie au rang \(n=1\)
hérédité :
- soit un entier \(n\) tel que la propriété \(u_n=2^n-1\) soit vraie
- je vais montrer que cette propriété reste vraie au rang suivant, c’est-à-dire que \(u_{n+1}=2^{n+1}-1\)
- \(u_{n+1}=2u_n+1 =2\left(2^n-1\right)+1 =2^{n+1}-2+1=2^{n+1}-1\)
conclusion :
- la propriété \(u_n=2^n-1\) est vraie au rang \(n=1\) et héréditaire
- j’en déduis qu’elle est vraie pour tout rang supérieur ou égal à 1

Bilan pour les tours de Hanoï

La suite est croissante ; cela signifie que plus la tour a d’étages, plus le nombre d’étapes pour la déplacer est important. On s’en doutait un peu 😏

Une tour de n étages nécessite \(2^n-1\) mouvements. Ainsi, pour une tour de dix étages, tu devra effectuer \(2^10-1=1023\) mouvements. J’espère que tu n’a pas un train à prendre 😁