Mathématiques - Raisonnement par récurrence

Mathématiques : Raisonnement par récurrence

Aucun commentaire

Le raisonnement par récurrence est un raisonnement très puissant souvent utilisé en mathématiques. Il permet en général de démontrer des propriétés qui dépendent d'entiers, naturels ou relatifs (qui commencent par : quelque soit n entier naturel...).

On pourra distinguer plusieurs types de raisonnements par récurrence :

Le raisonnement simple. On l'étudie en général à partir du lycée et si vous en êtes à cette étape la de votre scolarité, peut-être ne vous paraît-il pas si "simple" Pourtant vous verrez que ce n'est pas très compliqué ! Si, si, c'est vrai !!
Le raisonnement multiple. Âme sensible s'abstenir ^-^ Enfin, cela dit, personne n'en est encore mort !

Je vais commencer par expliquer de manière très simple le raisonnement par récurrence dans ce cours, puis je ferai un tour plus approfondi des raisonnements par récurrence simple et multiple pour satisfaire les plus curieux mini_bn

.

Vous vous apercevrez très vite que le principe est simple, mais l'application est parfois un peu plus délicate ! (ce ne serait pas marrant sinon bn_wink

) Mais ce cours devrait vous apprendre à éradiquer toutes les démonstrations récalcitrantes !
Je préfère vous prévenir tout de suite : j'utilise tout un tas de termes mathématiques qui peuvent vous rebuter au début, mais ne vous inquiétez pas, j'explique tout ! Et au pire, c'est pas très important pour comprendre le principe. bn_heureux

Il est aussi possible que vous n'ayez pas les connaissances mathématiques nécessaire pour suivre toutes les parties de ce cours, (j'utilise certaines notions qu'on ne voit qu'au lycée, voire plus tard) donc ne stressez pas trop si vous ne comprenez pas tout et n'hésitez pas à poser vos questions sur le Bar à Nougat. (forum de la Bnbox)
Vous êtes prêt ? Alors... à l'assaut !

Pour les nuls en orthographe (comme moi bn_hmm

) il y a un seul C et deux R à "récurrence"

Raisonnement par récurrence (version simplifiée)

Concrêtement on va vous demander de prouver une propriété mathématique, par exemple la suivante :
$\forall n \in \mathbb{N} \,\, S_n=1+2+...+n=\frac{n(n+1)}{2}.$
Traduisons : Montrons que, quelque soit l'entier naturel (1, 2, 5...) n, la somme des entiers naturels de 1 à n est égale à $\frac{n(n+1)}{2}$

Vous pourrez aussi trouver cette propriété sous la forme :

$\forall n \in \mathbb{N} \,\, \sum_{k=0}^n k = \frac{n(n+1)}{2}$

Vous l'avez peut-être vu ainsi en parlant des suites.

Nous allons raisonner en 3 étapes. Soyez bien attentif car il faut toujours effectuer ces trois étapes, et les effectuer dans l'ordre.

On vérifie que la propriété est vraie pour n=0. (n est alors le plus petit possible) On dit alors que la propriété est initialisée.

Pour n=0 $S_0=0$ et $\frac{0(0+1)}{2}=0$
Donc la propriété est bien vraie pour n=0, et donc initialisée.
On suppose que, pour n fixé, notre propriété est vraie au rang n. (C'est-à-dire pour un n donné et fixé.) C'est l'hypothèse de récurrence. On démontre alors, grâce à l'hypothèse de récurrence que la propriété est toujours vraie au rang suivant, c'est-à-dire n+1.
Cela vérifié, on peut alors dire que la propriété est héréditaire. (C'est comme ça qu'on dit, pas ma faute...)

Supposons que, pour n fixé, la propriété est vraie au rang n. Alors :
$S_{n+1}=1+2+...+n+(n+1) = \frac{n(n+1)}{2}+(n+1) = \frac{n(n+1)+2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$
Donc la propriété est héréditaire.

Donc on a montré que si la propriété était vraie pour un entier donné, elle était aussi vraie pour l'entier suivant. N'ayant pas précisé cet entier, et puisque la propriété est vraie à l'entier le plus petit qui nous intéresse (ici 0), elle est forcément vraie au rang 1, puis 2, puis 3, etc... c'est-à-dire pour tout entier!

Conclusion : On a démontré que la propriété était vraie pour n=0 et qu'elle était héréditaire. Par conséquent, on a démontré que : $\forall n \in \mathbb{N} \,\, S_n=1+2+...+n=\frac{n(n+1)}{2}.$

Et voilà ! Rien de très sorcier vous voyez. Si vous désirez aller plus loin avec le raisonnement par récurrence, la suite de ce cours est faîte pour vous. Si vous ne comprenez pas tout, n'hésitez pas à relire et à poser des questions sur le Bar à Nougat. Nous verrons d'autres exemples d'utilisation un peu plus loin.

Quand utiliser ce raisonnement ?

On a souvent tendance à n'utiliser le raisonnement par récurrence qu'en dernier recours (entre nous, c'est pas vrai ? bn_tongue

) pourtant il permet bien souvent d'éviter de se torturer le cerveau ! Encore faut-il savoir l'utiliser à bon escient.
((
Je vais utiliser quelques termes savants puis je traduirai en Français courant. (Ne fuyez donc pas tout de suite. bn_tongue

)
Soit $A(n)$ un prédicat de référentiel $\mathbb{N}$ . Le raisonnement par récurrence s'emploie lorsque l'on veut prouver que : $\forall n \in \mathbb{N} \,\, A(n)$
Où : $\forall n \in \mathbb{N} \,\, A(n)$ est la propriété que l'on nous demande de prouver.

Le symbôle $\forall$ signifie "Quelque soit", "Pour tout".
Le symbôle $\in$ signifie "appartient".
Ce sont des symbôles Mathématique compréhensible par les matheux des quatre coins de la planète !!

Avant tout, définissons le mot prédicat :
Soit E un ensemble d'élément. (c'est à dire un ensemble de nombres, de chiffres, de patates,de carottes, de BN, bref de tout ce que vous voulez !) Un prédicat de référentiel E est un énoncé de la forme : $A(x, y, ...)$ où x et y sont des lettres appelés variables telles que lorsque l'on transforme ces variables par des objets on obtienne quelque chose qui est vrai ou faux.

Elles sont marrantes tes blagues, mais est-ce que tu pourrais passer tout de suite au Français normal la, steuplait ?

Puisque c'est demandé si gentiment... bn_big_smile

Utilisons une image pour comprendre ce qu'est un prédicat. Imaginez une petite boîte dans laquelle on puisse mettre certains objets. On pourrait s'amuser à tester quels objets rentrent dans cette boîboîte ! (c'est un peu débile je vous l'accorde bn_tongue

) On peut par exemple y faire entrer un stylo, une punaise, un BN, un bonbon. Par contre, on aura certainement plus de mal à y faire entrer un éléphant ! Où alors il nous faudrait une très très grosse boîte !
$A(n)$ est un peu comme cette boîte. Nos objets seront les n. Et en raisonnant, on cherche à démontrer que avec tel n, A(n) est vraie, et que pour tel autre, A(n) est fausse. (Ce qui correspond à un objet pouvant entrer dans la boîte et un autre étant trop grand pour y pénétrer.)

Pour les matheux pur et dur, sachez qu'un prédicat n'est ni vrai ni faux. En effet dans un prédicat on ne précise pas ce qu'est la variable. (c'est comme si on vous disait : "j'ai une boîte et je vais faire entrer des objets dedans", ne connaissant ni la taille de la boîte, ni celle des objets, vous êtes dans l'incapacité de me dire si mon objet rentrera ou non dans la boîte.
Par contre si on précise ce qu'est la variable de notre prédicat, on peut répondre. Le tout s'appelle alors une assertion. Par exemple le prédicat suivant : A(n) "n est un entier" On pourra dire que A(2) est vraie (2 est bien un entier) mais que A(2.5) est fausse (2.5 n'est pas un entier) de la même manière $\forall n \in \mathbb{Z} \,\, A(n)$ est vraie ! (Quelque soit le n appartenant à l'ensemble des entiers relatifs, n est un entier !)
Bref, c'était le petit interlude pour les matheux qui veulent se la raconter avec du vocabulaire. bn_wink

Si vous avez du mal à comprendre ces subtilités (on ne vous en voudra pas^^ Je n'ai vu ça qu'en première année de prépa, c'est pour dire.) n'hésitez pas à poser des questions sur le Bar à Nougat.

Vous pouvez lire une définition expliquée un peu différemment sur le cours à propos des bases de la logique de DarKnight bn_wink

Rappelez-vous ce qu'on nous avait demandé de prouver : $\forall n \in \mathbb{N} \,\, A(n)$
On peut traduire cette phrase mathématique par : "Quelque soit l'entier naturel n, A(n) est vraie". Bref, on nous demande de prouver que ce que dit cette phrase est vraie ! (ou faux^^)
Et c'est dans ces conditions que l'on se sert du raisonnement par récurrence. Quand on nous demande de démontrer quelque chose quelque soit n alors il est possible que la récurrence soit une bonne méthode.

Ayez du flair ! Si la phrase en question a l'air vraie, qu'elle semble assez tordue et qu'on vous demande de la démontrer quelque soit n, alors il y a beaucoup de chance que le raisonnement par récurrence soit la bonne méthode.
Si la phrase vous semble fausse, alors il vous faudra vous tourner vers un autre raisonnement. (notamment vers le raisonnement par l'absurde que DarKnight vous explique sur la Bnbox bn_wink

)

Raisonnement simple

Principe

Il y a trois étapes dans le raisonnement par récurrence qu'il faut bien suivre et dans l'ordre. Démontrons par récurrence cette propriété : $\forall n \in \mathbb{N} \,\, A(n)$
En traduisant : Montrons que, quelque soit l'entier naturel (1, 2, 5...) n, la phrase A(n) est vraie.

Etape d'initialisation : On vérifie que la propriété est vraie au rang le plus petit possible. C'est à dire pour n le plus petit possible. (Par exemple n=0. C'est souvent le cas)
On suppose que, pour n fixé, la propriété est vraie au rang n. (c'est à dire pour un n donné.) C'est l'hypothèse de récurrence. On démontre alors, grâce à l'hypothèse de récurrence que la propriété est toujours vraie au rang n+1.
Cela vérifié, on peut alors dire que la propriété est héréditaire.
La phrase suivante : On suppose que, pour n fixé, la propriété est vraie au rang n. est celle qui vous servira tout le temps, donc n'hésitez pas à l'apprendre par coeur !
Conclusion : On a démontré que la propriété était vraie au plus petit rang possible et qu'elle était héréditaire. Par conséquent, on a démontré que : $\forall n \in \mathbb{N} \, \,A(n)$

On peut traduire cette définition simplement en langage mathématique, cela veut dire exactement la même chose.
$\left.\begin{array}{lcl} A(0)&&\\\forall n \in \mathbb{N} \,\, (A(n) \Longrightarrow A(n+1))\\\end{array}\right\} \Longrightarrow \forall n \in \mathbb{N} \,\, A(n)$

Ce raisonnement vous paraît peut-être simple, voir trop simple. Nous verrons dans les exemples que la réalité est parfois tout autre. Peut-être que vous ne comprenez pas la logique de ce raisonnement, peut-être même doutez vous de sa véracité. Jusqu'au lycée on ne vous demande pas de prouver ce raisonnement, vous avez donc le droit de faire confiance à vos professeurs. bn_heureux

Mais si vous êtes curieux ou que vous avez déjà dépassé les années lycées, sachez que l'on démontrera ce raisonnement à la fin de ce cours !! Niark, niark bn_cool

Maintenant que vous savez en théorie ce qu'est le raisonnement par récurrence, passons à quelques exemples : on va voir ce que vous valez vraiment. mini_bn

Exemple 1

Montrez que :

$\forall n \in \mathbb{N} \,\, \sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}$

Si vous voulez devenir un ou une boss du raisonnement par récurrence, il serait bon que vous trouviez la réponse à cet exemple tout seul... (ça ne prend pas très longtemps, je vous assure mini_bn

) En tout cas, voici comment il faut faire.

Vous avez ci-dessous la manière dont je rédigerai cet exercice en étant rigoureux. Cela dit, on peut vous imposer des fioritures et il vaut toujours mieux faire ce qui vous est demandé bn_tongue

Pour n=0 :
$\sum_{k=0}^0 k^2 = 0$ et $\frac{0(0+1)(2 \times 0+1)}{6}=0$
Supposons que, pour n fixé, la propriété soit vraie, c'est à dire :
$\sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}$
Alors au rang (n+1) :
$\sum_{k=1}^{n+1} k^2 = (\sum_{k=1}^{n} k^2)+(n+1)^2= \frac{n(n+1)(2n+1)}{6}+(n+1)^2$
$\,\,\,\,\,\,\,\,= \frac{n(n+1)(2n+1)+6(n+1)(n+1)}{6}= \frac{(n+1)[2n^2+n+6n+6)]}{6}= \frac{(n+1)(n+2)(2(n+1)+1)}{6}$
On a donc démontré que la propriété était vraie au rang 0, qu'elle était héréditaire, donc : $\forall n \in \mathbb{N} \,\, \sum_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6}$

Et voilà ! Pour vous entrainer, vous pouvez aussi démontrer que :

$\forall n \in \mathbb{N} \,\, \sum_{k=0}^n k^3 = \frac{n^2(n+1)^2}{4}$

Exemple 2

Vous croyiez être devenu un boss du raisonnement par récurrence ? Vous croyiez avoir tout compris ? Voilà qui devrait vous convaincre de la difficulté et de la puissance de ce raisonnement,en effet, nous allons effectuer deux raisonnements par récurrence à la fois. (âme sensible, s'abstenir) Rassurez-vous, si vous n'avez pas dépassé les années lycées, on ne vous demandera pas de comprendre cela.
Nous allons utiliser la suite de Fibonnacci :
$\left\{\begin{array}{lcl} F_0=1&&\\F_1=1\\\forall n \in \mathbb{N} \,\, F_{n+2}=F_{n+1}+F_n\\\end{array}\right\.$
Montrons que :
$\forall n \in \mathbb{N}^* \,\,\, \left\{\begin{array}{lcl} F_{2n-1} = 2 \times F_n \times F_{n-1} - (F_{n-1})^2 &&\\F_{2n} = (F_n)^2 + (F_{n+1})^2\\\end{array}\right\.$

Pour n=1 :
$\left\{\begin{array}{lcl} F_1 = 2 \times 1 - 1 = 2 \times F_1 \times F_0 - F_0^2 &&\\F_2 = 1 \times 1 = (F_1)^2 + (F_0)^2\\\end{array}\right\.$
Supposons que, pour n fixé, $F_{2n}$ et $F_{2n-1}$ soient vrais. Alors :
$\left\{\begin{array}{lcl} F_{2n+1} = F_{2n} \times F_{2n-1}&&\\F_{2n+2} = F_{2n+1} + F_{2n} = 2 \times F_{2n} + F_{2n-1} \,\,\,\, (1)\\\end{array}\right\.$

$(1) \, \Longleftrightarrow \,\, \left\{\begin{array}{lcl} F_{2n+1} = (F_{n})^2 + (F_{n-1})^2 + 2 \times F_n \times F_{n-1} - (F_{n-1})^2&&\\F_{2n+2} = 2 \times (F_{n})^2 + 2 \times (F_{n-1})^2 + 2 \times F_n \times F_{n-1} - (F_{n-1})^2\\\end{array}\right\.$

Or $(F_{n})^2 + (F_{n-1})^2 = F_{2n}$ Donc :

$(1) \, \Longleftrightarrow \,\, \left\{\begin{array}{lcl} F_{2n+1} = (F_{n})^2 + 2 \times F_n \times F_{n-1}&&\\F_{2n+2} = \, F_{2n} + 2 \times F_n \times F_{n+1} - (F_{n})^2 = \, (F_{n-1})^2 + 2 \times F_n \times F_{n+1}\\\end{array}\right\.$

Or $2 \times F_n \times F_{n-1} \, = \, 2 \times F_n \times (F_{n+1} - F_n)$ Donc :

$(1) \, \Longleftrightarrow \,\, \left\{\begin{array}{lcl} F_{2n+1} = 2 \times F_n \times F_{n+1} - (F_{n})^2&&\\F_{2n+2} = \, (F_{n+1})^2 - 2 \times F_n \times F_{n+1} + (F_{n})^2 + 2 \times F_n \times F_{n+1}\\\end{array}\right\.$

D'où :
$(1) \, \Longleftrightarrow \,\, \left\{\begin{array}{lcl} F_{2n+1} = 2 \times F_n \times F_{n+1} - (F_{n})^2&&\\F_{2n+2} = \, (F_{n+1})^2 + (F_{n})^2\\\end{array}\right\.$

La propriété est donc héréditaire.
Par conséquent, on a bien démontré que :
$\forall n \in \mathbb{N}^* \,\,\, \left\{\begin{array}{lcl} F_{2n-1} = 2 \times F_n \times F_{n-1} - (F_{n-1})^2 &&\\F_{2n} = (F_n)^2 + (F_{n+1})^2\\\end{array}\right\.$

Raisonnement multiple

Principe

Il y a toujours trois étapes au raisonnement par récurrence multiple qu'il faut bien suivre et dans l'ordre.
Prenons comme exemple la suite de Fibonacci :
$\left\{\begin{array}{lcl} F_0=0&&\\F_1=1\\\forall n \in \mathbb{N} \,\, F_{n+2}=F_{n+1}+F_n\\\end{array}\right\.$
Et montrons que $\forall n \in \mathbb{N} \,\, F_n \in \mathbb{N}$ ce qui se traduit par : Quelque soit l'entier naturel n, montrons que Fn est aussi un entier naturel.

Etape d'initialisation : On vérifie que la propriété est vraie au rang le plus petit possible et un rang plus haut. C'est à dire pour n le plus petit possible et le n situé juste au dessus. (ici n=0 et n=1. C'est souvent le cas)

Pour n=0, on a bien $F_0 \in \mathbb{N}$
Pour n=1, on a bien $F_1 \in \mathbb{N}$
On suppose que, pour n fixé, la propriété est vraie au rang n et au rang n+1. (c'est à dire pour un n donné) C'est l'hypothèse de récurrence. On démontre alors, grâce à l'hypothèse de récurrence que la propriété est toujours vraie au rang n+2.
Cela vérifié, on peut alors dire que la propriété est héréditaire.
On dit aussi parfois : On suppose que, pour n fixé, la propriété est vraie jusqu'au rang n. Mais si on utilise 3 hypothèses, il ne faut pas oublier d'initialiser 3 fois ! (donc de vérifier que ça marche jusqu'à n=3)

$F_{n+2} = F_{n+1} + F_n$
Donc, d'après l'hypothèse de récurrence : $F_{n+2} \in \mathbb{N}$
Conclusion : On a démontré que la propriété était vraie au plus petit rang possible et qu'elle était héréditaire. Par conséquent, on a démontré que : $\forall n \in \mathbb{N} \,\, F_n \in \mathbb{N}$

Exemple 1

On va de nouveau utiliser la suite de Fibonnacci :
$\left\{\begin{array}{lcl} F_0=1&&\\F_1=1\\\forall n \in \mathbb{N} \,\, F_{n+2}=F_{n+1}+F_n\\\end{array}\right\.$
Et cette fois-ci, nous allons tenter de démontrer la propriété suivante :
$\forall (n,p) \in (\mathbb{N}^*)^2 \,\, F_{n+p} = F_n \times F_p + F_{n-1} \times F_{p-1}$ On la notera $\mathcal{P}(n)$ .

Soit $p \in \mathbb{N}^*$ fixé. (en effet, on ne fait une récurrence qu'avec une seule variable. On fait comme si p était connu, ce qui n'enlève rien à la validité du raisonnement.)

Pour n=1 : $F_{1+p} = F_p + F_{p-1}$
Pour n=2 : $F_{2+p} = 2F_p + 1F_{p-1}$
Donc la propriété est initialisée.
Supposons que, pour n fixé, $n \geq 2$ , on ait : $\mathcal{P}(n)$ et $\mathcal{P}(n-1)$ . Alors :

$F_{n+1+p} \, = \, F_{n+p} + F_{n+p-1}$
$\,\,\,\,\,\,\,\,\, = F_n \times F_p + F_{n-1} \times F_{p-1} \, + \, F_{n-1} \times F_p \, + \, F_{n-2} \times F_{p-1}$
$\,\,\,\,\,\,\,\,\, = F_p \times (F_n + F_{n-1}) \, + \, F_{p-1} \times (F_{n-1} \, + \, F_{n-2})$
$\,\,\,\,\,\,\,\,\, = \, F_p \times F_{n+1}) \, + \, F_{p-1} \times F_{n}$
Donc la propriété est héréditaire.
Par conséquent, on a bien démontré que :
$\forall (n,p) \in (\mathbb{N}^*)^2 \,\, F_{n+p} = F_n \times F_p \, + \, F_{n-1} \times F_{p-1}$

Démonstration du raisonnement par récurrence

Et voilà le moment tant attendu, nous allons (enfin) démontrer que ce raisonnement tient la route ! Pour cela on va démontrer que, si on démontre par récurrence la propriété suivante :
$\left.\begin{array}{lcl} P(0) \,\, et \,\, P(1)&&\\\forall n \in \mathbb{N}^* \,\, (P(n) \,\, et \,\, P(n-1) \Longrightarrow P(n+1))\\\end{array}\right\} \Longrightarrow \forall n \in \mathbb{N} \,\, P(n)$
Alors on a démontré que cette propriété était vraie. Et on va démontrer ça par l'absurde.
Are you ready ? So... go !

On suppose donc que P(0) est vraie et que, pour n fixé dans $\mathbb{N}$ , si P(n) est vraie, alors P(n+1) est vraie aussi.
Il s'agit de prouver que : $\forall n \in \mathbb{N} \,\, P(n)$ est vraie.
Considérons l'ensemble : $A=\{n \in \mathbb{N} \, / P(n) \, est \, vraie\}$ . Il s'agit donc de montrer que $A=\mathbb{N}$ .

Supposons $A \neq \mathbb{N}$ c'est à dire : $\overline{A} \neq \oslash$
Puisque $\overline{A} \neq \oslash$ et $\overline{A} \subset \mathbb{N}$ , $\overline{A}$ admet un plus petit élement b. (d'après l'axiome fondamental de l'ensemble des entiers naturels)
Puisque, par hypothèse, P(0) est vrai, alors $0 \in A$ donc $b \neq 0$ donc $a=b-1 \in \mathbb{N}$ .
Puisque b est le plus petit élément de $\overline{A}$ , $a=b-1 \in A$
Puisque $a \in A$ , P(a) est vraie, donc, la propriété étant héréditaire, P(a+1) est vraie aussi. Donc $a+1=b \in A$ Ce qui est impossible.
Donc l'hypothèse de départ : $A \neq \mathbb{N}$ est fausse. Par conséquent on a démontré que $A = \mathbb{N}$ .
Donc le raisonnement par récurrence est tout a fait juste, vérifié et certifié. bn_wink

Il existe des tonnes et des tonnes de manière d'utiliser le raisonnement par récurrence, selon ce qu'on veut démontrer. On peut utiliser des raisonnements croisés, ou bien des récurrences finies pour montrer que la propriété est vraie d'un entier à un autre, etc... Mais pour ne pas trop surcharger cet article, on évitera d'en parler ici bn_heureux

. Direction le Bar à Nougat pour toute question ou autre

Et voilà ! C'est finit ! mini_bn

J'espère que vous avez fait un bon voyage dans le monde des Mathématiques ^-^

Auteur : Bnmaster
Créé le : 08/12/2006
Modifié le : 31/07/2007
Vues : 2701 fois
Aucun commentaire

La Bnbox !

Menu

Mon compte

Recherche

Cahier de l'élève