Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Deuxième principe d'induction



  1. #1
    MiMoiMolette

    Deuxième principe d'induction


    ------

    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

    -----

  2. Publicité
  3. #2
    Gwyddon

    Re : Deuxième principe d'induction

    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.
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  4. #3
    Deeprod

    Re : Deuxième principe d'induction

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

  5. #4
    MiMoiMolette

    Re : Deuxième principe d'induction

    @ 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
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  6. A voir en vidéo sur Futura
  7. #5
    MiMoiMolette

    Re : Deuxième principe d'induction

    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 m1 < m et n1 < 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 ?
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

  8. #6
    MMu

    Re : Deuxième principe d'induction

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

  9. Publicité
  10. #7
    MiMoiMolette

    Re : Deuxième principe d'induction

    Merci bien, je ne connaissais pas cet ordre lexicographique. J'ai flirté avec lui dans la correction du TD et tout s'éclaire
    - Je peux pas, j'ai cours
    - Vous n'êtes pas un peu vieux ?
    - Je suis le prof

Discussions similaires

  1. Probleme D'induction
    Par lobo dans le forum Électronique
    Réponses: 4
    Dernier message: 28/12/2007, 20h04
  2. champ d'induction d'une bobine
    Par yocto dans le forum Électronique
    Réponses: 5
    Dernier message: 16/11/2007, 09h04
  3. Hg dans les phénomènes d'induction
    Par kub dans le forum Physique
    Réponses: 4
    Dernier message: 19/10/2005, 18h48
  4. Systeme d'induction???
    Par Walker dans le forum Biologie
    Réponses: 3
    Dernier message: 03/09/2005, 11h55
  5. problème d'induction.
    Par xjunex dans le forum Physique
    Réponses: 4
    Dernier message: 26/04/2005, 11h54