Récurrence

Balix

Je viens de trouver dans une copie pour une récurrence,
la récurrence est correctement initialisée, mais comme HR pour l'hérédité, l'élève m'écrit
"Supposons qu'il existe n tel que la propriété soit vraie"
au lieu de soit n quelconque, supposons la propriété vraie au rang n.
Ce qui suit est juste.

Les 2 formulations ne me paraissent pas équivalentes , mais avec la sienne, il me semble que la récurrence tient debout aussi.

Me trompé-je ?

kioups

Pour celle de l'élève, on prend un n particulier, pas n'importe quel n. Mais je préfère effectivement l'écriture de l'élève.

Poirot

La formulation de l'élève est fausse. Il ne suffit pas de supposer l'initialisation et qu'il existe un rang $n$ tel que $P(n)$ et d'en déduire $P(n+1)$ pour avoir $P(n)$ pour tout entier $n$. C'est particulièrement clair pour la propriété $P(n) : n+1=1$.

Balix

J'ai tendance à penser comme toi Poirot après que Jaybe m'ait mis ça sous forme logique en pm; mais je dois être particulièrement obtus aujourd'hui, je ne vois pas comment tu déduis P(n+1) de P(n) dans ton exemple, j'ai (n+1) +1 = 2 , pas 1.

Edit: C'est bon j'ai pigé

marsup

Avec "supposons qu'il existe $n$ tel que $P(n)$, on ne voit pas trop ce que l'on va montrer dans l'hérédité.

En premier lieu, si on fait l'hérédité après l'initialisation, il n'y a pas besoin de supposer qu'il existe un tel $n$, puisqu'on a déjà vu que $n=0$ (ou $n=n_0$) convient.

Ensuite, c'est ambigu, parce qu'il n'est pas clair si on va montrer que l'existence d'un tel $n$ (qui est déjà vraie d'après l'initialisation!) implique $P(n+1)$ au choix :
pour au moins un de ces $n$,
ou bien pour tous les tels $n$.

Dans le premier cas, la récurrence ne marche pas. (je propose $P(n) : n(n-1)=0$ vraie et "héréditaire" pour $n=0$)

Dans le deuxième cas, à quoi servait de supposer l'existence de tels $n$ (déjà acquise) si c'est pour finalement montrer que tous les tels $n$ vérifient aussi $P(n+1)$ ? Quel rapport avec leur existence ?

Quel rapport logique entretiennent les faits suivants :

le fait que l'ensemble des $\{n \text{ tq } P(n)\}$ soit stable par passage au successeur, (hérédité)
le fait que cet ensemble soit non-vide (initialisation) ?

Pourquoi supposer le deuxième fait pour montrer le premier, alors qu'on l'a déjà vu tout de suite ?

Bref, c'est très mal dit : une rédaction qui dit "supposer" des trucs déjà acquis, et qui laisse l'ambigüité du "pour tout $n$ tel que" ou "pour au moins un $n$ tel que" ouverte.