Pour aller plus loin : le raisonnement par récurrence en arithmétique

Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

Définitions et théorèmes

Le raisonnement par récurrence permet de démontrer qu'une propriété P(n) est vraie pour tout entier n\ge n_0. Il comporte deux étapes : - Initialisation : on vérifie que P(n_0) est vraie (souvent n_0=0 ou 1). - Hérédité : on suppose P(n) vraie pour un entier n\ge n_0 fixé (hypothèse de récurrence) et on démontre P(n+1).

Le principe de récurrence assure alors que P(n) est vraie pour tout n\ge n_0.

En arithmétique, la propriété est typiquement une divisibilité : « b\mid(a^n-c) ». L'hypothèse de récurrence se traduit par l'existence d'un entier k tel que a^n-c=bk.

Formules

  • Initialisation + Hérédité \implies \forall n\ge n_0,\;P(n).
  • Hypothèse type : a^n-c=bk, k\in\mathbb{Z}.
  • Identité de passage : a^{n+1}=a\times a^n.
  • 4^{n+1}-1=4(4^n-1)+3 ; 7^{n+1}-1=7(7^n-1)+6 ; 3^{2(n+1)}-1=9(3^{2n}-1)+8.

Méthodes type bac

  • Divisibilité d'une puissance : poser P(n)\,:\,b\mid(a^n-c). Hypothèse a^n-c=bk. Dans l'hérédité, écrire a^{n+1}=a\times a^n, substituer a^n=bk+c, développer et factoriser par b.
  • Combinaison de deux suites (ex. 3^{2n}-2^n) : faire apparaître u_n dans u_{n+1} par une décomposition astucieuse, puis ajouter un multiple visible de b.
  • Rédaction : nommer clairement P(n), traiter les deux étapes, conclure par le principe de récurrence.

Pièges

  • Oublier l'initialisation : une propriété héréditaire mais fausse au départ reste fausse partout.
  • Écrire a^n-c=bk avec k\in\mathbb{N} alors que k doit être dans \mathbb{Z}.
  • Dans l'hérédité, ne pas utiliser l'hypothèse de récurrence (la preuve est alors invalide).
  • Oublier de factoriser par b à la fin : c'est la factorisation qui prouve la divisibilité.
  • Vérifier l'initialisation au mauvais rang (par exemple n=1 alors que l'énoncé démarre à n=0).

Exemple détaillé

Montrons par récurrence que 3\mid(4^n-1) pour tout n\ge0. Initialisation : 4^0-1=0 et 3\mid0, vrai. Hérédité : supposons 4^n-1=3k avec k\in\mathbb{Z}. Alors 4^{n+1}-1=4\times4^n-1=4(3k+1)-1=12k+3=3(4k+1), qui est bien un multiple de 3. La propriété est donc héréditaire, et par principe de récurrence vraie pour tout n\ge0.

Pour l'épreuve

En arithmétique, la récurrence sert à démontrer les divisibilités de puissances que les congruences traitent aussi : connaître les deux approches est un atout, car certains énoncés imposent une méthode. La clé de l'hérédité est l'identité a^{n+1}=a\times a^n, suivie d'une substitution de l'hypothèse de récurrence puis d'une factorisation par le diviseur. Rédige soigneusement l'hypothèse de récurrence (existence d'un entier k relatif) et conclus toujours explicitement par le principe de récurrence. Pour les expressions à deux puissances comme 3^{2n}-2^n, l'astuce consiste à reconstruire u_n dans u_{n+1} et à isoler un multiple du diviseur.