Exercice de raisonnement par récurrence

Mélodie - Mis à jour le 28/03/2022
exercice de raisonnement par récurrence

Avant de présenter les raisonnements par récurrence, nous allons donner une propriété importante de l’ensemble des entiers naturels que nous admettrons.

Toute partie non vide de \mathbb{N} admet un plus petit élément.

Conséquence : Il n’existe pas de suite infinie d’entiers naturels strictement décroissante.

Le principe de récurrence

La récurrence simple

Soit n_0\in\mathbb{N}. On considère une propriété (ou un prédicat) \mathcal{P}_n définie pour n\in\mathbb{N}, n\ge n_0 telle que :
  • Initialisation : \mathcal{P}_{n_0} est vraie;
  • Hérédité : pour tout n\in\N, n\ge n_0, si \mathcal{P}_n est vraie, alors \mathcal{P}_{n+1} l’est aussi.
  • Alors, pour tout n\in\mathbb{N}, n\ge n_0, \mathcal{P}_n est vraie.

    Démonstration

    On considère l’ensemble A =\big\{n \in\N,\;n\ge n_0,\; \mathcal{P}_n\text{ est fausse}\big\}.
    On suppose que A est non vide, il admet donc un plus petit élément que nous noterons m qui est différent de n_0 (car \mathcal{P}_{n_0} est vraie). Alors m-1 n’est pas dans A et donc l’entier suivant, m, n’est pas non plus dans A ce qui amène à une contradiction. On en déduit que A est vide.

    Exemple

    Montrer que pour tout n\in\mathbb{N}, la somme S_n des n premiers entiers naturels est égale à \dfrac{n(n+1)}{2}.
    Soit n\in\mathbb{N}. Montrons par récurrence sur n\in\mathbb{N} la propriété \mathcal{P}_n : S_n=\dfrac{n(n+1)}{2}.
    Initialisation : Pour n=0, S_0=0, la propriété est évidente.
    Hérédité : Soit n\in\mathbb{N}. On suppose que \mathcal{P}_n est vraie, montrons que \mathcal{P}_{n+1} l’est encore. Par définition : S_{n+1}=S_n+(n+1). D’après l’hypothèse de récurrence, on a : S_n=\dfrac{n(n+1)}{2}.
    Ainsi : S_{n+1}=\dfrac{n(n+1)}{2}+n+1=\dfrac{(n+1)(n+2)}{2}.
    \mathcal{P}_{n+1} est bien vraie. D’après le principe de récurrence, la propriété est vraie pour tout n\in\mathbb{N}.

    On va maintenant présenter deux variantes du raisonnement par récurrence : la récurrence double et la récurrence forte.

    La récurrence double

    Proposition

    Soit n_0\in\mathbb{N}. On considère une propriété (ou un prédicat) \mathcal{P}_n définie pour n\in\mathbb{N}, n\ge n_0 telle que :
  • Initialisation : \mathcal{P}_{n_0} et \mathcal{P}_{n_0+1} sont vraies ;
  • Hérédité : pour tout n\in\N, n\ge n_0, si \mathcal{P}_n et \mathcal{P}_{n+1} sont vraies, alors \mathcal{P}_{n+2} l’est aussi.
  • Alors, pour tout n\in\mathbb{N}, n\ge n_0, \mathcal{P}_n est vraie.

    Exemple

    On considère la suite de Fibonacci définie par : u_0=0,\;u_1=1,\;\forall n\in\mathbb{N},\;u_{n+2}=u_{n+1}+u_n.
    Soit n\in\mathbb{N}^*. Montrons par récurrence double sur n\in\mathbb{N}^* la propriété \mathcal{P}_n : u_{n}\in\mathbb{N}^*
  • Initialisation : Pour n=1 et n=2, la propriété est évidente.
  • Hérédité : Soit n\in\mathbb{N}^*. On suppose que \mathcal{P}_n et \mathcal{P}_{n+1} sont vraies, montrons que \mathcal{P}_{n+2} l’est encore. On a : u_{n+2}=u_{n+1}+u_{n}. La somme de deux entiers naturels non nuls est encore un entier naturel non nul, \mathcal{P}_{n+2} est bien vraie.
  • D’après le principe de récurrence double, la propriété est vraie pour tout n\in\mathbb{N}^*.

    La récurrence forte

    Proposition

    Soit n_0\in\mathbb{N}. On considère une propriété (ou un prédicat) \mathcal{P}_n définie pour n\in\mathbb{N}, n\ge n_0 telle que :
  • Initialisation : \mathcal{P}_{n_0} est vraie ;
  • Hérédité : pour tout n\in\mathbb{N}, n\ge n_0, si, pour tout k\in\llbracket n_0,n\rrbracket, \mathcal{P}_k est vraie, alors \mathcal{P}_{n+1} l’est aussi.
  • Alors, pour tout n\in\mathbb{N}, n\ge n_0, \mathcal{P}_n est vraie.

    Exemple

    Montrons par récurrence forte sur n\in\mathbb{N}, n\ge 2, la propriété \mathcal{P}_n : « n admet une décomposition comme produit de nombres premiers ».
    Initialisation : 2 est un nombre premier, donc \mathcal{P}_2 est vraie.
    Hérédité : Soit n\in\mathbb{N}, n\ge 2. On suppose que \mathcal{P}_k est vraie pour tout k\in\llbracket 2,n\rrbracket, montrons que \mathcal{P}_{n+1} l’est encore. Deux cas sont à considérer :
  • soit n+1 est premier, dans ce cas, \mathcal{P}_{n+1} est bien vraie ;
  • soit n+1 n’est pas premier, alors, il existe deux entiers p et q avec 2 \le p \le n et 2 \le q \le n tels que n+1=pq. Or, \mathcal{P}_p et \mathcal{P}_q sont vraies, donc p et q sont des produits de nombres premiers et n+1 aussi. \mathcal{P}_{n+1} est encore vraie.
  • D’après le principe de récurrence forte, la propriété est vraie pour tout n\in\mathbb{N}, n\ge 2.
    livre maths mpsi vuibert

    Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, méthodes, entraînement et corrigés (éditions Vuibert, juin 2021) écrit par E. Thomas, S. Bellec, G. Boutard. ISBN n°9782311408720

    2/5 - (1 vote)
    profile picture
    Mélodie
    Journaliste
    Hello ! Spécialisée dans toutes les questions de l'enseignement supérieur et l'orientation, j'espère que mes articles t'aideront à trouver ta voie et devenir la meilleure version de toi-même. Mes autres sujets de prédilection ? L'écologie, la science et la littérature.

    Laisse-nous un commentaire !

    Des questions ? Des bons plans à partager ? Nous validons ton commentaire et te répondons en quelques heures ! 🎉

    ebook

    Notre ebook pour réussir ta prépa

    Télécharge notre guide et découvre comment réussir tes années en prépa grâce à nos conseils et nos méthodes ! 👩🏻‍🎓