Partage

[Bêta ON] Le principe de récurrence

Dans la catégorie "Mathématiques" par Janeo

Le 5 novembre 2011 à 16:08:02

Lire le tutoriel
Tuto ouvert aux bêta-tests
Réservé aux membres

Publicité
Le 5 novembre 2011 à 16:08:02
Le 5 novembre 2011 à 16:08:02

Tuto terminé. En attente de validation, vos avis sont les bienvenus.
Le 5 novembre 2011 à 19:56:36

Rien de faux après un rapide survol. Par contre :
* contenant : très scolaire : tu t'attaches énormément à la rédaction. Hors les maths, ce n'est pas une histoire de rédaction ; pour "bien rédiger", il suffit d'énoncer les hypothèses, toutes les hypothèses et rien que les hypothèses des théorèmes qu'on utilise, (si on veut bien faire les choses) citer ledit théorème, et enfin donner la conclusion. Point. Et si on comprend parfaitement la logique qui est dans son raisonnement, on ne peut pas rédiger autrement que correctement. En terme plus savant : pour écrire une preuve, si la sémantique est comprise, la syntaxe vient naturellement et non l'inverse.


* contenu : tu ne donnes des exemples que de l'application de la récurrence à des suites suites numériques ; les exemples dans d'autres situations ne manquent pas, comme tu l'as signalé : preuve d'algorithmes, graphes, algèbre linéaire ( récurrence sur les dimensions d'espaces vectoriels),... c'est un peu triste de ne pas en donner des exemples. Et ce serait beaucoup plus intéressant de s'attarder là dessus plutôt que sur des questions de rédactions ou de s'éterniser une partie entière sur l'initialisation de la récurrence à partir d'autre chose que de 0 (pourquoi ne pas le faire dès le début ? Au final, ça ne change rien et c'est tout aussi intuitif). Tu aurais mieux fait de donner un exemple d'utilisation de la récurrence forte qui apporte une vraie subtilité supplémentaire dans le raisonnement (par exemple tout entier admet une décomposition en facteur premier : c'est simple et n'utilise que la définition d'un nombre premier et la récurrence forte)

De même, si tu veux poursuivre ton tuto, les directions que tu proposes ne me semblent pas judicieuses :
*récurrence sur Z : moue bon... on fait une récurrence pour P(n) et une autre pour P(-n)... De quoi y passer une partie ?
* récurrence sur N²: qu'est ce que c'est que ça ? Je vois mal comment on peut avoir des raisonnement compréhensibles en montrant les choses par récurrence sur cet ensemble... quel est ton principe de "récurrence sur IN²" ?
* Plutôt que des exercices sans but, pourquoi ne pas essayer de nous expliquer des trucs marrants faisant appel à la récurrence ? Par exemple : les tours de Hanoi.

Dernier point : ta "démonstration du principe" est à la limite de la malhonnêteté : dans quelle théorie exactement te places tu ? Quel axiomes prends tu ? Suivant la théorie que tu choisis, c'est un axiome de la théorie des entiers... Sorti de son contexte, la démonstration que tu donnes n'a donc pas beaucoup de sens.
Le 5 novembre 2011 à 20:37:49

Citation

contenant : très scolaire : tu t'attaches énormément à la rédaction. Hors les maths, ce n'est pas une histoire de rédaction ; pour "bien rédiger", il suffit d'énoncer les hypothèses, toutes les hypothèses et rien que les hypothèses des théorèmes qu'on utilise, (si on veut bien faire les choses) citer ledit théorème, et enfin donner la conclusion. Point. Et si on comprend parfaitement la logique qui est dans son raisonnement, on ne peut pas rédiger autrement que correctement. En terme plus savant : pour écrire une preuve, si la sémantique est comprise, la syntaxe vient naturellement et non l'inverse.



Dire que scolaire = rédaction me semble faux. Les chercheurs en math doivent aussi rédiger avec précision pour être compris par la communauté scientifique.

Ensuite, oui il y a une orientation scolaire puisque ce tutoriel s'adresse notamment aux terminales.

Je suis en total désaccord avec l'affirmation "si on comprend parfaitement la logique qui est dans son raisonnement, on ne peut pas rédiger autrement que correctement.". Je pratique du soutien scolaire au lycée et nombre des élèves que j'aide me prouvent le contraire. Ils comprennent très bien la logique mais ont du mal à l'exprimer avec rigueur. Ensuite, la rédaction c'est aussi une histoire de communication. Une récurrence qui commence par l'hérédité et finit par l'initialisation est juste aussi, car comme tu le dis "toutes les hypothèses sont énoncées", mais ne respecte pas la logique du principe.

Citation

s'éterniser une partie entière sur l'initialisation de la récurrence à partir d'autre chose que de 0 (pourquoi ne pas le faire dès le début ? Au final, ça ne change rien et c'est tout aussi intuitif



En effet ce point se discute. Au départ, j'avais présenté le principe à un rang quelconque. Mais je me suis dis que sur le site du zéro, il fallait aller plus doucement. Peut-être que ça te semble trivial, mais pour d'autres ça peut sembler plus facile de commencer au rang 0.

Citation

Tu aurais mieux fait de donner un exemple d'utilisation de la récurrence forte qui apporte une vraie subtilité supplémentaire dans le raisonnement (par exemple tout entier admet une décomposition en facteur premier : c'est simple et n'utilise que la définition d'un nombre premier et la récurrence forte)



L'exemple que tu cites est dans mon tuto :p

Citation

*récurrence sur Z : moue bon... on fait une récurrence pour P(n) et une autre pour P(-n)... De quoi y passer une partie ?



Peut-être pas, mais c'est utile de le mentionner et de donner un exemple, non ?

Citation

* récurrence sur N²: qu'est ce que c'est que ça ? Je vois mal comment on peut avoir des raisonnement compréhensibles en montrant les choses par récurrence sur cet ensemble... quel est ton principe de "récurrence sur IN²" ?



Puisque tu ne sais pas ce que c'est, ça peut être intéressant de le présenter non ?

Citation

Dernier point : ta "démonstration du principe" est à la limite de la malhonnêteté : dans quelle théorie exactement te places tu ? Quel axiomes prends tu ? Suivant la théorie que tu choisis, c'est un axiome de la théorie des entiers... Sorti de son contexte, la démonstration que tu donnes n'a donc pas beaucoup de sens.



Je n'utilise qu'un axiome de N que je cite avant ma preuve... C'est moi ou tu n'as lu le tuto qu'à moitié ?

En conclusion, certaines remarques sont intéressantes même si tu as sauté certains passage de mon tuto à la lecture. Dans les exercices que je vais proposer, il y aura exemples assez variés comme ceux que tu cites.
Le 5 novembre 2011 à 21:24:54

Contrairement à ce que tu dis, ce tutoriel est scolaire. Et je dois te prévenir : les validateurs n'aiment pas ce genre de tutoriel.

Le siteduzéro science est un site de vulgarisation scientifique, pas un site du soutien scolaire. C'est le genre de site sur lequel on doit expliquer des concepts, faire comprendre des notions et pas montrer des méthodes de rédaction qui ne servent qu'à l'école ou dans certains métiers. Parler de rédaction ne nous apprend rien : cela sert uniquement à l'école, et éventuellement à quelques mathématiciens qui savent déjà rédiger (sauf qu'il rédigent surement d'une façon très différente et doivent le faire en anglais, pas en français). Si tu veux que ton tutoriel soit accepté, tu devrais vraiment supprimer tout ce qui a rapport à la rédaction.

EDIT : oui, c'était une faute de frappe. :p
Le 5 novembre 2011 à 22:11:45

Citation : Mewtow

Contrairement à ce que tu dis, ce tutoriel est scolaire.



Citation : Janeo

oui il y a une orientation scolaire puisque ce tutoriel s'adresse notamment aux terminales.

:-°

Citation : Mewtow

Ce n'est pas le genre de site sur lequel on doit expliquer des concepts, faire comprendre des notions



Faute de frappe ?

Citation : Mewtow

Parler de rédaction ne nous apprend rien : cela sert uniquement à l'école, et éventuellement à quelques mathématiciens qui savent déjà rédiger



Réduire la rédaction à un formalisme pur est réducteur. Rédiger, c'est être rigoureux logiquement, exprimer ses idées clairement et de façon concise. La rédaction c'est tout simplement une des composantes fondamentales des mathématiques. Car faire des maths c'est notamment démontrer des propositions, et pour les démontrer il faut les rédiger. Tous les sites qui parlent de math présentent des démos rédigées. Rien à voir avec l'école.

Alors maintenant si les validateurs n'acceptent pas que je présente une rédaction, ainsi soit-il. Je suppose que je dois supprimer les deux rédactions types que je présente ?
Le 5 novembre 2011 à 22:18:30

Citation : Janeo

Je suppose que je dois supprimer les deux rédactions types que je présente ?



Oui, je pense que ce serait une bonne idée de les enlever.
Le 5 novembre 2011 à 22:33:36

Et au contraire, ta première partie "Idées" devrait être clairement étoffé et amélioré. La différence avec son cours ou son livre de maths doit se faire dans ces moments là. Prends le temps de mieux vulgariser, de faire un vrai schéma, de raconter une histoire,... L'idée de l'échelle est pas mal mais il faut aller plus loin.
Le 5 novembre 2011 à 23:12:42

Citation : Janeo


Citation

Tu aurais mieux fait de donner un exemple d'utilisation de la récurrence forte qui apporte une vraie subtilité supplémentaire dans le raisonnement (par exemple tout entier admet une décomposition en facteur premier : c'est simple et n'utilise que la définition d'un nombre premier et la récurrence forte)



L'exemple que tu cites est dans mon tuto :p


Au temps pour moi, j'avais vu le passage, mais vu que c'était présenté dans la même présentation que les différents énoncés du principe de récurrence, je n'ai pas lu. Ce qui implique une remarque de forme : il serait bon d'avoir une présentation différente pour les exemples et les propriétés ; mais vu le zCode, ce n'est pas forcément facile de faire ça bien...

Citation


Citation

*récurrence sur Z : moue bon... on fait une récurrence pour P(n) et une autre pour P(-n)... De quoi y passer une partie ?



Peut-être pas, mais c'est utile de le mentionner et de donner un exemple, non ?


En exemple ok, mais vu que c'est la première chose dont tu parles dans "la suite du tuto", ça fait bizarre : on a l'impression que c'est un truc super fendard qui a des applications énormes ! Alors que ... ben non :D

Citation

Citation

* récurrence sur N²: qu'est ce que c'est que ça ? Je vois mal comment on peut avoir des raisonnement compréhensibles en montrant les choses par récurrence sur cet ensemble... quel est ton principe de "récurrence sur IN²" ?



Puisque tu ne sais pas ce que c'est, ça peut être intéressant de le présenter non ?

On a le droit à un petit spoiler quand même ? Je suis intrigué là ... Tu peux me donner au moins l'énoncé du principe ?

Citation

Citation

Dernier point : ta "démonstration du principe" est à la limite de la malhonnêteté : dans quelle théorie exactement te places tu ? Quel axiomes prends tu ? Suivant la théorie que tu choisis, c'est un axiome de la théorie des entiers... Sorti de son contexte, la démonstration que tu donnes n'a donc pas beaucoup de sens.



Je n'utilise qu'un axiome de N que je cite avant ma preuve... C'est moi ou tu n'as lu le tuto qu'à moitié ?


J'ai bien vu que tu utilises un axiome, mais pour définir IN, il te faut un peu plus qu'un axiome. D'ailleurs tu as implicitement utilisé d'autres axiomes : quand tu utilises "n+1", tu utilises l'axiome disant que chaque élément a un successeur. Certaines définitions de IN inclues le principe de récurrence,d'autres non. Et donc si tu l'inclues(c'est ce que je fais tous les jours, et je m'en porte très bien), la démonstration ne sert ... à rien ! C'est pour ça que pour être complet, il faudrait que donnes tous les axiomes que tu utilises. Mais là ça devient lourd. Faire ce genre de démonstration est toujours très périlleux car on est en train de formaliser des notions qui sont très intuitives ; on a vite fait d'utiliser un axiome sans s'en rendre compte :p .

Citation

En conclusion, certaines remarques sont intéressantes même si tu as sauté certains passage de mon tuto à la lecture. Dans les exercices que je vais proposer, il y aura exemples assez variés comme ceux que tu cites.


Oui j'ai lu vite pour lire les points sensibles, je m'excuse encore platement de l'erreur ... Pourquoi ne mets tu pas dans "la suite du tuto" les "exemples assez variés comme ceux que [je] cite" ? Ce serait bien plus instructif et attrayant que de la récurrence sur Z ;)

Quant à la rédaction, je persiste et je signe : si tu penses que tes élèves ont tout compris, demande leur de faire le raisonnement à l'oral, de donner toutes les hypothèses, énoncer le théorème et pitatipatata. Après, ce qu'ils ont dit à l'oral, ils n'ont plus qu'à l'écrire. S'ils ne sont pas capables de faire le raisonnement à l'oral, c'est qu'ils n'ont pas _vraiment_ compris ; ils ont compris _en gros_... mais fait des maths, pas du _en gros_.

De là à retirer complètement toutes les parties "sur la rédaction", je pense que c'est excessif. Par contre, tu peux le présenter différemment, en expliquant non pas la syntaxe, mais la sémantique : <<au début, il serait bien de savoir ce qu'on va démontrer : c'est ce qu'on appelle "l'hypothèse de récurrence". Ensuite, on va montrer qu'on sait monter sur la 1ere marche, c'est "l'initialisation", puis que si on est sur une marche, on peut atteindre la marche suivante, c'est "l'hérédité". Et si on a réussi à montrer tout ça, on a terminé, on peut conclure que l'hypothèse est vraie pour tout n. Pour faire une "preuve par récurrence, j'utiliserai toujours ce schéma dans mon tuto>>.
Après pour la suite, tu lorsque tu fais tes démonstrations, tu appliques strictement ce schéma. Par contre, remarque de mise en forme : la présentation est assez lourde : pour le premier raisonnement, ça se justifie bien, après pour le reste, on peut p-ê se contenter d'un "gras soulginé" ou qcch d'équivalent nan ?

Et pour finir, en me relisant, je me rends compte que j'ai été un peu sec dans mon premier message, je m'en excuse :p .

@Mewtow : je pense que les "mathématiciens" n'ont pas besoin du site du zéro pour apprendre à rédiger... Et ces "mathématiciens" ont aussi très bien le droit de rédiger en français, ougandais ou gautemalteque si ça leur chante ! :p (bon après, j'avoue ne pas lire couramment le guatemalteque...)
Le 6 novembre 2011 à 1:08:21

Suite à vos remarques judicieuses, j'ai fait des mises à jour :

- Suppression des exemples de rédaction type, remplacés par une explication de la sémantique proposée par sebsheep.

- Ajout d'une analogie avec les dominos

- Ajout de deux schémas d'échelles, suite à la remarque de Lanfeust.

- Allègement de la présentation des récurrences

- Ajout du problème des tours d'Hanoï.

Citation : sebsheep

On a le droit à un petit spoiler quand même ? Je suis intrigué là ... Tu peux me donner au moins l'énoncé du principe ?



Ça ressemble un peu à la récursivité utilisant l'ordre lexicographique. L'idée générale est : si je sais me déplacer en haut et à droite sur une grille, je sais me déplacer dans le cadran Nord-Est représentant N². Bien sûr la rédaction utilisant ce principe est assez lourde, mais il reste amusant :D

Citation

J'ai bien vu que tu utilises un axiome, mais pour définir IN, il te faut un peu plus qu'un axiome. D'ailleurs tu as implicitement utilisé d'autres axiomes : quand tu utilises "n+1", tu utilises l'axiome disant que chaque élément a un successeur. Certaines définitions de IN inclues le principe de récurrence,d'autres non. Et donc si tu l'inclues(c'est ce que je fais tous les jours, et je m'en porte très bien), la démonstration ne sert ... à rien ! C'est pour ça que pour être complet, il faudrait que donnes tous les axiomes que tu utilises. Mais là ça devient lourd. Faire ce genre de démonstration est toujours très périlleux car on est en train de formaliser des notions qui sont très intuitives ; on a vite fait d'utiliser un axiome sans s'en rendre compte :p .



En fait j'utilise une construction de N basée sur 3 axiomes, et l'existence du successeur se démontre avec l'axiome 1 et 3. Mais je trouvais ça un peu lourd de présenter les 3 axiomes alors que la démonstration n'en utilise qu'un. Elle reste amusante et intéressante même si on ne connaît pas tous les axiomes.

Voilà, merci pour vos remarques et bonne soirée :)
Le 12 novembre 2011 à 16:02:02

Une idée comme ça : tu pourrais montrer (ou dire) que les principes de récurrence que tu cites (récurrence simple, double, forte) sont équivalents.
Le 20 novembre 2011 à 14:02:44

En effet c'est une bonne idée. Mais avant de faire des rajouts je pense que je vais attendre le verdict de l'équipe de validation sur l'état actuel du tuto.
anonyme
avatar
Le 23 novembre 2011 à 23:12:08

Citation : Tutoriel

Soit une propriété qui dépend de n.

Si P(0) est vraie,
et si pour tout entier naturel n, P(n) implique P(n+1),

alors pour tout entier naturel, P(n) est vraie.


Petit point précis : le point que j'ai mis en gras est à corriger par « s'il existe un entier naturel n tel que », sans quoi le théorème de récurrence n'a pas de sens.

J'aime bien l'introduction avec l'exemple de l'échelle, que je trouve particulièrement adapté. Pour le reste, je rejoins un peu les autres : c'est un peu terre-à-terre et c'est dommage.

As-tu envisagé de profiter de ton tutoriel pour prouver des résultats divertissants sur les entiers (des divisibilités, par exemple). Enfin, il pourrait être également amusant de montrer des fausses preuves par récurrence afin de permettre au lecteur de vérifier s'il a bien compris toute la subtilité de la récurrence (je pense notamment à la fameuse preuve que tous les crayons d'une trousse sont d'une même couleur dès lors que deux d'entre eux sont de la même couleur).

Ajout — Concernant la présentation du tutoriel, le choix de souligner systématiquement « Initialisation », « Hérédité » et « Conclusion » m'attriste un peu. Mettre les étapes en valeur est une bonne idée, mais privilégie le texte mis en gras ou en italique, plus élégant et respectueux des conventions typographiques en usage. Par ailleurs, pour les équations écrites en TeX, essaie d'aligner les unes sous les autres les différentes étapes d'un calcul (en général, tes calculs se commencent sur une ligne et commencent au début de la ligne suivante ; il serait mieux d'aligner les symboles « = » les uns sous les autres) et d'utiliser les symboles proposés par TeX (×, ≤ et ≥ notamment, j'en ai peut-être oublié). Si tu as besoin d'appui pour rédiger tes formules, tu peux lire http://fr.wikipedia.org/wiki/Aide:Formules_TeX et http://www.siteduzero.com/tutoriel-3-2 [...] ise-math.html.
Le 24 novembre 2011 à 11:38:43

Citation : sk

Petit point précis : le point que j'ai mis en gras est à corriger par « s'il existe un entier naturel n tel que », sans quoi le théorème de récurrence n'a pas de sens.



Non, il ne suffit pas que l'implication P(n) => P(n+1) soit vraie pour un seul entier naturel. Comment tu passerais d'un échelon à un autre dans ce cas ?

Citation : sk

As-tu envisagé de profiter de ton tutoriel pour prouver des résultats divertissants sur les entiers (des divisibilités, par exemple)



J'utilise la récurrence forte pour un résultat de divisibilité. Si tu as un exemple vraiment fun en tête je veux bien le rajouter.

Je mettrais peut-être l'exemple de la trousse.

Citation : sk

le choix de souligner systématiquement « Initialisation », « Hérédité » et « Conclusion » m'attriste un peu.



Mettre en gras n'est pas une option car le LateX est gras. Mettre en italique ne sera pas assez visible et clair. Si tu as une autre idée je veux bien.

Merci pour les commentaires.
anonyme
avatar
Le 24 novembre 2011 à 11:53:48

Citation : Janeo

Citation : sk

Petit point précis : le point que j'ai mis en gras est à corriger par « s'il existe un entier naturel n tel que », sans quoi le théorème de récurrence n'a pas de sens.



Non, il ne suffit pas que l'implication P(n) => P(n+1) soit vraie pour un seul entier naturel. Comment tu passerais d'un échelon à un autre dans ce cas ?


Hum, en effet, je me suis planté. Toutes mes excuses. :)
Le 17 décembre 2011 à 21:13:25

Bonjour.
Je trouve le tuto très propre, on s'est fixé un but, on l'atteint.
La seule chose qui m'a dérangé est le mot "axiome", je constate d'ailleurs qu'on a bien débattu sur le sujet. M'est avis que tu devrais simplement dire quelque chose du genre "Je démontre le principe en admettant la propriété de N suivante qui découle de sa construction, et qui sort du cadre de ce tuto".
J'aime le passage par les tours de Hanoi, qui montre une "vraie" application de la puissance de la récursivité.
Peut-être devrais tu aussi parler des récurrences doubles et fortes (on suppose la propriété vraie pour n et n+1 (respectivement, pour tout k<=n), et on la montre pour n+2 (respectivement, pour n+1))
Bonne continuation.
Le 18 décembre 2011 à 11:39:52

J'ai rajouté une phrase qui précise que le principe de récurrence est admis dans certaines constructions de N. Je pense que le mot axiome peut rester, c'est le synonyme de propriété admise, surtout qu'ici l'axiome énoncé est très connu.

Pour les récurrences doubles et fortes, j'ai déjà écris une partie dessus intitulée "les récurrences d'ordre supérieur".

Merci pour ton commentaire :)
Le 18 décembre 2011 à 12:03:45

Y a pas d'histoires d' "énoncé très connu" -on pourrait très bien dire que le principe de récurrence est "très connu" et l'admettre dans ce cas. Je me répète, pour être complet et rigoureux, il faut que expliques quelle est TA construction de IN, autrement dit que tu donnes un système complet d'axiomes qui permette de faire tout ce qu'on fait "d'habitude" avec les entiers ; sinon cette démo n'a aucun sens vu qu'on ne sait pas ce qu'on manipule.

Commentaire sur les tours de Hanoi : sujet très sympa effectivement, mais il y a une petite subtilité dans l'hypothèse de récurrence, il faut être un brin plus précis, et préciser que l'on conserve bien les conditions de départ (un piquet vide, l'autre rempli jusqu'au rang k, un truc dans le genre). Ca devient assez lourd, alors peut-être tu peux conserver ton hypothèse qui est "naturelle" et après expliquer qu'en fait l'hypothèse qu'on doit faire est beaucoup plus forte si on veut être rigoureux.

[Bêta ON] Le principe de récurrence

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur
  • Markdown