Question récurrence forte

[Wekron]

Bonjour, je rentre en première année de maths l'année prochaine et j'avais une question.
Un des théorème de la récurrence forte pour les entiers est:
Soit P(n) une propriété définie sur N,
si [∀k < n P(k)] ⇒ P(n) (pour tout n ∈ N)
alors P(n) pour tout n ∈ N.


Ce que je ne comprends pas, c'est que lorsque l'on prend n=0, comment montrer que l'on a P(0)(pour prouver le théorème)? Car l'ensemble des k<n étant vide, a-t-on donc le droit de dire que l'on a P(k)?

J'ai regardé sur wikipédia et ils disent:
Dans le cas où n = 0, l'hypothèse est vraie par vacuité de l'ensemble des k < 0, ainsi la quantification est vraie et l'assertion revient à P(0).
Mais je n'ai pas bien compris la réponse, même relisant plusieurs fois.

Merci de votre réponse!

[Ayzee]

Pour l'initialisation, c'est comme une récurrence simple tout simplement. Même pour une récurrence simple on ne suppose pas le rang précédent dans l'initialisation, on se contente de montrer P(0)! C'est seulement pour l'hérédité qu'on le fait donc il en est de même pour la récurrence forte à part qu'ici dans l'hérédité on suppose pour tout k<n.

[Archytas]

Soit P(n) une propriété définie sur N,
si [∀k < n P(k)] ⇒ P(n) (pour tout n ∈ N)
alors P(n) pour tout n ∈ N.

Enoncé tel quel ça m'a l'air faux. Il manque en effet l'initialisation. On peut par exemple montrer que pour tout entier on a . L'implication est vraie (car est fausse et "faux n'importe quoi" est une proposition vraie) mais est bien entendu fausse pour tout .

Pour une récurrence forte on procède comme une récurrence normale, on initialise au rang qu'on veut puis on montre l'hérédité pour les rangs suivants. La seule différence est que pour le passage à on utilise pas seulement l'hypothèse au rang mais tous les pour .

[Wekron]

Pourtant j'ai retrouvé ce théorème sur wikipedia (https://fr.m.wikipedia.org/wiki/Raisonn ... A9currence voir "Autres formes de récurrence puis Récurrence bien fondé") et dans le Ramis (le livre universitaire que j'utilise).

Je ne parle pas de comment montrer que l'on a P(n) pour un n donné mais de comment démontrer le théorème, cad en supposant l'hypothèse: pour tout n, (pour tout k<n, P(n)).
Or la démonstration est de considérer l'ensemble A des n tel que P(n) est faux, de prendre le minimum, disons n', et de montrer que les k <n vérifient P(k) donc P(n) est vérifiée, donc que l'on a P(n) pour tout n car l'ensemble A est vide. Sauf que si l'on suppose 0 en tant que minimum de A, comment montrer que l 'on a P(0) car il n'y a pas de k<0?

[lyceen95]

Dans une récurrence classique, on montre que la propriété est vraie pour n=0 et on montre ensuite l'hérédité.
Ici, c'est bien caché, mais c'est pareil.

On montre uniquement l'hérédité.
On montre donc : pour tout entier k, si la propriété est vraie pour tous les entiers positifs strictement inférieurs à k, alors elle est vraie pour k.
Si on a réussi à montrer ça, sans erreur, alors on a montré :
Pour k donné, si la propriété est vraie pour tous les entiers positifs strictement inférieurs à k, elle est vraie aussi pour k.

Formulé autrement :
Pour k donné, si la propriété est fausse pour aucun entier entre 0 et k-1, elle est vraie pour k.

Ou encore, en démontrant l'hérédité, on a démontré :
Pour k donné, si il n'y a aucun entier x entre 0 et k-1 (0<=x<=k-1) tel que la propriété soit fausse pour ce x , alors la propriété est vraie pour k.

Appliquons cela pour k=0
y a-t-il des entiers entre 0 et -1 (0<=x<=-1) tels que la propriété soit fausse ?
Non, évidemment, parce qu'il n'y a même pas d'entier dans cet intervalle.
Donc la propriété est vraie pour k=0.

L'initialisation est démontrée, dès que l'hérédité est démontrée.
Attention : c'est vrai dans le cas de la récurrence forte, pas dans le cas de la récurrence classique.

[Archytas]

Ok pardon, oui j'ai compris.

La proposition est équivalente à si on convient que est vraie. Dans tous les cas on doit bien démontrer .

Je ne parle pas de comment montrer que l'on a P(n) pour un n donné mais de comment démontrer le théorème, cad en supposant l'hypothèse: pour tout n, (pour tout k<n, P(n)).

Je ne comprends pas très bien ce que tu veux. Si tu veux montrer le théorème tu dois supposer pour tout et en déduire .
Si tu suppose "pour tout n, (pour tout k<n, P(n))" alors est vraie par hypothèse.

[Wekron]

Super merci beaucoup lyceen85 et Archytas c'est les explications que j'attendais

Sinon Archytas, pour démontrer le théorème je me suis trompé j'ai mis n à la place de k effectivement mais le raisonnement après reste le même.
Merci pour toutes vos réponses en tout cas!