Une collection progressive de 20 exercices résolus sur le principe de récurrence mathématique, conçue pour comprendre de manière rigoureuse le fonctionnement des démonstrations par récurrence. Chaque exercice illustre clairement :
- comment vérifier correctement l'initialisation ;
- comment formuler l'hypothèse de récurrence ;
- comment utiliser l'hypothèse sans commettre d'erreurs logiques ;
- comment démontrer le passage du rang \(n\) au rang \(n+1\).
L'objectif n'est pas seulement de vérifier des formules, mais de comprendre la structure logique d'une démonstration par récurrence et d'apprendre à construire des raisonnements rigoureux pas à pas.
Exercice 1 — niveau ★☆☆☆☆
Démontrer par récurrence que :
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
Démonstration
Initialisation
Vérifions tout d'abord la propriété pour \(n=1\).
Le membre gauche vaut :
\[ 1 \]
Le membre droit vaut :
\[ \frac{1(1+1)}{2}=\frac{2}{2}=1 \]
Les deux membres coïncident. La propriété est donc vraie pour \(n=1\).
Hypothèse de récurrence
Supposons maintenant que la formule est vraie pour un certain entier naturel \(n\). Cette supposition s'appelle l'hypothèse de récurrence.
On suppose donc :
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
Il est fondamental de comprendre que l'on ne suppose pas la formule vraie pour tous les entiers naturels, mais uniquement pour une valeur arbitraire \(n\).
Hérédité
Nous devons montrer que, si la formule est vraie au rang \(n\), elle l'est aussi au rang \(n+1\).
Autrement dit, nous devons établir :
\[ 1+2+3+\dots+n+(n+1)=\frac{(n+1)(n+2)}{2} \]
Partons du membre gauche :
\[ 1+2+3+\dots+n+(n+1) \]
Nous faisons appel à l'hypothèse de récurrence, qui nous permet de remplacer la somme des \(n\) premiers entiers par l'expression déjà connue :
\[ \frac{n(n+1)}{2} \]
On obtient ainsi :
\[ 1+2+\dots+n+(n+1) = \frac{n(n+1)}{2}+(n+1) \]
Notre objectif est maintenant de transformer cette expression en la formule attendue :
\[ \frac{(n+1)(n+2)}{2} \]
Pour ce faire, on met en facteur \(n+1\) :
\[ \frac{n(n+1)}{2}+(n+1) = (n+1)\left(\frac{n}{2}+1\right) \]
En écrivant \(1\) sous la forme \(\frac{2}{2}\), on peut additionner les fractions :
\[ \frac{n}{2}+1 = \frac{n}{2}+\frac{2}{2} = \frac{n+2}{2} \]
En substituant, on obtient :
\[ (n+1)\left(\frac{n+2}{2}\right) = \frac{(n+1)(n+2)}{2} \]
Nous avons donc établi que :
\[ 1+2+\dots+n+(n+1) = \frac{(n+1)(n+2)}{2} \]
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique, on conclut que :
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
pour tout entier naturel \(n\geq1\).
Exercice 2 — niveau ★☆☆☆☆
Démontrer par récurrence que :
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Démonstration
Interprétation de la formule
Le membre gauche représente la somme des \(n\) premiers nombres impairs :
\[ 1,3,5,7,\dots \]
La formule affirme que cette somme est toujours égale au carré de \(n\).
Initialisation
Vérifions la formule pour \(n=1\).
Le membre gauche vaut :
\[ 1 \]
Le membre droit vaut :
\[ 1^2=1 \]
Les deux membres coïncident. La propriété est donc vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain entier naturel \(n\).
On suppose donc :
\[ 1+3+5+\dots+(2n-1)=n^2 \]
Hérédité
Nous devons montrer que l'on a aussi :
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
Il est important d'observer pourquoi le terme \(2n+1\) apparaît.
En effet :
\[ 2(n+1)-1=2n+2-1=2n+1 \]
Ainsi, \(2n+1\) est précisément le nombre impair suivant.
Partons du membre gauche :
\[ 1+3+5+\dots+(2n-1)+(2n+1) \]
On applique l'hypothèse de récurrence pour remplacer la partie initiale de la somme :
\[ n^2+(2n+1) \]
On obtient :
\[ n^2+2n+1 \]
On reconnaît un carré parfait :
\[ n^2+2n+1=(n+1)^2 \]
Nous avons ainsi établi que :
\[ 1+3+5+\dots+(2n-1)+(2n+1)=(n+1)^2 \]
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été vérifiée.
Par le principe de récurrence mathématique :
\[ 1+3+5+\dots+(2n-1)=n^2 \]
pour tout \(n\geq1\).
Exercice 3 — niveau ★★☆☆☆
Démontrer par récurrence que :
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
Démonstration
Interprétation de la formule
Le membre gauche représente la somme des premières puissances de \(2\) :
\[ 2^0+2^1+2^2+\dots+2^n \]
La formule affirme que cette somme peut s'écrire sous forme close comme :
\[ 2^{n+1}-1 \]
Initialisation
Vérifions la propriété pour \(n=0\).
Le membre gauche vaut :
\[ 2^0=1 \]
Le membre droit vaut :
\[ 2^{0+1}-1=2^1-1=2-1=1 \]
Les deux membres coïncident. La propriété est donc vraie pour \(n=0\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain entier naturel \(n\).
On suppose donc :
\[ 1+2+4+\dots+2^n=2^{n+1}-1 \]
Hérédité
Nous devons montrer que l'on a aussi :
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
Partons du membre gauche :
\[ 1+2+4+\dots+2^n+2^{n+1} \]
On applique l'hypothèse de récurrence pour remplacer la somme initiale :
\[ (2^{n+1}-1)+2^{n+1} \]
On regroupe les termes semblables :
\[ 2^{n+1}+2^{n+1}-1 \]
Puisque :
\[ 2^{n+1}+2^{n+1}=2\cdot2^{n+1} \]
on obtient :
\[ 2\cdot2^{n+1}-1 \]
En appliquant les propriétés des puissances :
\[ 2\cdot2^{n+1}=2^{n+2} \]
il vient :
\[ 2^{n+2}-1 \]
Nous avons donc établi que :
\[ 1+2+4+\dots+2^n+2^{n+1}=2^{n+2}-1 \]
Conclusion
La propriété est vraie pour \(n=0\) et l'hérédité a été vérifiée.
Par le principe de récurrence mathématique :
\[ 1+2+4+8+\dots+2^n=2^{n+1}-1 \]
pour tout \(n\geq0\).
Exercice 4 — niveau ★★☆☆☆
Démontrer par récurrence que :
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
Démonstration
Signification de la formule
La formule fournit une expression close pour la somme des carrés des \(n\) premiers entiers naturels.
Plutôt que d'additionner chaque terme séparément :
\[ 1^2+2^2+3^2+\dots+n^2 \]
on peut calculer directement :
\[ \frac{n(n+1)(2n+1)}{6} \]
Initialisation
Vérifions la propriété pour \(n=1\).
Le membre gauche vaut :
\[ 1^2=1 \]
Le membre droit vaut :
\[ \frac{1(1+1)(2\cdot1+1)}{6} \]
En simplifiant :
\[ \frac{1\cdot2\cdot3}{6}=\frac{6}{6}=1 \]
La propriété est donc vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain entier naturel \(n\).
On suppose donc :
\[ 1^2+2^2+3^2+\dots+n^2 = \frac{n(n+1)(2n+1)}{6} \]
Hérédité
Nous devons montrer que l'on a aussi :
\[ 1^2+2^2+\dots+n^2+(n+1)^2 = \frac{(n+1)(n+2)(2n+3)}{6} \]
Partons du membre gauche :
\[ 1^2+2^2+\dots+n^2+(n+1)^2 \]
On applique l'hypothèse de récurrence :
\[ \frac{n(n+1)(2n+1)}{6}+(n+1)^2 \]
Pour additionner les termes, on ramène tout au dénominateur \(6\) :
\[ \frac{n(n+1)(2n+1)}{6}+\frac{6(n+1)^2}{6} \]
On obtient :
\[ \frac{n(n+1)(2n+1)+6(n+1)^2}{6} \]
On remarque que les deux termes du numérateur ont \(n+1\) en facteur commun. On le met en évidence :
\[ \frac{(n+1)\left[n(2n+1)+6(n+1)\right]}{6} \]
On développe maintenant l'expression entre crochets :
\[ n(2n+1)+6(n+1) \]
En développant :
\[ 2n^2+n+6n+6 \]
On regroupe les termes semblables :
\[ 2n^2+7n+6 \]
Il reste à factoriser ce trinôme.
On cherche deux nombres dont le produit est :
\[ 2\cdot6=12 \]
et dont la somme est :
\[ 7 \]
Ces nombres sont \(3\) et \(4\). On obtient donc :
\[ 2n^2+7n+6=(n+2)(2n+3) \]
En substituant :
\[ \frac{(n+1)(n+2)(2n+3)}{6} \]
ce qui est exactement la formule à démontrer.
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été établie.
Par le principe de récurrence mathématique :
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6} \]
pour tout \(n\geq1\).
Exercice 5 — niveau ★★☆☆☆
Démontrer par récurrence que :
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
Démonstration
Signification de la formule
La formule affirme que la somme des cubes des \(n\) premiers entiers naturels est égale au carré de la somme des \(n\) premiers entiers naturels.
En effet :
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2} \]
et donc le membre droit :
\[ \left(\frac{n(n+1)}{2}\right)^2 \]
est précisément le carré de cette quantité.
Initialisation
Vérifions la propriété pour \(n=1\).
Le membre gauche vaut :
\[ 1^3=1 \]
Le membre droit vaut :
\[ \left(\frac{1(1+1)}{2}\right)^2 = \left(\frac{2}{2}\right)^2 = 1^2 = 1 \]
Les deux membres coïncident. La propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain entier naturel \(n\).
On suppose donc :
\[ 1^3+2^3+3^3+\dots+n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
C'est la seule information dont nous disposons dans l'étape d'hérédité : nous ne pouvons pas supposer directement la formule au rang \(n+1\), car c'est précisément ce que nous devons démontrer.
Hérédité
Nous devons montrer que :
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
Partons du membre gauche :
\[ 1^3+2^3+3^3+\dots+n^3+(n+1)^3 \]
On applique l'hypothèse de récurrence à la somme des \(n\) premiers cubes :
\[ \left(\frac{n(n+1)}{2}\right)^2+(n+1)^3 \]
On développe le premier terme pour mieux identifier les facteurs communs :
\[ \left(\frac{n(n+1)}{2}\right)^2 = \frac{n^2(n+1)^2}{4} \]
On obtient donc :
\[ \frac{n^2(n+1)^2}{4}+(n+1)^3 \]
Les deux termes ont \((n+1)^2\) en facteur. On le met en évidence :
\[ (n+1)^2\left(\frac{n^2}{4}+n+1\right) \]
Il s'agit maintenant de transformer l'expression entre parenthèses en un carré parfait. On ramène tout au dénominateur \(4\) :
\[ \frac{n^2}{4}+n+1 = \frac{n^2}{4}+\frac{4n}{4}+\frac{4}{4} \]
soit :
\[ \frac{n^2}{4}+n+1 = \frac{n^2+4n+4}{4} \]
Le numérateur est un carré parfait :
\[ n^2+4n+4=(n+2)^2 \]
Donc :
\[ \frac{n^2}{4}+n+1 = \frac{(n+2)^2}{4} \]
En substituant dans notre expression :
\[ (n+1)^2\cdot\frac{(n+2)^2}{4} \]
On écrit le produit comme un carré :
\[ \frac{(n+1)^2(n+2)^2}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^2 \]
Nous avons bien obtenu la formule requise au rang \(n+1\).
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 1^3+2^3+3^3+\dots+n^3=\left(\frac{n(n+1)}{2}\right)^2 \]
pour tout \(n\geq1\).
Exercice 6 — niveau ★★☆☆☆
Démontrer par récurrence que \(5^n-1\) est divisible par \(4\), pour tout \(n\geq1\).
Démonstration
Signification de la propriété
Dire que \(5^n-1\) est divisible par \(4\) signifie qu'il existe un entier \(k\) tel que :
\[ 5^n-1=4k \]
Dans une démonstration par récurrence portant sur la divisibilité, l'hypothèse de récurrence se traduit presque toujours précisément sous cette forme.
Initialisation
Vérifions la propriété pour \(n=1\).
On calcule :
\[ 5^1-1=5-1=4 \]
Comme \(4\) est divisible par \(4\), la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
Cela signifie que \(5^n-1\) est divisible par \(4\). Il existe donc un entier \(k\) tel que :
\[ 5^n-1=4k \]
Cette écriture est essentielle : elle nous permet d'exploiter concrètement l'hypothèse de récurrence dans les calculs.
Hérédité
Nous devons montrer que \(5^{n+1}-1\) est également divisible par \(4\).
Partons de l'expression :
\[ 5^{n+1}-1 \]
On écrit \(5^{n+1}\) sous la forme \(5\cdot5^n\) :
\[ 5^{n+1}-1=5\cdot5^n-1 \]
On souhaite faire apparaître \(5^n-1\), qui est précisément l'expression figurant dans l'hypothèse de récurrence.
Pour cela, on réécrit :
\[ 5\cdot5^n-1=5(5^n-1)+4 \]
Vérifions mentalement ce passage :
\[ 5(5^n-1)+4=5\cdot5^n-5+4=5\cdot5^n-1 \]
On peut maintenant appliquer l'hypothèse de récurrence :
\[ 5^n-1=4k \]
donc :
\[ 5(5^n-1)+4=5\cdot4k+4 \]
On met \(4\) en facteur :
\[ 5\cdot4k+4=4(5k+1) \]
Comme \(5k+1\) est un entier, l'expression \(4(5k+1)\) est divisible par \(4\).
Donc \(5^{n+1}-1\) est divisible par \(4\).
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que si \(5^n-1\) est divisible par \(4\), alors \(5^{n+1}-1\) l'est aussi.
Par le principe de récurrence mathématique, \(5^n-1\) est divisible par \(4\) pour tout \(n\geq1\).
Exercice 7 — niveau ★★☆☆☆
Démontrer par récurrence que \(7^n-1\) est divisible par \(6\), pour tout \(n\geq1\).
Démonstration
Signification de la propriété
Dire que \(7^n-1\) est divisible par \(6\) signifie que \(7^n-1\) est un multiple de \(6\).
En symboles, nous devons montrer qu'il existe un entier \(k\) tel que :
\[ 7^n-1=6k \]
Initialisation
Vérifions la propriété pour \(n=1\).
On calcule :
\[ 7^1-1=7-1=6 \]
Comme \(6\) est divisible par \(6\), la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
Cela signifie que \(7^n-1\) est divisible par \(6\). Il existe donc un entier \(k\) tel que :
\[ 7^n-1=6k \]
L'objectif de l'étape d'hérédité sera de faire apparaître l'expression \(7^n-1\), afin de pouvoir effectuer la substitution grâce à l'hypothèse de récurrence.
Hérédité
Nous devons montrer que \(7^{n+1}-1\) est divisible par \(6\).
Partons de :
\[ 7^{n+1}-1 \]
On écrit \(7^{n+1}\) sous la forme \(7\cdot7^n\) :
\[ 7^{n+1}-1=7\cdot7^n-1 \]
On réécrit cette expression de façon à faire apparaître \(7^n-1\) :
\[ 7\cdot7^n-1=7(7^n-1)+6 \]
En effet :
\[ 7(7^n-1)+6=7\cdot7^n-7+6=7\cdot7^n-1 \]
En utilisant l'hypothèse de récurrence \(7^n-1=6k\), on obtient :
\[ 7(7^n-1)+6=7\cdot6k+6 \]
On met \(6\) en facteur :
\[ 7\cdot6k+6=6(7k+1) \]
Comme \(7k+1\) est un entier, \(6(7k+1)\) est divisible par \(6\).
Donc \(7^{n+1}-1\) est divisible par \(6\).
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que la divisibilité par \(6\) se transmet du rang \(n\) au rang \(n+1\).
Par le principe de récurrence mathématique, \(7^n-1\) est divisible par \(6\) pour tout \(n\geq1\).
Exercice 8 — niveau ★★★☆☆
Démontrer par récurrence que :
\[ 11^n-4^n \]
est divisible par \(7\), pour tout \(n\geq1\).
Démonstration
Signification de la propriété
Nous devons montrer que la différence \(11^n-4^n\) est toujours un multiple de \(7\).
Autrement dit, nous voulons établir qu'il existe un entier \(k\) tel que :
\[ 11^n-4^n=7k \]
Cet exercice est légèrement plus délicat que les précédents, car il met en jeu deux puissances distinctes. Dans l'étape d'hérédité, il faudra donc transformer l'expression avec soin, de façon à faire apparaître \(11^n-4^n\).
Initialisation
Vérifions la propriété pour \(n=1\).
On calcule :
\[ 11^1-4^1=11-4=7 \]
Comme \(7\) est divisible par \(7\), la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
On suppose donc que \(11^n-4^n\) est divisible par \(7\), c'est-à-dire qu'il existe un entier \(k\) tel que :
\[ 11^n-4^n=7k \]
C'est cette information que nous utiliserons à l'étape suivante.
Hérédité
Nous devons montrer que :
\[ 11^{n+1}-4^{n+1} \]
est divisible par \(7\).
On écrit les puissances au rang suivant :
\[ 11^{n+1}-4^{n+1}=11\cdot11^n-4\cdot4^n \]
On souhaite faire apparaître \(11^n-4^n\). Pour y parvenir, on ajoute et on soustrait le même terme \(11\cdot4^n\) :
\[ 11\cdot11^n-4\cdot4^n = 11\cdot11^n-11\cdot4^n+11\cdot4^n-4\cdot4^n \]
Ce passage ne modifie pas la valeur de l'expression, puisque l'on a ajouté et soustrait la même quantité.
On met maintenant \(11\) en facteur dans les deux premiers termes, et \(4^n\) dans les deux derniers :
\[ 11(11^n-4^n)+(11-4)4^n \]
Comme \(11-4=7\), on obtient :
\[ 11(11^n-4^n)+7\cdot4^n \]
On applique maintenant l'hypothèse de récurrence :
\[ 11^n-4^n=7k \]
En substituant :
\[ 11(11^n-4^n)+7\cdot4^n = 11\cdot7k+7\cdot4^n \]
On met \(7\) en facteur :
\[ 11\cdot7k+7\cdot4^n = 7(11k+4^n) \]
Comme \(11k+4^n\) est un entier, l'expression est divisible par \(7\).
Donc :
\[ 7\mid(11^{n+1}-4^{n+1}) \]
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été établie.
Par le principe de récurrence mathématique, \(11^n-4^n\) est divisible par \(7\) pour tout \(n\geq1\).
Exercice 9 — niveau ★★★☆☆
Démontrer par récurrence que :
\[ 2^n \geq n+1 \]
pour tout \(n\geq0\).
Démonstration
Signification de la propriété
L'inégalité affirme que la puissance \(2^n\) croît au moins aussi vite que l'expression linéaire \(n+1\).
Dans une démonstration par récurrence portant sur des inégalités, le point délicat consiste à utiliser l'hypothèse de récurrence sans inverser le sens de l'inégalité.
Initialisation
Vérifions la propriété pour \(n=0\).
Le membre gauche vaut :
\[ 2^0=1 \]
Le membre droit vaut :
\[ 0+1=1 \]
Donc :
\[ 2^0\geq0+1 \]
La propriété est vraie pour \(n=0\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq0\).
On suppose donc :
\[ 2^n\geq n+1 \]
Cette hypothèse nous dit que l'on peut remplacer \(2^n\) par une quantité supérieure ou égale à \(n+1\).
Hérédité
Nous devons montrer que :
\[ 2^{n+1}\geq n+2 \]
Partons du membre gauche :
\[ 2^{n+1} \]
On l'écrit sous la forme :
\[ 2^{n+1}=2\cdot2^n \]
Puisque l'hypothèse de récurrence donne \(2^n\geq n+1\), en multipliant les deux membres par \(2\), qui est positif, le sens de l'inégalité est préservé :
\[ 2\cdot2^n\geq2(n+1) \]
Donc :
\[ 2^{n+1}\geq2n+2 \]
Il reste à comparer \(2n+2\) avec \(n+2\), puisque l'objectif est d'obtenir \(n+2\).
Comme \(n\geq0\), on a :
\[ 2n+2\geq n+2 \]
En effet, la différence entre les deux membres est :
\[ (2n+2)-(n+2)=n\geq0 \]
En combinant les deux inégalités :
\[ 2^{n+1}\geq2n+2\geq n+2 \]
donc :
\[ 2^{n+1}\geq n+2 \]
Conclusion
La propriété est vraie pour \(n=0\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 2^n\geq n+1 \]
pour tout \(n\geq0\).
Exercice 10 — niveau ★★★☆☆
Démontrer par récurrence que :
\[ 3^n>n \]
pour tout \(n\geq1\).
Démonstration
Signification de la propriété
L'inégalité affirme que la puissance \(3^n\) est toujours strictement supérieure à l'exposant \(n\), pour tout \(n\geq1\).
Bien que la propriété soit intuitivement évidente, les puissances de \(3\) croissant très rapidement, l'objectif est de l'établir de façon rigoureuse par récurrence.
Initialisation
Vérifions la propriété pour \(n=1\).
Le membre gauche vaut :
\[ 3^1=3 \]
Le membre droit vaut :
\[ 1 \]
Comme :
\[ 3>1 \]
la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
On suppose donc :
\[ 3^n>n \]
C'est l'information dont nous nous servirons pour établir l'inégalité au rang suivant.
Hérédité
Nous devons montrer que :
\[ 3^{n+1}>n+1 \]
Partons de :
\[ 3^{n+1} \]
On écrit :
\[ 3^{n+1}=3\cdot3^n \]
En utilisant l'hypothèse de récurrence \(3^n>n\) et en multipliant par \(3>0\), on obtient :
\[ 3\cdot3^n>3n \]
Donc :
\[ 3^{n+1}>3n \]
Il reste à comparer \(3n\) avec \(n+1\).
Pour \(n\geq1\), on a :
\[ 3n>n+1 \]
En effet :
\[ 3n-(n+1)=2n-1 \]
et, si \(n\geq1\), alors :
\[ 2n-1\geq1>0 \]
Donc :
\[ 3n>n+1 \]
En combinant :
\[ 3^{n+1}>3n>n+1 \]
donc :
\[ 3^{n+1}>n+1 \]
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été établie.
Par le principe de récurrence mathématique :
\[ 3^n>n \]
pour tout \(n\geq1\).
Exercice 11 — niveau ★★★★☆
Démontrer par récurrence que :
\[ 2^n < n! \]
pour tout \(n\geq4\).
Démonstration
Signification de la propriété
L'inégalité compare une puissance et une factorielle.
La factorielle \(n!\) est le produit :
\[ n!=1\cdot2\cdot3\cdot\dots\cdot n \]
La propriété affirme qu'à partir de \(n=4\), la factorielle est toujours strictement supérieure à \(2^n\).
Initialisation
Vérifions la propriété pour \(n=4\).
Le membre gauche vaut :
\[ 2^4=16 \]
Le membre droit vaut :
\[ 4!=1\cdot2\cdot3\cdot4=24 \]
Comme :
\[ 16<24 \]
la propriété est vraie pour \(n=4\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq4\).
On suppose donc :
\[ 2^n < n! \]
Cette hypothèse nous permet de comparer \(2^n\) avec \(n!\). À l'étape suivante, nous devrons comparer \(2^{n+1}\) avec \((n+1)!\).
Hérédité
Nous devons montrer que :
\[ 2^{n+1}<(n+1)! \]
Partons du membre gauche :
\[ 2^{n+1} \]
On l'écrit sous la forme :
\[ 2^{n+1}=2\cdot2^n \]
L'hypothèse de récurrence donne :
\[ 2^n < n! \]
En multipliant les deux membres par \(2>0\), on obtient :
\[ 2\cdot2^n<2\cdot n! \]
Donc :
\[ 2^{n+1}<2\cdot n! \]
Il reste à relier \(2\cdot n!\) à \((n+1)!\). On rappelle que :
\[ (n+1)!=(n+1)\cdot n! \]
Puisque \(n\geq4\), on a :
\[ n+1\geq5 \]
donc :
\[ 2 < n+1 \]
En multipliant par \(n!>0\), on obtient :
\[ 2\cdot n!<(n+1)\cdot n! \]
c'est-à-dire :
\[ 2\cdot n!<(n+1)! \]
En combinant les deux inégalités :
\[ 2^{n+1}<2\cdot n!<(n+1)! \]
donc :
\[ 2^{n+1}<(n+1)! \]
Conclusion
La propriété est vraie pour \(n=4\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 2^n < n! \]
pour tout \(n\geq4\).
Exercice 12 — niveau ★★★★☆
Démontrer par récurrence que :
\[ 4^n\geq3n+1 \]
pour tout \(n\geq0\).
Démonstration
Signification de la propriété
La propriété compare une croissance exponentielle, représentée par \(4^n\), et une croissance linéaire, représentée par \(3n+1\).
La récurrence nous permet d'établir que cette inégalité est valable pour tout entier naturel \(n\geq0\), sans avoir à vérifier chaque cas séparément.
Initialisation
Vérifions la propriété pour \(n=0\).
Le membre gauche vaut :
\[ 4^0=1 \]
Le membre droit vaut :
\[ 3\cdot0+1=1 \]
Les deux membres sont égaux, donc :
\[ 4^0\geq3\cdot0+1 \]
La propriété est vraie pour \(n=0\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq0\).
On suppose donc :
\[ 4^n\geq3n+1 \]
Nous devons utiliser cette information pour établir l'inégalité au rang suivant.
Hérédité
Nous devons montrer que :
\[ 4^{n+1}\geq3(n+1)+1 \]
Puisque :
\[ 4^{n+1}=4\cdot4^n \]
on peut appliquer l'hypothèse de récurrence. Comme \(4>0\), multiplier par \(4\) conserve le sens de l'inégalité :
\[ 4\cdot4^n\geq4(3n+1) \]
Donc :
\[ 4^{n+1}\geq12n+4 \]
Nous cherchons à obtenir :
\[ 3(n+1)+1 \]
En développant :
\[ 3(n+1)+1=3n+3+1=3n+4 \]
Il s'agit donc de comparer \(12n+4\) avec \(3n+4\).
Comme \(n\geq0\), on a :
\[ 12n+4\geq3n+4 \]
En effet :
\[ (12n+4)-(3n+4)=9n\geq0 \]
Donc :
\[ 12n+4\geq3n+4=3(n+1)+1 \]
En combinant :
\[ 4^{n+1}\geq12n+4\geq3(n+1)+1 \]
ainsi :
\[ 4^{n+1}\geq3(n+1)+1 \]
Conclusion
La propriété est vraie pour \(n=0\) et nous avons montré que sa validité au rang \(n\) implique sa validité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 4^n\geq3n+1 \]
pour tout \(n\geq0\).
Exercice 13 — niveau ★★★★☆
Démontrer par récurrence que :
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
pour tout \(n\geq0\).
Démonstration
Signification de la formule
Le membre gauche est la somme des premières puissances de \(3\), à partir de \(3^0=1\) :
\[ 1+3+3^2+\dots+3^n \]
La formule affirme que cette somme peut se calculer directement par :
\[ \frac{3^{n+1}-1}{2} \]
Initialisation
Vérifions la propriété pour \(n=0\).
Le membre gauche vaut :
\[ 1 \]
Le membre droit vaut :
\[ \frac{3^{0+1}-1}{2} = \frac{3-1}{2} = \frac{2}{2} = 1 \]
Les deux membres coïncident. La propriété est vraie pour \(n=0\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain \(n\geq0\).
On suppose donc :
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
Hérédité
Nous devons montrer que :
\[ 1+3+3^2+\dots+3^n+3^{n+1} = \frac{3^{n+2}-1}{2} \]
Partons du membre gauche :
\[ 1+3+3^2+\dots+3^n+3^{n+1} \]
On applique l'hypothèse de récurrence à la partie initiale de la somme :
\[ \frac{3^{n+1}-1}{2}+3^{n+1} \]
On ramène tout au même dénominateur :
\[ \frac{3^{n+1}-1}{2}+\frac{2\cdot3^{n+1}}{2} \]
On additionne les numérateurs :
\[ \frac{3^{n+1}-1+2\cdot3^{n+1}}{2} \]
On regroupe les termes en \(3^{n+1}\) :
\[ 3^{n+1}+2\cdot3^{n+1}=3\cdot3^{n+1} \]
Donc :
\[ \frac{3\cdot3^{n+1}-1}{2} \]
Par la règle des puissances :
\[ 3\cdot3^{n+1}=3^{n+2} \]
On obtient ainsi :
\[ \frac{3^{n+2}-1}{2} \]
ce qui est exactement la formule au rang \(n+1\).
Conclusion
La propriété est vraie pour \(n=0\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 1+3+3^2+\dots+3^n=\frac{3^{n+1}-1}{2} \]
pour tout \(n\geq0\).
Exercice 14 — niveau ★★★★☆
Démontrer par récurrence que :
\[ 8^n-1 \]
est divisible par \(7\), pour tout \(n\geq1\).
Démonstration
Signification de la propriété
Nous devons montrer que \(8^n-1\) est toujours un multiple de \(7\).
Autrement dit, nous devons établir qu'il existe un entier \(k\) tel que :
\[ 8^n-1=7k \]
Initialisation
Vérifions la propriété pour \(n=1\).
On calcule :
\[ 8^1-1=8-1=7 \]
Comme \(7\) est divisible par \(7\), la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
Il existe donc un entier \(k\) tel que :
\[ 8^n-1=7k \]
Dans l'étape d'hérédité, il faudra faire apparaître l'expression \(8^n-1\) afin de pouvoir appliquer l'hypothèse de récurrence.
Hérédité
Nous devons montrer que \(8^{n+1}-1\) est divisible par \(7\).
Partons de :
\[ 8^{n+1}-1 \]
On écrit \(8^{n+1}\) sous la forme :
\[ 8^{n+1}=8\cdot8^n \]
Donc :
\[ 8^{n+1}-1=8\cdot8^n-1 \]
On réécrit l'expression de façon à faire apparaître \(8^n-1\) :
\[ 8\cdot8^n-1=8(8^n-1)+7 \]
En effet :
\[ 8(8^n-1)+7=8\cdot8^n-8+7=8\cdot8^n-1 \]
En utilisant l'hypothèse de récurrence \(8^n-1=7k\), on obtient :
\[ 8(8^n-1)+7=8\cdot7k+7 \]
On met \(7\) en facteur :
\[ 8\cdot7k+7=7(8k+1) \]
Comme \(8k+1\) est un entier, l'expression \(7(8k+1)\) est divisible par \(7\).
Donc \(8^{n+1}-1\) est divisible par \(7\).
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que la divisibilité se transmet du rang \(n\) au rang \(n+1\).
Par le principe de récurrence mathématique, \(8^n-1\) est divisible par \(7\) pour tout \(n\geq1\).
Exercice 15 — niveau ★★★★☆
Démontrer par récurrence que :
\[ 9^n-1 \]
est divisible par \(8\), pour tout \(n\geq1\).
Démonstration
Signification de la propriété
Nous devons montrer que \(9^n-1\) est toujours un multiple de \(8\).
En symboles, nous voulons établir qu'il existe un entier \(k\) tel que :
\[ 9^n-1=8k \]
Initialisation
Vérifions la propriété pour \(n=1\).
On calcule :
\[ 9^1-1=9-1=8 \]
Comme \(8\) est divisible par \(8\), la propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq1\).
Il existe donc un entier \(k\) tel que :
\[ 9^n-1=8k \]
Hérédité
Nous devons montrer que \(9^{n+1}-1\) est divisible par \(8\).
Partons de :
\[ 9^{n+1}-1 \]
On écrit :
\[ 9^{n+1}=9\cdot9^n \]
donc :
\[ 9^{n+1}-1=9\cdot9^n-1 \]
On souhaite faire apparaître \(9^n-1\), qui est l'expression contrôlée par l'hypothèse de récurrence.
On réécrit :
\[ 9\cdot9^n-1=9(9^n-1)+8 \]
En effet :
\[ 9(9^n-1)+8=9\cdot9^n-9+8=9\cdot9^n-1 \]
En utilisant l'hypothèse de récurrence :
\[ 9^n-1=8k \]
on obtient :
\[ 9(9^n-1)+8=9\cdot8k+8 \]
On met \(8\) en facteur :
\[ 9\cdot8k+8=8(9k+1) \]
Comme \(9k+1\) est un entier, l'expression est divisible par \(8\).
Donc \(9^{n+1}-1\) est divisible par \(8\).
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été établie.
Par le principe de récurrence mathématique, \(9^n-1\) est divisible par \(8\) pour tout \(n\geq1\).
Exercice 16 — niveau ★★★★★
Démontrer par récurrence que :
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
pour tout \(n\geq1\).
Démonstration
Signification de la formule
Le membre gauche est une somme dont les termes sont de la forme :
\[ k\cdot k! \]
La formule affirme que cette somme se simplifie de façon remarquablement compacte :
\[ (n+1)!-1 \]
Le point clé de cet exercice est de reconnaître comment le terme suivant \((n+1)(n+1)!\) se combine avec \((n+1)!\).
Initialisation
Vérifions la propriété pour \(n=1\).
Le membre gauche vaut :
\[ 1\cdot1!=1 \]
Le membre droit vaut :
\[ (1+1)!-1=2!-1=2-1=1 \]
Les deux membres coïncident. La propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain \(n\geq1\).
On suppose donc :
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!=(n+1)!-1 \]
Hérédité
Nous devons montrer que :
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)!=(n+2)!-1 \]
Partons du membre gauche :
\[ 1\cdot1!+2\cdot2!+\dots+n\cdot n!+(n+1)(n+1)! \]
On applique l'hypothèse de récurrence à la somme jusqu'au rang \(n\) :
\[ (n+1)!-1+(n+1)(n+1)! \]
On met en évidence le facteur commun \((n+1)!\) :
\[ (n+1)!+(n+1)(n+1)!-1 \]
Les deux premiers termes contiennent \((n+1)!\), donc :
\[ (n+1)!\left[1+(n+1)\right]-1 \]
On simplifie la parenthèse :
\[ 1+(n+1)=n+2 \]
donc :
\[ (n+1)!(n+2)-1 \]
Comme :
\[ (n+2)!=(n+2)(n+1)! \]
on obtient :
\[ (n+2)!-1 \]
ce qui est exactement la formule requise au rang \(n+1\).
Conclusion
La propriété est vraie pour \(n=1\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 1\cdot1!+2\cdot2!+3\cdot3!+\dots+n\cdot n!=(n+1)!-1 \]
pour tout \(n\geq1\).
Exercice 17 — niveau ★★★★★
Démontrer par récurrence que :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
pour tout \(n\geq0\).
Démonstration
Signification de la formule
Le membre gauche est une somme de puissances négatives de \(2\), c'est-à-dire une somme géométrique :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} \]
La formule affirme que cette somme est égale à :
\[ 2-\frac{1}{2^n} \]
Le terme \(\frac{1}{2^n}\) mesure l'écart entre la somme partielle et la valeur \(2\).
Initialisation
Vérifions la propriété pour \(n=0\).
Le membre gauche ne contient que le premier terme :
\[ 1 \]
Le membre droit vaut :
\[ 2-\frac{1}{2^0}=2-1=1 \]
Les deux membres coïncident. La propriété est vraie pour \(n=0\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain \(n\geq0\).
On suppose donc :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
Cette hypothèse décrit la somme jusqu'au terme \(\frac{1}{2^n}\). À l'étape suivante, il faudra ajouter le nouveau terme \(\frac{1}{2^{n+1}}\).
Hérédité
Nous devons montrer que :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
Partons du membre gauche :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
On applique l'hypothèse de récurrence à la somme jusqu'à \(\frac{1}{2^n}\) :
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
Il s'agit de simplifier les deux derniers termes :
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} \]
On observe que :
\[ \frac{1}{2^n}=\frac{2}{2^{n+1}} \]
car \(2^{n+1}=2\cdot2^n\).
Donc :
\[ -\frac{1}{2^n}+\frac{1}{2^{n+1}} = -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} \]
En additionnant les fractions :
\[ -\frac{2}{2^{n+1}}+\frac{1}{2^{n+1}} = -\frac{1}{2^{n+1}} \]
Par conséquent :
\[ 2-\frac{1}{2^n}+\frac{1}{2^{n+1}} = 2-\frac{1}{2^{n+1}} \]
Nous avons bien obtenu la formule requise au rang \(n+1\).
Conclusion
La propriété est vraie pour \(n=0\) et l'hérédité a été établie.
Par le principe de récurrence mathématique :
\[ 1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^n} = 2-\frac{1}{2^n} \]
pour tout \(n\geq0\).
Exercice 18 — niveau ★★★★★
Démontrer par récurrence que :
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
pour tout \(n\geq1\).
Démonstration
Signification de la formule
Le symbole :
\[ \sum_{k=1}^{n} k(k+1) \]
désigne la somme des termes de la forme \(k(k+1)\), pour \(k\) allant de \(1\) à \(n\).
Explicitement :
\[ \sum_{k=1}^{n} k(k+1) = 1\cdot2+2\cdot3+3\cdot4+\dots+n(n+1) \]
La formule affirme que cette somme peut s'écrire sous forme close comme :
\[ \frac{n(n+1)(n+2)}{3} \]
Initialisation
Vérifions la propriété pour \(n=1\).
Le membre gauche vaut :
\[ \sum_{k=1}^{1} k(k+1)=1(1+1)=2 \]
Le membre droit vaut :
\[ \frac{1(1+1)(1+2)}{3} = \frac{1\cdot2\cdot3}{3} = 2 \]
Les deux membres coïncident. La propriété est vraie pour \(n=1\).
Hypothèse de récurrence
Supposons que la formule est vraie pour un certain \(n\geq1\).
On suppose donc :
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
Cette hypothèse décrit la somme jusqu'au terme \(n(n+1)\). À l'étape suivante, nous devrons ajouter le terme correspondant à \(k=n+1\).
Hérédité
Nous devons montrer que :
\[ \sum_{k=1}^{n+1} k(k+1)=\frac{(n+1)(n+2)(n+3)}{3} \]
On écrit la somme jusqu'au rang \(n+1\) en séparant le dernier terme :
\[ \sum_{k=1}^{n+1} k(k+1) = \sum_{k=1}^{n} k(k+1)+(n+1)(n+2) \]
On applique l'hypothèse de récurrence :
\[ \frac{n(n+1)(n+2)}{3}+(n+1)(n+2) \]
Les deux termes ont \((n+1)(n+2)\) en facteur commun. On le met en évidence :
\[ (n+1)(n+2)\left(\frac{n}{3}+1\right) \]
On transforme la parenthèse :
\[ \frac{n}{3}+1=\frac{n}{3}+\frac{3}{3}=\frac{n+3}{3} \]
En substituant :
\[ (n+1)(n+2)\cdot\frac{n+3}{3} \]
soit :
\[ \frac{(n+1)(n+2)(n+3)}{3} \]
Nous avons bien obtenu la formule requise au rang \(n+1\).
Conclusion
La propriété est vraie pour \(n=1\) et l'hérédité a été établie.
Par le principe de récurrence mathématique :
\[ \sum_{k=1}^{n} k(k+1)=\frac{n(n+1)(n+2)}{3} \]
pour tout \(n\geq1\).
Exercice 19 — niveau ★★★★★
Démontrer par récurrence que :
\[ 2^n>n^2 \]
pour tout \(n\geq5\).
Démonstration
Signification de la propriété
L'inégalité compare une croissance exponentielle, \(2^n\), et une croissance polynomiale, \(n^2\).
La propriété n'est pas vraie pour toutes les petites valeurs de \(n\). Par exemple, pour \(n=2\) on a \(2^2=4\) et \(2^2=4\), de sorte que l'inégalité stricte n'est pas satisfaite.
C'est pourquoi la démonstration par récurrence débute à \(n=5\).
Initialisation
Vérifions la propriété pour \(n=5\).
Le membre gauche vaut :
\[ 2^5=32 \]
Le membre droit vaut :
\[ 5^2=25 \]
Comme :
\[ 32>25 \]
la propriété est vraie pour \(n=5\).
Hypothèse de récurrence
Supposons que la propriété est vraie pour un certain \(n\geq5\).
On suppose donc :
\[ 2^n>n^2 \]
Nous devons utiliser cette information pour établir l'inégalité au rang suivant.
Hérédité
Nous devons montrer que :
\[ 2^{n+1}>(n+1)^2 \]
Partons du membre gauche :
\[ 2^{n+1} \]
On écrit :
\[ 2^{n+1}=2\cdot2^n \]
L'hypothèse de récurrence donne :
\[ 2^n>n^2 \]
En multipliant par \(2>0\), on obtient :
\[ 2\cdot2^n>2n^2 \]
Donc :
\[ 2^{n+1}>2n^2 \]
Il reste à montrer que \(2n^2\) est supérieur à \((n+1)^2\). En effet, si :
\[ 2n^2>(n+1)^2 \]
alors, en combinant les deux inégalités, on obtiendra :
\[ 2^{n+1}>2n^2>(n+1)^2 \]
Vérifions donc que :
\[ 2n^2>(n+1)^2 \]
On passe tout au membre gauche :
\[ 2n^2-(n+1)^2 \]
On développe le carré :
\[ (n+1)^2=n^2+2n+1 \]
donc :
\[ 2n^2-(n+1)^2 = 2n^2-(n^2+2n+1) \]
soit :
\[ n^2-2n-1 \]
On réécrit cette expression sous une forme commode :
\[ n^2-2n-1=(n-1)^2-2 \]
Comme \(n\geq5\), on a \(n-1\geq4\), donc :
\[ (n-1)^2\geq4^2=16 \]
Par conséquent :
\[ (n-1)^2-2\geq16-2=14>0 \]
Donc :
\[ 2n^2-(n+1)^2>0 \]
et ainsi :
\[ 2n^2>(n+1)^2 \]
En combinant :
\[ 2^{n+1}>2n^2>(n+1)^2 \]
on obtient :
\[ 2^{n+1}>(n+1)^2 \]
Conclusion
La propriété est vraie pour \(n=5\) et nous avons montré que sa vérité au rang \(n\) entraîne sa vérité au rang \(n+1\).
Par le principe de récurrence mathématique :
\[ 2^n>n^2 \]
pour tout \(n\geq5\).
Exercice 20 — niveau ★★★★★
Démontrer par récurrence que tout entier naturel \(n\geq2\) est premier ou produit de nombres premiers.
Démonstration
Signification de la propriété
Cette propriété constitue une forme essentielle du théorème fondamental de l'arithmétique : tout entier naturel supérieur ou égal à \(2\) peut se décomposer en produit de facteurs premiers.
Dans cet exercice, nous utiliserons la récurrence forte. Contrairement à la récurrence ordinaire, la récurrence forte permet, pour démontrer la propriété au rang \(n\), de supposer qu'elle est vraie pour tous les entiers naturels compris entre \(2\) et \(n-1\).
Cette forme de récurrence est naturelle ici, car si un entier n'est pas premier, il s'écrit comme produit de deux entiers plus petits.
Initialisation
Vérifions la propriété pour \(n=2\).
L'entier \(2\) est premier.
La propriété est donc vraie pour \(n=2\).
Hypothèse de récurrence forte
Supposons que la propriété est vraie pour tout entier naturel \(m\) vérifiant :
\[ 2\leq m\leq n \]
Cela signifie que tout entier naturel compris entre \(2\) et \(n\) est premier ou produit de nombres premiers.
Hérédité
Nous devons montrer que la propriété est vraie pour \(n+1\).
Considérons donc l'entier \(n+1\).
Deux cas se présentent.
Premier cas : \(n+1\) est premier
Si \(n+1\) est premier, la propriété est immédiatement vraie.
En effet, la propriété exige que l'entier soit premier ou produit de premiers ; dans ce cas, il est directement premier.
Second cas : \(n+1\) n'est pas premier
Si \(n+1\) n'est pas premier, alors par définition il existe deux entiers naturels \(a\) et \(b\), tous deux strictement supérieurs à \(1\), tels que :
\[ n+1=ab \]
De plus, comme \(a>1\) et \(b>1\), les deux facteurs sont strictement inférieurs à \(n+1\).
Donc :
\[ 2\leq a\leq n \qquad \text{et} \qquad 2\leq b\leq n \]
On peut alors appliquer l'hypothèse de récurrence forte à la fois à \(a\) et à \(b\).
Par hypothèse, \(a\) est premier ou produit de nombres premiers.
De même, \(b\) est premier ou produit de nombres premiers.
Puisque :
\[ n+1=ab \]
et que \(a\) et \(b\) sont tous deux premiers ou produits de premiers, il s'ensuit que \(n+1\) est lui aussi un produit de nombres premiers.
Conclusion
Nous avons établi que, si la propriété est vraie pour tous les entiers de \(2\) à \(n\), elle l'est aussi pour \(n+1\).
Comme la propriété est vraie pour \(n=2\), par le principe de récurrence forte on conclut que tout entier naturel \(n\geq2\) est premier ou produit de nombres premiers.