Salut ,
Quand on fait un raisonnement par récurrence, en général, l'initialisation est assez simple (pour ne pas dire simpliste).
Je cherche un exemple de démonstration par récurrence où au contraire, l'hérédité est beaucoup plus facile que l'initialisation. Et donc, où on sue pour initialiser la propriété.
Il me semblait en avoir croisé une il y a quelques années mais je n'arrive pas à la retrouver d'ou ma demande
C'est peu être facile, mais ça ne me saute pas aux yeux
Merci
salut
l'initialisation est toujours simple quand on donne le rang de départ ...
tu connais les exo classiques : montrer que à partir du rang ... (qui est toujours donné au lycée)
mais si je te pose le pb sous la forme : pour quels entiers n a-t-on ? comment fais-tu ?
PS : l'exemple est ici trivial et archi-classique mais c'est pour te donner une idée du pb : en gros : on "sait" (ou on démontre que) que la propriété est héréditaire ... mais à partir de quand ??
salut
l'initialisation est toujours simple quand on donne le rang de départ ...
tu connais les exo classiques : montrer que à partir du rang ... (qui est toujours donné au lycée)
mais si je te pose le pb sous la forme : pour quels entiers n a-t-on ? comment fais-tu ?
PS : l'exemple est ici trivial et archi-classique mais c'est pour te donner une idée du pb : en gros : on "sait" (ou on démontre que) que la propriété est héréditaire ... mais à partir de quand ??
ainsi par exemple et si je te mets ou n'importe quel exposant ...
on sait qu'une exponentielle l'emporte sur la puissance à l'infini ... mais à partir de quand est-ce vrai ?
d'ailleurs le raisonnement par récurrence fera intervenir des conditions fort probablement suffisantes (dès que l'exposant n'est plus 2 ou 3) et ne donnera peut-être pas le rang minimal mais un rang à partir duquel la propriété est héréditaire ...
et pour trouver le rang minimal ... ben bonjour !!! ou alors utiliser un algo pour traiter tous les cas (en nombre fini) restants ...
Bonjour
pas besoin d'une récurrence pour voir que 10^n+1 est congru à 2 modulo 9, quelque soit n, si ?
Bonjour lafol
je voulais juste taquiner carpediem, mon message est hors sujet, car il parlait du passage d'une CS à une CNS pour l'hérédité
lafol : certes mais c'est une question didactique et pédagogique fondamentale (pour qui veut réellement éduquer et instruire et non pas faire réciter des math en donnant l'illusion de la réussite) sur le problème de la vérité d'une affirmation
la plupart des élèves (et bon nombre d'adultes) pensent que la proposition si deux est supérieur à trois alors les chats sont verts est fausse (l'implication est vraie)
et si on considère les propositions et
il est intéressant de comprendre que ces deux propriétés sont héréditaires : les implications P(n) => P(n + 1) et Q(n) => Q(n + 1) sont vraie
pourtant 'une des propriétés est fausses pour tout n et l'autre est vraie pour tout n ...
et pour poursuivre avec mousse42 : il n'y a pas de pb puisque la propriété est héréditaire pour tout n ... or P(0) est faux ... donc c'est terminé !!!
et pas besoin d'algo !!! qui ne sera nécessaire que lorsqu'on montre qu'une propriété est héréditaire à partir d'un certain rang ... mais qui peut-être vraie avant ce rang sans que la récurrence puisse le montrer ou parce qu'on a travaillé par condition suffisante ...
c'est plutôt le pb "à l'envers" qui ... pose pb : c'est quand on démontre qu'une propriété est héréditaire à partir d'un rang n mais qu'elle est vraie qu'à partir d'un rang m > n
et là pour trouver ce rang m ben ça peut être problématique ...
visualisation (avec n = 10 pour simplifier)
P(0) => P(1) => P(2) => .... => P(9) => P(10) => P(11) => .... => P(
=> P(
=> ...
Salut à tous,
Merci beaucoup pour vos réponses!
Salut
Pour l'exemple de
L'hérédité est vraie à partir de mais pour l'initialisation il faut attendre
,
ha oui Taylor est aussi un classique du genre : l'initialisation est pénible ... mais ensuite ça roule tout seul par IPP ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :