Deuxième principe d'induction

[invite1237a629]

Hello,

Bon, c'est censé être appliqué à l'informatique, mais ce sont des maths

En fait, je voulais savoir ce qu'il fallait démontrer lorsque l'on utilise le deuxième principe d'induction (induction généralisée) : «Si P(k) vraie pour tout k < n implique que P(n) est vraie, alors quel que soit n, P(n) vraie.»

Ce que j'avais cru comprendre du cours, c'était qu'il fallait montrer que c'était vérifié pour tout rang k < n... Mais dans un exercice, on a supposé (comme pour le premier principe où l'on suppose que la proposition est vraie au rang n) que P(k) est vérifiée pour tout k < n, puis on a montré que pour n, la proposition était vraie.

Alors que faut-il faire exactement ? (pour l'exercice, c'était un peu flou...Donc je ne sais pas si je peux m'y fier)

Merci
-----

[Gwyddon]

Hello,

Il faut seulement que tu suppose que P(k) est vérifié pour tout k < n, puis montrer alors que P(n) est vérifié.

Puis tu pourras conclure qu'en effet P(n) est alors vrai pour tout n supérieur ou égal à m, si tu as montré que P(m) est vrai.

[Deeprod]

C'est ce qu'on appelle aussi la récurence pleine, ou forte ?

[invite1237a629]

@ Gwyddon : merci beaucoup pour cette réponse rapide

@ Deeprod : il semblerait que oui ^^ on a appelé ça récurrence complète, mais l'idée a l'air de rester la même. Quant à l'origine étymathématicologique de cette différence, chuis pas sûre de mon idée

[A voir en vidéo sur Futura]

[invite1237a629]

Bon, en réalité, je compte appliquer ça à un exercice, mais je ne suis pas sûre que ce soit la bonne méthode.

J'ai la fonction d'Ackerman f: IN x IN -> IN :
(i) f(0,n)=n+1
(ii) f(m,0)=f(m-1,1)
(iii) f(m,n)=f(m-1,f(m,n-1))

Je dois démontrer que f(m,n) est définie pour tout couple (m,n) appartenant à IN x IN.

Donc je passe par le deuxième principe d'induction, en supposant que c'est défini pour tout m₁ < m et n₁ < n (donc montrer que c'est bon pour les rangs m+1 et n+1)

Et c'est là que j'ai un premier doute. Est-ce que je dois vérifier que f(m+1,n), f(m,n+1) et f(m+1,n+1) sont définies ou simplement f(m+1,n+1) ?

La suite n'est que supposition...mais je me heurte encore à un problème : avec le m+1 initial, je le garderai (cf (iii)), alors que n diminuera, jusqu'à atteindre 0. Ai-je le droit alors d'utiliser (ii), alors que je n'ai pas encore démontré qu'au rang m+1 c'était défini ?

[MMu]

MiMolette, c'est immédiat si tu utilise dans ce cas l'induction (ou encore la récurrence) avec la relation d'ordre lexicographique :

[invite1237a629]

Merci bien, je ne connaissais pas cet ordre lexicographique. J'ai flirté avec lui dans la correction du TD et tout s'éclaire