La récurrence en quoi est-elle une preuve ?

[PIAB]

Bonjour/Bonsoir tout le monde !

D'abord je m’excuse si le titre n'est du topic n'est pas convenable.

Voilà je suis en Terminale Mathelem, nous avons fait le chapitre sur les Suites Numériques et bien sur la preuve par récurrence, et j'ai un problème avec ce dernier pas au niveau calculatoire (je sais comment résoudre des exos etc...). Mais au niveau du raisonnement lui même, je n'arrive pas a comprendre comment la récurrence prouve quelque soi.

Désoler pour mon français un peu chewiya


Merci d'avance.
-----

[Matt_error]

L'initialisation montre qu'on connait un terme qui vérifie la propriété voulue.
Ensuite, on arrive à montrer que si t'as un terme n (entier naturel quelconque !)***, alors forcément celui d'après (donc n+1) vérifie aussi la propriété.
Bien, rien de nouveau tu vas me dire.
Maintenant mets en lien l'initialisation et l'étape d'après. Le terme initial on va le noter n0 marche. Avec ce qu'on a prouvé, on sait que celui d'après (que je note n1) marche aussi. Donc n1 marche (=vérifie la propriété). Or si n1 marche, d'apres ce qu'on a montré, n2 marche aussi. Donc n3 marche aussi. Donc n4 aussi etc... Ca se propage de proche en proche.

Dismoi si c'est plus clair

EDIT: *** plus grand que celui de l'initialisation

[erik]

Salut,

Pour établir un raisonnement par récurrence on vérifie tout d'abord qu'une proposition (notons la P(n)) est vérifiée pour un certain n0 (généralement dans les exercices la proposition est vérifiée dès n0=0), ensuite on montre que si on suppose que P(n) est vérifiée pour un certain n alors la relation est encore vérifiée pour le n suivant (c'est à dire que P(n+1) est vérifiée).

donc : on sait que la relation est vérifiée pour n0, donc elle est vérifiée pour n0+1 (puisqu'on a montré que si on a P(n) alors on a P(n+1)), donc elle est vérifiée pour n0+2 (puisqu'on a montré que si on a P(n) alors on a P(n+1)), donc elle est vérifiée pour n0+3 (puisqu'on a montré que si on a P(n) alors on a P(n+1)), donc elle est vérifiée pour n0+3 (puisqu'on a montré que si on a P(n) alors on a P(n+1))....... donc elle est vérifiée pour tout n>=n0

EDIT Grillé par Matt_error

[gg0]

Bonjour.

En fait, la récurrence n'est que la façon de fabriquer les entiers. Tu a fait ça progressivement en maternelle et en primaire : on compte de 1 en 1 et on peut toujours continuer. On obtient tous les entiers ainsi (*).
Une autre façon de voir est de comprendre que quel que soit l'entier considéré en soustrayant 1 puis recommençant, on arrivera à 0.
mais surtout, il y a une preuve simple que la récurrence est efficace : Supposons que la propriété P est vraie pour 0 et que lorsqu'elle est vraie pour un entier, elle est vraie pour l'entier suivant. On considère l'ensemble E des entiers pour lesquels P est fausse. Si E n'est pas vide, comme les entiers sont totalement ordonnés, il y a un plus petit entier n appartenant à E, donc P est fausse pour n. mais pour n-1, P est vraie (n-1 n'est pas dans E puisque n est le plus petit). Comme p est vraie pour n-1, p est vraie pour l'entier suivant n. Ce qui contredit le fait que n est le plus petit. Cette preuve par l'absurde montre que E est vide, et que P est vraie pour tout entier.
En fait, j'ai remplacé la propriété qui fonde la preuve par récurrence par une autre, qui est équivalente : "tout ensemble non vide d'entiers naturels a un plus petit élément".

Si tu veux prolonger la réflexion, tu peux aller voir les axiomes de Peano pour les entiers (**), ou la construction des entiers dans la théorie des ensembles par exemple dans le cours de Patrick Dehornoy (nettement plus costaud).

Cordialement.

(*) Ou pas pour certains logiciens, mais ça dépasse de loin les besoins des matheux ordinaires.
(**) le cinquième est le fondement de la preuve par récurrence

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Si E n'est pas vide, comme les entiers sont totalement ordonnés, il y a un plus petit entier n appartenant à E, donc P est fausse pour n.

C'est parce que l'ordre sur |N est un bon ordre et pas seulement un ordre total, mais cela nécessite une démonstration n'utilisant pas la récurrence ...

Mais cela n'est pas utile au niveau lycée.

(*) Ou pas pour certains logiciens

Je confirme

[gg0]

Merci Médiat.

En fait, je n'ai même pas pensé à la notion d'ordre total, je donnais une idée "évidente" à quelqu'un qui ne connaît pas ce vocabulaire. J'aurais dû chercher un mot qui n'est pas mathématique. Je ne sais pas s'il y a un mot simple en français courant qui traduise la "droite des entiers".

Cordialement.

[Smooth56]

Salut !

Mon prof de maths nous a donné une image assez parlante de la récurrence :

Imagine une échelle.
Imagine que tu puisses monter sur le premier barreau de l'échelle. (c'est l'initialisation)
puis que, pour n'importe quel barreau de l'échelle, tu puisses accéder au barreau suivant. (c'est l'hérédité)

Alors tu peux accéder à tous les barreaux de l'échelle.

C'est juste histoire de comprendre le principe =)
Bonne journée

[PlaneteF]

Bonjour,

Imagine une échelle.

Une autre image, celles des dominos :

On dispose des dominos debouts les uns à côté des autres de telle sorte que la chute d'un domino entraine celle du domino à côté (c'est l'héridité), un domino numéro n tombé correspondant à la propriété vraie au rang n.

Maintenant pour faire tomber tous les dominos qui sont ainsi debouts (c'est-à-dire montrer la propriété pour tous rangs), il suffit de faire tomber le premier domino (c'est l'initilalisation) et tous les dominos tombent en cascade.