Chapitre 02

Partie 2 - Principe de réccurence

Objectif

  • Utiliser le principe de récurrence pour démontrer une proposition
  • Proposition

    Une proposition est un énoncé mathématique complet qui est soit vrai soit faux.
    Par exemple :
    • "23 \geq 10" est une proposition fausse;
    • Alors que "Dans tout triangle rectangle, le carré de la longueur de l'hypothénuse est égale à la somme des carrés des longueurs des deux autres côtés" est une proposition vraie.


    Proposition

    Une proposition peut-être :

    • une égalité, par exemple \mathcal{P}_n: 1 + 2 + \dots + 3 = \dfrac{n(n+1)}{2};

    • une inégalité, par exemple \mathcal{P}_n: (1 + \pi)^n \geq 1 + n\pi ;

    • une phrase, par exemple \mathcal{P}_n: n^3 - n est un multiple de 3

    Domaine d'application

    Le raisonnement par récurrence ne peut s’utiliser que lorsque l’on cherche à démontrer qu’une proposition est vraie pour tout entier naturel n \in \mathbb{N} tel que n \geq n_0

    Propriété

    Soit n_0 \in \mathbb{N}. On considère la proposition \mathcal{P}_n défnie pour tout entier naturel n \gt n_0.
    Si les deux conditions suivantes sont vérifées :
    • Initialisation : P_n est vraie pour l’entier n_0;
    • Hérédité : pour tout entier naturel k \leq n_0, «\mathcal{P}_k est vraie.» implique \mathcal{P}_{k+1} est vraie.


    Alors on peut conclure que, pour tout n\in \mathbb{N}, tel que n \geq n_0, la proposition \mathcal{P}_n est vraie.

    Exemple de mise en oeuvre

    Démontrer que pour tout entier naturel n \in \mathbb{N}^{*}
    1 + 2 + \ldots + n = \dfrac{n(n+1)}{2}

    0 - Ennoncé la proposition

    Soit n \in \mathbb{N}*, on note \mathcal{P}_{n} la proposition
    1+2+3 + \ldots + n = \dfrac{n(n+1)}{2}

    I - Initialisation

    Pour n = 1 :
    D'une part, le membre de gauche de l'équalité vaut 1
    D’autre part,le membre de droite de l'équalité vaut \dfrac{1 \times 2}{2} = 1

    On a ainsi montré que est \mathcal{P}_1 vraie.

    II - Hérédité

    Supposons qu'il existe k \in \mathbb{N}, tel que P_{k} soit vraie.
    Montrons que P_{k+1} est vraie;

    II - Hérédité

    D'après l'hypothèse de récurrence ( \mathcal{H.R.}):
    1+ 2 + 3 + \ldots + k = \dfrac{k(k+1)}{2}
    1+ 2 + 3 + \ldots + k + \textcolor{orange}{k+1} = \dfrac{k(k+1)}{2} + \textcolor{orange}{k+1}
    1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k(k+1)}{2} + \textcolor{orange}{\dfrac{2(k+1)}{2}}
    1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k(k+1)+\textcolor{orange}{2(k+1)}}{2}
    1+ 2 + 3 + \ldots + k + k+1 = \dfrac{k\textcolor{orange}{(k+1)}+2\textcolor{orange}{(k+1)}}{2}
    1+ 2 + 3 + \ldots + k + k+1 = \dfrac{(k+1)\big(k+2\big)}{2}
    Donc la proposition \mathcal{P}_{k+1} est vraie.

    III - Conclusion

    Par le principe de récurrence, on en déduit que P_n est vraie pour tout n \in N^{*}

    Exercice type

    Soit (U_n) la suite définie par U_0 = 2 et, pour tout entier naturel n,~ U_{n+ 1} = 0,6 U_n + 4 .
    1. Démontrer par récurrence que U_n \leq 10 pour tout entier naturel n.
    2. On considère la suite (V_n), définie par :
      V_n = U_n - 10
      • a. Montrer que la suite (V_n) est géométrique. Déterminer son terme initial et sa raison
      • b. Déterminer l'expression de V_n en fonction de n. En déduire celle de (U_n)