Principe de récurrence forte

[casus_orez]

Bonjour à tous,

Je pense faire une erreur de compréhension du principe de récurrence forte.

Voici le principe tel qu'il est présenté dans le livre "Mathématiques - Tout en un pour la licence niveau 1":

"Soit P(n) une propriété qui dépend d’un entier positif ou nul n.

Dès qu'un entier m >= n0 est tel que P(k) soit vraie pour tous les entiers k vérifiant n0=n0 tel que P(k) vraie pour tous les entiers vérifiant n0<=k<m.
Or P(2) est évidemment fausse...

Pourriez-vous svp m'éclairer sur ce point?

Merci d'avance!

Bonne soirée

[Skullkid]

Bonjour, en effet le principe tel que tu l'as écrit est faux, et d'ailleurs n'a rien à voir avec la récurrence forte. Soit c'est une faute grave du bouquin, soit tu as mal recopié. Un énoncé correct du principe de récurrence forte est :

Si P(n0) est vraie pour un certain n0 et si, quel que soit l'entier n, la validité de P(k) pour tout n0 = n0.

À comparer avec la récurrence simple :

Si P(n0) est vraie pour un certain n0 et si, quel que soit l'entier n, la validité de P(n) entraîne celle de P(n+1) ; alors P(n) est vraie pour tout n >= n0.

Dans les deux cas on a besoin d'une initialisation et d'une hérédité. La différence est que pour la récurrence simple l'hérédité relie un rang avec celui qui le précède immédiatement, alors que pour la récurrence forte elle relie un rang avec tous ceux qui le précèdent.

[zygomatique]

salut

récurrence forte ou faible c'est du pareil au même ...

1/ initialisation (pour une ou plusieurs valeurs)

2/ hérédité :: est vraie

...

maintenant dans ces deux ensembles il peut n'y avoir que n pour le premier et n + 1 pour le second ....

[bolza]

Bonjour

salut

récurrence forte ou faible c'est du pareil au même ...

1/ initialisation (pour une ou plusieurs valeurs)

2/ hérédité :: est vraie

...

maintenant dans ces deux ensembles il peut n'y avoir que n pour le premier et n + 1 pour le second ....

les deux principes sont peut-être équivalents, mais parfois la récurrence faible ne suffit pas à montrer certaines propriétés.


P.S. : la récurrence forte que je connais, ne fait pas intervenir le n+1 :

Si P(n0) est vrai et si pour tout m, la validité de P(k) pour tout n0 n0.

à mon avis c'est cette définition qui doit être dans ton bouquin casus (qui est équivalente à celle donnée par Skullkid de toute façon).

[zygomatique]

je ne comprends pas ton PS ....

EDIT : ha si mais que tu passe de m - 1 à m ou de m à m + 1 c'est du pareil au même ...


le principe de récurrence c'est simplement de montrer que si une propriété est vraie pour un ensemble E d'entiers alors elle est vraie pour un ensemble F d'entiers contenant strictement E (F a strictement plus d'éléments que E)

pour un exemple voir http://www.ilemaths.net/sujet-demonstration-par-recurrence-609554.html#msg5157047

:lol3:

[Robot]

Je pense que casus-orez a mal retranscrit ce qu'il a lu. Je corrige en un énoncé correct

"Soit P(n) une propriété qui dépend d’un entier positif ou nul n.
On suppose que dès qu'un entier m >= n0 est tel que P(k) soit vraie pour tous les entiers k vérifiant n0= n0"

Ce principe de récurrence forte est parfaitement exact. Et c'est vrai que sous cette forme il n'y a pas besoin d'initialisation.

[Robot]

Un exemple d'application de ce "principe de récurrence forte" : tout entier >1 se décompose en produit de nombres premiers.

On montre la propriété d'hérédité : si c'est vrai pour tout entier > 1 et 1 et <n. Par hypothèse de récurrence, p et q sont produits de premiers, donc n aussi.

On en déduit par récurrence la conclusion annoncée, sans qu'il y ait besoin d'une initialisation.

[beagle]

Un exemple d'application de ce "principe de récurrence forte" : tout entier >1 se décompose en produit de nombres premiers.

On montre la propriété d'hérédité : si c'est vrai pour tout entier > 1 et 1 et <n. Par hypothèse de récurrence, p et q sont produits de premiers, donc n aussi.

On en déduit par récurrence la conclusion annoncée, sans qu'il y ait besoin d'une initialisation.

Dans le mème exemple wiki ne fait pas l'impasse sur l'initialisation:
https://fr.wikipedia.org/wiki/Raisonnement_par_r%C3%A9currence#R.C3.A9currence_forte

Et zygomatique qui explique que le n et n+1 n'est qu'un cas particulier de la récurrence forte,
ben zygo il reprend
1)initialisation
2)hérédité
Zygomatique:
"récurrence forte ou faible c'est du pareil au même ...

1/ initialisation (pour une ou plusieurs valeurs)

2/ hérédité :: \{n_0 \le k \le n => P(k) \ est \ vraie\} => \{n_0 \le k \le n + 1 => P(k) \ est \ vraie\} est vraie

...

maintenant dans ces deux ensembles il peut n'y avoir que n pour le premier et n + 1 pour le second ....
___"

[Robot]

Dans le mème exemple wiki ne fait pas l'impasse sur l'initialisation:
https://fr.wikipedia.org/wiki/Raisonnement_par_r%C3%A9currence#R.C3.A9currence_forte
___"

Ca montre que wikipedia n'est pas toujours pertinent. La récurrence forte donnée sur la page wikipedia n'est pas la même.
La récurrence forte telle que je l'ai formulée n'a pas besoin d'initialisation, je le répète encore une fois. Beagle, n'es-tu pas convaincu ?

[beagle]

Ca montre que wikipedia n'est pas toujours pertinent. La récurrence forte donnée sur la page wikipedia n'est pas la même.
La récurrence forte telle que je l'ai formulée n'a pas besoin d'initialisation, je le répète encore une fois. Beagle, n'es-tu pas convaincu ?

ah, ok, j' ai survolé.Je regarderai ta définition plus précisément.
Je viens d'un vieux bac C où on ne faisait pas la récurrence.
J'ai découvert le raisonnement par récurrence en arrivant sur ce site.
Et je n'avais jamais vu la récurrence forte jusque là.
Donc je n'y connais rien à la base.
Ce que j'aimais bien avec la récurrence "faible" c'est que l'on se rapproche du
si A alors B, or A vrai
si A alors B était l'hérédité
A vrai était l'initialisation

Donc OK je vais relire ta façon de définir la récurrence forte,
pour mieux comprendre sa force, merci.

PS: pte ben que ta définition ressemble à
si A vrai alors B,
donc on sait dès le départ que A vrai, c'est ça?
L'initialisation est déjà presente, présentée dès le départ?

[Robot]

Le principe de récurrence forte pour la propriété , tel que je l'ai énoncé, se ramène bien sûr à la récurrence habituelle pour la propriété définie comme "pour tout tel que , ".