Le raisonnement par récurrence

a marqué ce sujet comme résolu.

Bonjour à tous,

J'ai commencé (il y a 1 semaine, 3 jours) la rédaction d'un tutoriel dont l'intitulé est Le raisonnement par récurrence.

J'aimerais obtenir un maximum de retour sur celui-ci, sur le fond ainsi que sur la forme, afin de proposer en validation un texte de qualité.

Si vous êtes intéressé, cliquez ci-dessous

Merci d'avance pour votre aide

+0 -0

Salut !

C'est pas mal ;)

J'apprécie beaucoup l'idée des contre-exemples, c'est une bonne manière de s'assurer que le principe est compris.

En voici 2 autres :

Montrer que $2^n < n!$ pour tout $n$ à partir d'un certain $n_0$. L'hérédité est valable dès $n = 3$ en revanche l'initialisation ne peut pas se faire avant $n = 4$.

Un autre exemple : http://www.les-mathematiques.net/phorum/read.php?2,171449,171456

Enfin, si le cœur t'en dis, tu peux rajouter un paragraphe sur le raisonnement par l'absurde et conclure avec la méthode en descente infinie.

Voilà. Sinon le contre-exemple que tu proposes est pas mal, mais à mon avis le formalisme, bien que léger, le rend pas évident à comprendre. Quelques explications seraient la bienvenue, y compris sur des choses "évidentes". Il ne faut pas oublier que ton article, en raison du sujet qu'il traite, intéressera essentiellement des lecteur de niveau Première S ou moins (la récurrence est étudiée dès la terminale), et pour ces derniers, l'absence d'explications peut rendre le formalisme compliqué.

Cela étant dit, l'article n'est pas mauvais.

EDIT: rectification du lien sur les crayons de couleur, qui était "cassé".

+0 -0

Je le trouve pertinent, mon professeur de terminale à l'époque avait utilisé la métaphore de l'échelle (capacité à monter au barreau suivant si on se trouve sur le précédent + être capable de monter sur le premier barreau) mais ça me semble moins intelligent que les dominos. L'idée est bonne.

J'ai également corrigé le lien du second exemple, qui interagissait mal avec le parser de ZdS.

EDIT : en effet Holosmos, je vies de m'en rendre compte à l'instant.

+0 -0

Salut !

C'est pas mal ;)

J'apprécie beaucoup l'idée des contre-exemples, c'est une bonne manière de s'assurer que le principe est compris.

En voici 2 autres :

Montrer que $2^n < n!$ pour tout $n$ à partir d'un certain $n_0$. L'hérédité est valable dès $n = 3$ en revanche l'initialisation ne peut pas se faire avant $n = 4$.

Un autre exemple : http://www.les-mathematiques.net/phorum/read.php?2,171449,171456

Merci du retour. Holosmos a eu la très bonne idée des contre-exemples.

Enfin, si le cœur t'en dis, tu peux rajouter un paragraphe sur le raisonnement par l'absurde et conclure avec la méthode en descente infinie.

On en avait discuté je crois.

Tout le monde poste pendant que j'écris. ^^

+0 -0

Pour plus de facilité, mes retours ne concernent pas l'orthographe.

Fin du XVIIIe siècle. La légende raconte

La légende est bien sûr jolie mais l'exactitude historique m'oblige à signaler que le raisonnement par récurrence était parfaitement maîtrisé au XVIIe siècle, notamment par Pascal, Fermat ou Bernoulli, et sans doute déjà connu chez les Arabes au XIe siècle. :)

Pour le suivre facilement, il vous faudra maîtriser les notions suivantes

Je maîtrise parfaitement le raisonnement par récurrence, et pourtant, j'ignore ce que vous entendez par « prédicat ». Peut-être qu'un terme plus usuel serait plus adapté à la présentation d'une notion de niveau lycée ?

Une infinité de dominos posés verticalement.

Je suppose que vous n'avez pas encore les images ? Chez moi, rien ne s'affiche.

En Mathématiques, l'ensemble des dominos représente un prédicat défini sur l'ensemble des entiers naturels N et la chute d'un domino particulier le fait que ce prédicat est vérifié au rang considéré. Le raisonnement par récurrence, basé sur le principe de récurrence, permet de démontrer un tel prédicat1.

Voilà exactement ce que je voulais dire. ^^ Après l'intro tout en douceur à base de dominos et tutti quanti, ce paragraphe est une bonne grosse baffe.

On veut démontrer Pn+1, i.e. :

Je trouve que cette ligne (et la formule qui va avec) est plus gênante qu'autre chose. Le raisonnement coulerait plus facilement en disant, en guise de transition vers « Sn+1=Sn+(n+1). », quelque chose comme « Avec ceci en tête, que vaut $S_{n+1}$ ? ». Ce qui éviterait de répéter « Or, par hypothèse de récurrence : [maths] », qui alourdit encore le cheminement.

pour tout n dans N∗, 1+⋯+n

Je ne vois pas trop l'utilité de répéter la formule, qui se trouve à peine une dizaine de lignes plus haut. D'autant que là, vous n'utilisez pas $S_n$, que vous vous êtes pourtant donnés la peine de définir dans une grosse boite info.

Soit Pn une propriété dépendant d'un entier n

Vous parliez de prédicat, maintenant de propriété. Ça change quelque chose ? Si oui, faut expliquer, si non, pourquoi changer de mot ? :)

Démonstration du principe

Toute cette section fait vraiment cheveu sur la soupe. :( Je m'explique.

  • La démonstration du raisonnement implique de bien maîtriser le raisonnement par l'absurde, ce que vous ne mettez pas dans les pré-requis et qui n'est pas nécessairement le cas chez un public dont le niveau est assez bas pour avoir besoin qu'on lui explique le raisonnement par récurrence.
  • L'idée même de démontrer formellement la validité d'une méthode de raisonnement me paraît d'un sacré niveau par rapport au thème abordé.
  • La propriété fondamentale n'est pas démontrée, donc finalement, vous remplacez une propriété non démontrée par une autre, ça ne sert pas à grand chose.

Sinon, le cours est pas mal, j'attends de le voir complet.

+5 -1

Une infinité de dominos posés verticalement.

Pour le début de l'explication : comment tu fais tomber un domino sans faire tomber les suivants ?
D'ailleurs j'ai l'impression que la partie "faire tomber les dominos un par un" est inutile dans l'analogie, non ?

En Mathématiques, l'ensemble des dominos représente un prédicat défini sur l'ensemble des entiers naturels N et la chute d'un domino particulier le fait que ce prédicat est vérifié au rang considéré. Le raisonnement par récurrence, basé sur le principe de récurrence, permet de démontrer un tel prédicat.

Je dirais que l'ensemble des dominos, c'est N. Mais j'arrive pas trop à voir du coup c'est quoi le prédicat: que tous les dominos peuvent tomber ? (ce qui est analogue à : une certaine propriété est vraie pour tout n)
L'hérédité, ce serait qu'un domino qui tombe fait tomber le suivant, et l'initialisation, c'est de voir que faire tomber le premier domino fait tomber le deuxième.
EDIT : après réflexion, l'initialisation, c'est de voir que le premier domino peut tomber (on vérifie le prédicat (et non l'hérédité) sur une valeur particulière).

Démonstration du principe

Moi je trouve intéressant de le mettre, mais peut-être à la fin, après les exemples et exercices, dans un extrait "Pour aller plus loin" parce qu'effectivement, c'est d'un niveau plus élevé que le reste. Ca permettrait de ne pas casser le rythme de lecture d'un lycéen, et de l'encourager à la fin à se poser des questions (parce qu'on ne pense pas forcément qu'une méthode de raisonnement, ça se démontre aussi)

+2 -0

À propos de

Toute cette section fait vraiment cheveu sur la soupe. :( Je m'explique.

et

Moi je trouve intéressant de le mettre, mais peut-être à la fin, après les exemples et exercices, dans un extrait "Pour aller plus loin" parce qu'effectivement, c'est d'un niveau plus élevé que le reste. Ca permettrait de ne pas casser le rythme de lecture d'un lycéen, et de l'encourager à la fin à se poser des questions (parce qu'on ne pense pas forcément qu'une méthode de raisonnement, ça se démontre aussi)

Je n'ai pas décidé de la location mais j'ai rédigé la démonstration. Je suis totalement d'accord avec ces remarques.

J'aimerai même aller plus loin en proposant une critique du principe de récurrence, en accentuant sur le fait que c'est la méthode de démonstration la plus naturelle mais aussi sur le fait que la démonstration est nulle puisqu'elle n'est qu'une reformulation du principe de récurrence.

+0 -0

Globalement, je trouve le tuto clair, propre, et simple.

Dans le détail, il y a trois trucs qui m'ont fait tiquer :

  • pour tout n dans N∗, P_n : « 1+2+⋯+n=n(n+1)2 ». (au début du chapitre Principe de récurrence). De mémoire, on apprend à lire ce genre de chose après avoir vu le raisonnement par récurrence. Si bien que seul les gens qui connaissent déjà la récurrence vont comprendre.
  • Si on parles de gens niveau lycée en maths, tu peux être sure qu'ils confondront « pour tout n dans N, P_n est vrai » et « P_n est vrai pour tout n dans N ». Pas mal risquent de raisonner en disant que si on suppose P_n vrai, alors on prend n=n+1, et donc la récurrence est vérifiée1. ^^ Or, je ne voit rien qui puisse prémunir ce genre d'idée.
  • Dans le contre-exemple, j'ai tiqué sur la notation « point central » pour la multiplication. Probablement parce que ça fait 4 points alignés, ou bien qu'on sait que la propriété n'a aucun sens. Quoiqu'il en soit, je me suis demandé si c'était bel et bien la multiplication, ou bien autre chose.

Voilà. Je n'ai rien vu d'autre.

  1. Je me souvient l'avoir faite moi-même celle-là. Mais je n'étais pas le seul. ↩

+0 -0

Je réponds rapidement :

La légende est bien sûr jolie mais l'exactitude historique m'oblige à signaler que le raisonnement par récurrence était parfaitement maîtrisé au XVIIe siècle, notamment par Pascal, Fermat ou Bernoulli, et sans doute déjà connu chez les Arabes au XIe siècle. :)

Bien cap'taine. Je le précise. Puis-je reprendre "était parfaitement maîtrisé au XVIIe siècle, notamment par Pascal, Fermat ou Bernoulli, et sans doute déjà connu chez les Arabes au XIe siècle" ?

Je maîtrise parfaitement le raisonnement par récurrence, et pourtant, j'ignore ce que vous entendez par « prédicat ». Peut-être qu'un terme plus usuel serait plus adapté à la présentation d'une notion de niveau lycée ?

Ouep, le terme « prédicat » n'est pas nécessaire et même nuisible. :)

Un prédicat est une proposition dépendant d'une variable (ici, un entier naturel). Par exemple, pour $n$ un entier naturel, $P_n :$ « $S_n = \frac{n(n+1)}{2}$ » est une proposition et $P$ est un prédicat (vérifié sur $\mathbb N$).

Je suppose que vous n'avez pas encore les images ? Chez moi, rien ne s'affiche.

Oui, ça prend du temps de photographier une infinité de dominos.1

Pour le début de l'explication : comment tu fais tomber un domino sans faire tomber les suivants ?

Tu les espaces suffisamment. Ca ira mieux avec une image.

D'ailleurs j'ai l'impression que la partie "faire tomber les dominos un par un" est inutile dans l'analogie, non ?

Ca illustre pourquoi on a introduit le principe de récurrence et qu'il n'est pas nécessaire, non ?

Je dirais que l'ensemble des dominos, c'est N. Mais j'arrive pas trop à voir du coup c'est quoi le prédicat: que tous les dominos peuvent tomber ?

Nop, le $n$ème domino est $P_n$ et sa chute le fait que le prédicat soit vérifié au rang $n$ ($P_n$ vrai). Donc oui, faire tomber tous les dominos revient à montrer que le prédicat est vérifié sur $\mathbb N$.

L'hérédité, ce serait qu'un domino qui tombe fait tomber le suivant, et l'initialisation, c'est de voir que faire tomber le premier domino fait tomber le deuxième.
EDIT : après réflexion, l'initialisation, c'est de voir que le premier domino peut tomber (on vérifie le prédicat (et non l'hérédité) sur une valeur particulière).

Oui.

  1. En fait, je voulais attendre de voir si l'analogie était judicieuse ou non avant de prendre des photos. ↩

+0 -0

Bien cap'taine. Je le précise. Puis-je reprendre "était parfaitement maîtrisé au XVIIe siècle, notamment par Pascal, Fermat ou Bernoulli, et sans doute déjà connu chez les Arabes au XIe siècle" ?

Tout à fait. Contre le paiement de la modique somme de 999€ par an au titre du droit d'auteur et l'acceptation inconditionnelle et irréfragable de la licence d'utilisation « Pacte avec le Diable ». :P

Ca illustre pourquoi on a introduit le principe de récurrence et qu'il n'est pas nécessaire, non ?

Oui, même si ce n'est pas forcément très explicite. J'ai moi aussi un peu achoppé sur ce passage-là. Il faudrait peut-être expliquer plus explicitement que vous voulez montrer que le raisonnement par récurrence est suffisant mais pas forcément nécessaire, et donc déplacer l'analogie à ce moment-là de l'explication. :)

+0 -0

Tout à fait. Contre le paiement de la modique somme de 999€ par an au titre du droit d'auteur et l'acceptation inconditionnelle et irréfragable de la licence d'utilisation « Pacte avec le Diable ». :P

'Trouve pas la licence. Serait-ce une escroquerie ?

Oui, même si ce n'est pas forcément très explicite. J'ai moi aussi un peu achoppé sur ce passage-là. Il faudrait peut-être expliquer plus explicitement que vous voulez montrer que le raisonnement par récurrence est suffisant mais pas forcément nécessaire, et donc déplacer l'analogie à ce moment-là de l'explication. :)

Du coup, j'enlèverais tout jusqu'à "Je redresse alors ceux que vous avez couchés et vous demande de tous les renverser." et changerais "En effet, vous avez commencé par les pousser un par un, puis, au moment où cette méthode devenait laborieuse, vous avez opté pour la chute en cascade." en un truc du genre "En effet, vous auriez pu les faire tous tomber un par un, mais c'est bien plus laborieux qu'une chute en cascade, surtout s'il y a une infinité de dominos." ?

Ce que je propose, c'est d'essayer d'ajouter les images rapidement puis de voir si ça manque encore de clarté. :)

+0 -0
  • Si on parles de gens niveau lycée en maths, tu peux être sure qu'ils confondront « pour tout n dans N, P_n est vrai » et « P_n est vrai pour tout n dans N ». Pas mal risquent de raisonner en disant que si on suppose P_n vrai, alors on prend n=n+1, et donc la récurrence est vérifiée[^perso]. ^^ Or, je ne voit rien qui puisse prémunir ce genre d'idée.

Gabbro

Il n’y a aucune différence entre ces deux propositions :

  • $\forall n\in N, P_n$
  • $P_n,~ \forall n \in N$
+0 -0

Mise à jour de l'introduction et du premier extrait. J'ai commencé par considérer les dominos mélangés afin que le lecteur comprenne qu'une récurrence n'a lieu d'être que lorsqu'on a un ordre.

Pensez-vous qu'il soit judicieux de donner des exemples de récurrences sur des arbres binaires par exemple ?

L'objectif étant de montrer qu'on peut se ramener à une récurrence quand on n'a pas explicitement les $P_n$.

+0 -0

J'ai revu le second extrait pour aborder l'aspect mathématique plus en douceur mais j'ai un problème de vocabulaire. En effet, j'ignore quel terme employer pour désigner ce sur quoi on travaille (ce qu'on appelle prédicat dans la bêta actuelle). Propriété ? Résultat ? Proposition ?

+0 -0

Le souci c'est que ça fait introduire des termes techniques non nécessaires à la compréhension du principe de récurrence. Ce tutoriel est majoritairement destiné à des lycéens, la plupart desquels se contrefichent du vocabulaire technique.

Je pense donc opter pour le terme « résultat », « propriété » donnant l'impression d'être attaché à un objet particulier.

+0 -0
Ce sujet est verrouillé.