Discussion :

[hiko-seijuro]

Bonjour

est ce que quelqu'un pourrait m'expliquer comment faire une démonstration par induction et la différence de celle ci avec une démonstration par récurrence

merci bcp

[FrancisSourd]

Pour moi, c'est le mot à mot du terme anglais "proof by induction" et cela veut dire preuve par récurrence.
J'ai également entendu dire qu'une preuve par induction désignait une récurrence non/peu formelle (on donne l'idée pour passer de n à n+1 et "par induction" cela marche pour tout n)

[Matthieu Brucher]

La version américaine de la récurrence, quoi : il évident que P(0) et il est évident que P(n)=>P(n+1)

[hiko-seijuro]

oki merci bcp

[DrTopos]

'Preuve par induction' est (me semble-t-il) une notion plus générale que 'preuve par récurrence'. En général on réserve le terme 'preuve par récurrence' pour les inductions sur le type des entiers, alors qu'on fait des preuves par induction sur des structures arborescentes. Par exemple, pour prouver une propriété d'un compilateur, on peut faire une preuve par induction sur la struture des termes (expressions) du langage, qu'il est difficile d'appeler une preuve par récurrence. Le principe reste le même mais la structure du type récursif (inductif) des entiers reste un cas très particulier.

[Médiat]

Pour confirmer et donner un exemple de ce que vient de dire DrTopos, on utilise aussi le mot induction pour des raisonnements mettant en cause des ordinaux > oméga, dans lesquels il faut faire des démonstrations pour les ordinaux limites (mais on dira aussi dans ce cas "récurrence transfinie").

[DrTopos]

Tout à fait, j'avais oublié récurrence transfinie, que j'ai étudiée il y a bien longtemps dans Bourbaki.

D'ailleurs, il y a trois mots qui entrent en conflit: récurrence, induction et récursion. Je ne crois pas qu'il y ait lieu de faire tellement de distinction entre induction et récursion.

Pour ceux que ça intéresse, j'en profite pour signaler que j'ai écrit un petit papier sur les relations entre récursion simple, récursion primitive et principe du raisonnement par récurrence, qui j'espère, est lisible par tous. Il se trouve ici.

[hiko-seijuro]

merci pour le paier et vos réponses

j'ai l'impression d'tre un peu idiot lol