Principe du raisonnement par récurrence

[Rebelle_]

Coucou à toutes (je sais, je rêve) et à tous ! =D

Bon, je suis partie pour ma question journalière... :P
Aujourd'hui, ce sera à propos du raisonnement par récurrence. J'en ai bien compris le principe, c'est plutôt très logique. On définit une propriété dont on veut vérifier qu'elle est vraie pour tout entier naturel n. On commence par vérifier sa véracité au premier terme (n_0) puis on se dit que si le fait qu'elle soit vraie pour un rang n implique qu'elle le soit aussi pour un rang n+1, alors la propriété est vraie quel que soit n. Jusque là ça va. ^^'

J'ai étudié quelques exemples. Le seul truc un peu embêtant c'est la rédaction, mais bon ça va aller aussi.

Dans mon cours, il est écrit que "Si P(n) est vraie pour la première valeur de n et si P(n) vraie implique P(n+1) vraie, alors P(n) est vraie pour tout n".
Je me demandais alors si le terme "implique" au milieu de la phrase ne pouvait pas se transformer en "équivaut à". Parce que si l'hypothèse de réucurrence est vraie et dit "P(n) implique P(n+1)", alors on a aussi "P(n+1) implique P(n)" non ? C'est-à-dire que ça marche aussi dans l'autre sens. Si c'est le cas, alors on peu parler d'équivalence non ? :/
Et si ce n'est pas le cas, quels sont les contre-exemples qui existent ?
C'est juste une question de vocabulaire, mais les équivalences sont plus puissantes que les implications... Enfin je crois !


Autre petit soucis : est-il possible d'avoir une propriété vraie en P(n_0) (qui passe donc l'initialisation) mais soit fausse - soit juste après, soit à n'importe quel moment ? Si oui, est-ce qu'on le verra dans l'hérédité ? J'imagine que oui, sinon le raisonnement par récurrence aurait une sacrée faille :/

Bref, sinon ça va ^^' J'ai tout compris (à part ces quelques points étranges) !

Merci beaucoup =)

Bonne soirée.

[windows7]

salut

implique c'est pas equivaut .
bah tu peux voir P0 vraie et P1 fausse P2 fausse P3 vraie
heu a oui oui on ne pourrait pas montrer l heredite en effet

[Rebelle_]

D'accord, implique n'est pas équivaut (je le conçois bien), mais peut-on écrire "*P(n) implique P(n+1)* équivaut à *P(n+1) implique P(n)*" ?

[windows7]

faux.

tiens de la poule ou de l'oeuf qui est arrivé le premier ? ( ca revient a ca en gros )

on suppose P vraie a partir de k

donc pk => pk+1 => pk+1

donc pk => pk-1 ?

bref

[benekire2]

Salut Rebelle :id:

tu as raison, si une propriété était vraie au rang P(0) par exemple et qu'elle passe l'hérédité aussi et que par dessus le marché il y ait un n tel que P(n) ne soit pas vrai ( oh le vilain !! ) ça mettrai en défaut le beau principe de récurrence. Donc c'est pas possible de voir un truc du genre (enfin pas avec ces axiomes sur N)


Cela dit ta question est très légitime, et une théorie mathématique c'est fondée sur le rejet de cet axiome ( ou de celui aui dit que toute partie finie de N est majorée au choix ) , il me semble que c'est l'analyse non standard.

Windows >> C'est l'oeuf j'en suis sûr !

[windows7]

mdr bene !

j'ai rajouté 2 lignes pour etre plus explicite.

[Rebelle_]

faux.

tiens de la poule ou de l'oeuf qui est arrivé le premier ? ( ca revient a ca en gros )

on suppose P vraie a partir de k

donc pk => pk+1 => pk+1

donc pk => pk-1 ?

bref

Ben justement, vu qu'on init. à k on se fiche de savoir ce qu'il se passe à k-1, non ? :/

PS : c'est la poule qui est arrivée la première, ça a été prouvé et c'est le résultat de l'évolution des espèces

[Rebelle_]

tu as raison, si une propriété était vraie au rang P(0) par exemple et qu'elle passe l'hérédité aussi et que par dessus le marché il y ait un n tel que P(n) ne soit pas vrai ( oh le vilain !! ) ça mettrai en défaut le beau principe de récurrence. Donc c'est pas possible de voir un truc du genre (enfin pas avec ces axiomes sur N)

Coucou !

Ok, merci ^^

[Olympus]

Salut à tous :zen:

c'est la poule qui est arrivée la première, ça a été prouvé et c'est le résultat de l'évolution des espèces

Windows >> C'est l'oeuf j'en suis sûr !

Non pour Rebelle . Oui pour benekire . La poule n'est qu'une invention faite par l'œuf pour pouvoir refaire un autre œuf . Conclusion : l'œuf est arrivé en premier .

[Rebelle_]

Ah ah, elle n'est pas de toi celle-là, je l'ai déjà entendue x)

En fait, plus rigoureusement, l'oeuf qui a donné la "première poule" a été pondu par une espèce "pré-poule" (il s'agirait même d'un dinosaure).

Enfin bon, on ne va pas débattre de ça ici :P

[benekire2]

PS : c'est la poule qui est arrivée la première, ça a été prouvé et c'est le résultat de l'évolution des espèces

Bah je suis pas biologiste mais ca me semble plus logique que la poule arrive après, en effet la poule est sortit d'un oeuf, mais ne me dit pas qu'une poule l'as pondu, tout les oiseaux pondent des oeufs ... :we:

[benekire2]

Enfin bon, on ne va pas débattre de ça ici

Why not ?

C'est de la récurrence après tout ,

[Dinozzo13]

Salut !

à propos du raisonnement par récurrence

Ca me fait penser que la récurrence n'est plus vue en 1re S
(il me vient deux ou trois exo sympa sur la récurrence ^^)

Au sujet du "équivaut à", il te suffit de démontrer ta propriété par récurrence puis de démontrer sa réciproque.

ex : Montrer qu'une suite de raison est arithmétique si et seulement si, pour tout :

Conjecture :
est arithmétique de raison donc :



POn peut affirmer que pour :

Raisonnement par récurrence :
Si alors , l'égalité est vérifiée.
Supposons que pour tout entier naturel , , montrons qu'alors .
Par définition :
donc, pour tout entier naturel :

Réciproque :
Si pour tout , alors :
donc est une suite arithmétique de raison .

[Rebelle_]

Je ne fais que diffuser la bonne parole de la prof de Bio ;)
Sinon, j'imagine que des sites sérieux pourraient nous renseigner ^^

[Rebelle_]

Coucou Dinozzo :)

Il y a vraiment besoin de récurrence pour démontrer ce théorème (qui découle de la définition) ? ^^

[Dinozzo13]

ben quand on ne connaît pas encore la formule, oui ça peut servir

[Dinozzo13]

Sinon, si ça te dit, j'ai deux ou trois exo sur la récurrence, tu les veux ?
(ils sont pas long)

[Rebelle_]

Ah ben on l'avait démontrée sans récurrence (puisque l'on voit cette formule en Première justement avant la récurrence en Terminale).
Enfin, c'est quand même intéressant pour débuter. :)

[Dinozzo13]

Coucou Dinozzo

Il y a vraiment besoin de récurrence pour démontrer ce théorème (qui découle de la définition) ? ^^

C'était également un exemple ^^
Si j'avais pris un truc plus difficile, tu ne l'aurais peut-être pas compris :we:

[benekire2]

Salut dinno !

Tient d'ailleurs vous avez du (re) voir la récurrence en début de sup, le premier DS c'est passé comment ?