Épisode 1
1. Principe et illustration
Avant de commencer, regarde les vidéos
Épisode 1
1. Principe et illustration
Épisode 2
2. Exemples
Introduction :
En mathématiques, un certain nombre de propriétés dépendent d’un entier naturel n.
Par exemple, la somme des entiers naturels de 1 à n est égale à 2n(n+1), c’est-à-dire que pour tout entier naturel n :
1+2+3+...+n=2n(n+1)
Vérification de ce résultat pour n=2 et pour n=3 :
1+2=3 et 22(2+1)=3
1+2+3=6 et 23(3+1)=6
Même si on vérifie ce résultat jusqu’à n=100, cela ne démontre pas qu’il est vrai pour tout n. Pour effectuer cette démonstration, on dispose d’un outil particulier : le raisonnement par récurrence.
Le raisonnement par récurrence
Principe
Pour démontrer par récurrence qu’une proposition (Pn) est vraie pour tout entier naturel n supérieur ou égal à un entier naturel n0 fixé, on procède en trois étapes.
Avant de commencer, on note (Pn) la proposition que l’on va démontrer.
On vérifie que (Pn0) est vraie, c’est-à-dire que la proposition est vraie pour le premier indice n0. On dit qu’on a initialisé la récurrence.
On suppose que pour un entier n quelconque n>n0, (Pn) est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition (Pn+1) est vraie. On a ainsi prouvé que l’hypothèse de récurrence « (Pn) vraie » est héréditaire.
Lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition (Pn) est vraie pour tout entier naturel n(n>n0).
Illustration
Démonstration de la formule vue en introduction à l’aide du raisonnement par récurrence :
Montrons que pour tout entier naturel n, 1+2+3+4+…+n=2n(n+1)
Notons (Pn) la proposition : 1+2+3+4+…+n=2n(n+1)
La proposition (P1) est vraie car 1=21(1+1)
On conçoit et on admet que si l’on sait démontrer que « (Pn) vraie » entraîne « (Pn+1) vraie », alors la proposition est vraie pour tout entier naturel n>0.
Supposons donc que (Pn) est vraie pour un entier naturel n, c’est-à-dire que pour un entier naturel n :
1+2+3+4+…+n−1+n=2n(n+1)
Montrons maintenant que la propriété est vraie au rang supérieur (au rang n+1), c’est-à-dire que (Pn+1) est vraie.
Autrement dit, montrons que :
1+2+3+...+n+(n+1)=2(n+1)(n+2)
Comme (Pn) est vraie, alors dans la somme 1+2+3+...+n+(n+1), on peut remplacer les n premiers termes par 2n(n+1)
On obtient alors :
En factorisant par n+1, on obtient :
En réduisant le deuxième facteur au même dénominateur 2, on a :
Ainsi (Pn+1) est vraie.
(Pn) est vraie pour tout entier naturel n>0, c’est-à-dire pour tout entier naturel n, 1+2+3+…+n= 2n(n+1)
Exemples
Exemple 1
Exemple
On considère la suite (un) définie par u0=1 et pour tout entier naturel n>0, un+1=un+1
On montre par récurrence que tous les termes de la suite (un) sont strictement positifs et que la suite est croissante.
Rappel
Une suite (un) est croissante si pour tout entier naturel n, un≤un+1
Il s’agit de démontrer que 0<un≤un+1
Commençons par noter (Pn) la proposition 0<un≤un+1
u0=1 et u1=u0+1=(1+1)=2
On a bien 0<1<2 donc 0<u0≤u1
Supposons la proposition (Pn) vraie pour un certain entier n, c’est-à-dire : 0<un≤un+1
Montrons que la proposition (Pn+1) est vraie (c’est-à-dire : 0<un+1≤un+2), ce qui est équivalent, en utilisant la définition de la suite (un), à :
0<un+1≤un+1+1
D’après l’hypothèse de récurrence :
0<un≤un+1
On ajoute 1 aux inégalités :
1<un+1≤un+1+1
Comme la fonction racine carrée est strictement croissante sur l’intervalle [0 ;+∞[, on obtient :
1<un+1≤un+1+1
Soit : 0<1<un+1≤un+2
Par récurrence, la proposition (Pn) est vraie pour tout entier naturel n, donc la suite (un) est croissante et à termes strictement positifs pour tout entier naturel n.
Exemple 2
Exemple
Démontrons que pour tout entier naturel n : 4n+2 est divisible par 3.
Notons Pn la proposition « 4n+2 est divisible par 3 ».
Pour n=0, on a 40+2=1+2=3 et 3 est bien divisible par 3.
Supposons la proposition Pn vraie pour un entier n.
On a alors 4n+2 est divisible par 3, c’est-à-dire qu’il existe un nombre b tel que 4n+2=3×b
Astuce
Pour montrer qu’un nombre x est divisible par un entier a, il faut montrer qu’il existe un nombre b tel que x=a×b
Montrons maintenant que la proposition Pn est vraie au rang n+1, c’est à dire que 4n+1+2 est aussi divisible par 3.
On a : 4n+2=3×b
4n=3×b−2
4n+1+2=4n×4+2
4n+1+2=(3×b−2)×4+2
4n+1+2=(3×b−2)×4+2=12b−8+2=12b−6
4n+1+2=3×(4b−2)
Comme le nombre 4b−2 est un entier alors on a bien 4n+1+2=3×k en posant k=4b−2
Par récurrence, pour tout entier naturel n, Pn est vraie, donc pour tout entier naturel n, 4n+2 est divisible par 3.
Exemple 3
Exemple
Soit (un) la suite définie par u0=2 et pour tout entier naturel n>0 :
un+1=1+unun
Démontrons que pour tout n∈N, un=2n+12
Notons Pn la proposition « un=2n+12 »
Pour n=0, u0=2 et 2×0+12=2
Donc la proposition P0 est vraie.
Supposons la proposition Pn vraie pour un entier n, c’est-à-dire que pour un entier n, un=2n+12
On montre maintenant que la proposition est vraie au rang n+1, c’est-à-dire que un+1=2(n+1)+12
Par définition de la suite un, on a un+1=1+unun et d’après l’hypothèse de récurrence cela donne : un+1=1+2n+122n+12
En réduisant au même dénominateur et en simplifiant par 2n+1, on obtient :
un+1=2n+1+22
ce qui est égal à un+1=2(n+1)+12
Par récurrence, pour tout entier naturel n, Pn est vraie, c’est-à-dire que pour tout entier naturel n :
un=2n+12
Télécharger en PDF
Cette fiche de cours fait appel aux contenus suivants