Le raisonnement par reccurence est un raisonnement très utilisé en mathématiques. Il permet de démontrer une propriété entière en démontrant seulement une partie que l'on est capable de répéter pour toutes les autres. Par exemple pour démontrer que tous les barreaux d'une échelle sont accessible, il suffit de montré que l'on peut monté sur le premier barreau ET que dès que l'on est sur n'importe quel barreau le suivvant est accessible.
En mathématique ceci s'écrit de la manière suivante:

Soit une propriété P_n à démontrer pour tout n Naturel ou pour n≥n_o

(n_o Naturel).

     Le principe de récurrence se démontre en prouvant:

           1. L'initialisation.

     Montrer que P est vraie pour n = 0 (ou pour n = n_o)

(c'est le premier barreau de l'echelle)
 

           2. L'hérédité.

     On suppose la propriété P vraie au rang k (k Naturel)

     On démontre alors P est vraie au rang k+1

(c'est la possibilité de passer d'un barreau au suivant)
 

           3. Si l'initialisation et l'hérédité sont prouvé alors on onclue P vraie pour tout n Naturel (ou pour tout n≥n_o)

      Voici un exemple pour rendre ce raisonnement plus claire:

  1. Montrer que pour tout n Naturel, on a 5ⁿ-2ⁿ est un multiple de 3.

         Montrons le par récurrence

              a) initialisation

Pour n=0 ,  5⁰-2⁰ = 1-1 = 0    et 0 est un multiple de 3  (0=3x0)

        Donc l'initialisation est vérifié.

             b) L'hérédité

Supposons P vraie au rang k (k Naturel)

   [5^k-2^k est un multiple de 3]  ->  hypothése de recurrence

et montrons qu'alors P est vraie au rang k+1

5^k+1-2^k+1 = 5^k x5 -2^k x2

              = 5^k x(3+2) -2^k x2

              = 3 x5^k +5^k x2 -2^k x2

              = 3 x5^k +2x(5^k -2^k)

    3 x5^k est un multiple de 3,                                                                  

       et par hypothèse de recurence 5^k -2^k est un multiple de 3

Or la sommes de deux multiple de 3 est un multiple de 3.

 Donc 3 x5^k +2x(5^k -2^k) est un multiple de 3 et par égalité 5^k+1-2^k+1 aussi.

                 c) Conclusion

Initialisation et hérédité prouvé donc 5^k-2^k est un multiple de 3 pour tout n Naturel.

      Un exercice typique d'algèbre qui entraine au raisonnement par reccurence. Cette esprit logique que donne ce raisonnement est important en mathématique.

      Exercice 1:

Montrer par récurrence que pour tout n Naturel on a 3³ⁿ⁺² - 2ⁿ⁺⁴  est un multiple de de 5.

     Correction 1:

•    initialisation

Pour n = 0  3^{3 x 0 +2} - 2^{0 + 4}  =  25       et 25 est un multiple de 5.

     Donc l'initialisation est vérifier

• hérédité

Supposons que P la Propriété est vraie au rang k (k Naturel)

        [ 3³ⁿ⁺² - 2ⁿ⁺⁴  multiple de 5]  est notre hypothèse de recurrence

        et montrons qu'alors P est vraie au rang k+1

    3^{3(k+1) +2}  - 2^{(k+1) +4}  =  3^{3k +5}  - 2^k+5  =  3^{3k +2}  x3³  - 2^{k +4}  x2   

                                   =  3^{3k +2}  x27  - 2^{k +4}  x2

                                   =  3^{3k +2}  x(25+2)  - 2^{k +4}  x2

                                   =  25 x 3^{3k +2}    + 2 x [ 3^{3k + 2}  + 2^{k +4} ]

25 x 3^{3k +2}   est divisible par 5   puisque 25 l'est.

2 x [ 3^{3k + 2}  + 2^{k +4} ]    est divisible par 5 puisque c'est notre hypothèse de départ  (le facteur 2 n'influent pas).

             L'hérédité et la récurrence sont vérifié donc 3³ⁿ⁺² - 2ⁿ⁺⁴ est un multiple de 5.

     Exercice 2:

Montrer que pour tout n Naturel on a 3⁶ⁿ⁺²  - 2 est un multiple de 7.

C'est le même principe que les exercice précédent, il n'y a donc pas de correction. Ceci motive plus pour le faire soi-même. De plus cette exercice ne devrait pas poser de probèmes.

Retour à l'accueil                             Haut de page