I. L'idée de la récurrence
Le raisonnement par récurrence est l'une des techniques de démonstration les plus puissantes en mathématiques. Elle permet de prouver qu'une propriété est vraie pour tous les entiers naturels — une infinité de cas — en ne vérifiant que deux choses finies.
.png)
Si P(0) est vraie et si P(n) implique P(n+1), alors P(n) est vraie pour tout entier \(n \geq 0\).
II. Le principe de récurrence
Pour démontrer qu'une propriété \(P(n)\) est vraie pour tout entier \(n \geq n_0\), on procède en deux étapes :
- Initialisation : montrer que \(P(n_0)\) est vraie.
- Hérédité : montrer que pour tout entier \(n \geq n_0\), si \(P(n)\) est vraie (hypothèse de récurrence), alors \(P(n+1)\) est aussi vraie.
Conclusion : par le principe de récurrence, \(P(n)\) est vraie pour tout entier \(n \geq n_0\). \(\square\)
Sans initialisation : l'hérédité seule ne prouve rien — "si demain il pleut, il pleuvra après-demain" ne dit pas s'il pleut aujourd'hui.
Sans hérédité : l'initialisation seule ne prouve qu'un seul cas. Montrer P(0) ne permet pas de conclure P(1), P(2), etc.
Ensemble, elles forment un raisonnement infini mais fini à décrire : on prouve P(0), puis P(0)→P(1), puis P(1)→P(2), etc. — chaque cas découle du précédent de façon automatique.
III. Modèle de rédaction
1. Propriété à démontrer : "Pour tout entier \(n \geq n_0\), \(P(n)\) : [énoncer clairement la propriété]."
2. Initialisation : "Pour \(n = n_0\), [vérifier P(n₀) par calcul explicite]. La propriété est initialisée."
3. Hérédité : "Soit \(n \geq n_0\) un entier fixé. Supposons \(P(n)\) vraie (hypothèse de récurrence — HR). Montrons \(P(n+1)\). [Calcul utilisant explicitement HR.] Donc \(P(n+1)\) est vraie."
4. Conclusion : "Par le principe de récurrence, \(P(n)\) est vraie pour tout entier \(n \geq n_0\). \(\square\)"
IV. Exemples fondamentaux — sommes remarquables
Démontrer que pour tout entier \(n \geq 1\) : \(\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}\)
Propriété \(P(n)\) : \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\).
Initialisation (\(n=1\)) :
Membre gauche : \(1\). Membre droit : \(\dfrac{1\times2}{2}=1\). ✓ Propriété initialisée.
Hérédité : Soit \(n\geq1\) fixé. Supposons P(n) vraie. Montrons P(n+1) :
\(1+2+\cdots+n+(n+1) = \underbrace{\left(\sum_{k=1}^n k\right)}_{\text{HR}:\;n(n+1)/2}+(n+1) = \dfrac{n(n+1)}{2}+(n+1)\)
\(= (n+1)\!\left(\dfrac{n}{2}+1\right) = \dfrac{(n+1)(n+2)}{2}\)
C'est bien \(\dfrac{(n+1)((n+1)+1)}{2}\) — P(n+1) est vraie. \(\square\)
Démontrer que pour tout \(n \geq 1\) : \(\displaystyle\sum_{k=1}^{n} k^2 = \dfrac{n(n+1)(2n+1)}{6}\)
Initialisation (\(n=1\)) :
Gauche : \(1^2=1\). Droite : \(\dfrac{1\times2\times3}{6}=1\). ✓
Hérédité :
\(\displaystyle\sum_{k=1}^{n+1}k^2 = \dfrac{n(n+1)(2n+1)}{6}+(n+1)^2 = (n+1)\!\left[\dfrac{n(2n+1)}{6}+(n+1)\right]\)
\(= (n+1)\cdot\dfrac{n(2n+1)+6(n+1)}{6} = (n+1)\cdot\dfrac{2n^2+7n+6}{6} = \dfrac{(n+1)(n+2)(2n+3)}{6}\)
qui est bien \(\dfrac{(n+1)((n+1)+1)(2(n+1)+1)}{6}\). \(\square\)
Démontrer que pour tout \(n \geq 0\) et tout réel \(q \neq 1\) : \(\displaystyle\sum_{k=0}^{n}q^k = \dfrac{1-q^{n+1}}{1-q}\)
Initialisation (\(n=0\)) :
Gauche : \(q^0=1\). Droite : \(\dfrac{1-q}{1-q}=1\). ✓
Hérédité :
\(\displaystyle\sum_{k=0}^{n+1}q^k = \dfrac{1-q^{n+1}}{1-q}+q^{n+1} = \dfrac{1-q^{n+1}+q^{n+1}(1-q)}{1-q} = \dfrac{1-q^{n+2}}{1-q}\)
qui est bien \(\dfrac{1-q^{(n+1)+1}}{1-q}\). \(\square\)
V. Récurrence et inégalités — l'inégalité de Bernoulli
La récurrence ne sert pas uniquement à prouver des formules de somme — elle permet aussi de démontrer des inégalités et des propriétés de divisibilité.
Démontrer que pour tout entier \(n \geq 1\) et tout réel \(x \geq -1\) : \((1+x)^n \geq 1+nx\)
Initialisation (\(n=1\)) :
\((1+x)^1 = 1+x = 1+1\cdot x\). ✓ (égalité)
Hérédité : Supposons \((1+x)^n \geq 1+nx\) pour un \(n\geq1\) fixé. Puisque \(1+x\geq0\) :
\((1+x)^{n+1}=(1+x)^n\cdot(1+x)\geq(1+nx)(1+x)\)
\(=1+x+nx+nx^2=1+(n+1)x+nx^2\geq1+(n+1)x\)
car \(nx^2\geq0\). Donc \((1+x)^{n+1}\geq1+(n+1)x\). \(\square\)
Démontrer que pour tout entier \(n \geq 0\) : \(3\mid(4^n-1)\).
Initialisation (\(n=0\)) :
\(4^0-1=0=3\times0\). Donc \(3\mid0\). ✓
Hérédité : Supposons \(3\mid(4^n-1)\), i.e. \(4^n-1=3k\) pour un entier \(k\).
\(4^{n+1}-1=4\cdot4^n-1=4(4^n-1)+3=4\cdot3k+3=3(4k+1)\)
Donc \(3\mid(4^{n+1}-1)\). \(\square\)
Méthode clé : écrire \(a^{n+1}-1 = a(a^n-1)+(a-1)\) pour faire apparaître l'hypothèse de récurrence.
VI. Récurrence forte
Dans la récurrence forte, l'hypothèse est plus puissante : au lieu de supposer uniquement \(P(n)\), on suppose que \(P(k)\) est vraie pour tout \(k\) avec \(n_0\leq k\leq n\), et on montre \(P(n+1)\).
Cette forme est utile quand \(P(n+1)\) dépend de plusieurs rangs précédents (pas seulement du rang \(n\)), comme dans les suites vérifiant \(u_{n+1}=f(u_n, u_{n-1})\). Il faut alors initialiser autant de cas de base que nécessaire.
La suite de Fibonacci est définie par \(F_0=0\), \(F_1=1\), \(F_{n+2}=F_{n+1}+F_n\).
Démontrons par récurrence forte que pour tout \(n\geq0\) : \(F_n\leq\left(\dfrac{5}{3}\right)^n\).
Initialisation (\(n=0\) et \(n=1\)) :
\(F_0=0\leq1=\left(\frac{5}{3}\right)^0\). ✓ \(F_1=1\leq\frac{5}{3}\). ✓
Hérédité (récurrence forte) : Supposons \(F_k\leq(5/3)^k\) pour tout \(k\leq n\), avec \(n\geq1\). Montrons pour \(n+1\) :
\(F_{n+1}=F_n+F_{n-1}\leq\left(\tfrac{5}{3}\right)^n+\left(\tfrac{5}{3}\right)^{n-1}=\left(\tfrac{5}{3}\right)^{n-1}\!\left(\tfrac{5}{3}+1\right)=\left(\tfrac{5}{3}\right)^{n-1}\cdot\tfrac{8}{3}\)
\(\leq\left(\tfrac{5}{3}\right)^{n-1}\cdot\left(\tfrac{5}{3}\right)^2=\left(\tfrac{5}{3}\right)^{n+1}\)
car \(\dfrac{8}{3}\leq\dfrac{25}{9}=\left(\dfrac{5}{3}\right)^2\). ✓ \(\square\)
VII. Erreurs classiques à éviter
Sans vérifier P(n₀), la preuve est invalide. L'hérédité seule ne prouve rien. Il existe des propriétés dont l'hérédité est vraie mais P(0) est fausse — et qui sont donc fausses pour tout n.
On part de \(P(n)\) pour arriver à \(P(n+1)\), jamais l'inverse. \(P(n+1)\) est la conclusion, pas une hypothèse.
Si \(P(n+1)\) dépend de \(P(n)\) et \(P(n-1)\), il faut initialiser deux cas de base (\(n_0\) et \(n_0+1\)) et utiliser la récurrence forte.
Toujours énoncer clairement \(P(n)\) avant de commencer. Marquer distinctement les étapes "Initialisation", "Hérédité", "Conclusion". Encadrer ou souligner l'hypothèse de récurrence (HR) pour montrer qu'elle est bien utilisée.
VIII. Application concrète ⭐
Amina ouvre un compte épargne à la Caisse Populaire du Burkina Faso avec un dépôt initial de 100 000 FCFA. Le taux d'intérêt annuel est de 5 %. On note \(C_n\) le capital après \(n\) années (\(C_0=100\,000\), \(C_{n+1}=1{,}05\cdot C_n\)).
- a) Démontrer par récurrence que \(C_n = 100\,000\times1{,}05^n\).
- b) Calculer le capital après 10 ans et après 20 ans.
- c) Au bout de combien d'années le capital dépasse-t-il 200 000 FCFA ? (Utiliser \(\log_{1,05}2\approx14{,}2\).)
a) Preuve par récurrence que \(C_n=100\,000\times1{,}05^n\) :
Initialisation (\(n=0\)) :
\(C_0=100\,000=100\,000\times1{,}05^0\). ✓
Hérédité : Supposons \(C_n=100\,000\times1{,}05^n\). Alors :
\(C_{n+1}=1{,}05\times C_n=1{,}05\times100\,000\times1{,}05^n=100\,000\times1{,}05^{n+1}\). \(\square\)
b) Applications numériques :
Après 10 ans : \(C_{10}=100\,000\times1{,}05^{10}\approx100\,000\times1{,}6289\approx\mathbf{162\,890}\) FCFA.
Après 20 ans : \(C_{20}=100\,000\times1{,}05^{20}\approx100\,000\times2{,}6533\approx\mathbf{265\,330}\) FCFA.
c) Quand C_n > 200 000 FCFA ?
\(100\,000\times1{,}05^n>200\,000\iff1{,}05^n>2\iff n>\log_{1{,}05}2\approx14{,}2\)
Le capital dépasse 200 000 FCFA à partir de \(n=\mathbf{15}\) années.
✏️ Exercices d'application
Démontrer par récurrence les formules suivantes pour tout \(n\geq1\) :
- a) \(\displaystyle\sum_{k=1}^{n}(2k-1)=n^2\) (somme des \(n\) premiers entiers impairs)
- b) \(\displaystyle\sum_{k=1}^{n}k^3=\left[\dfrac{n(n+1)}{2}\right]^2\)
Init. (n=1) : gauche = 1, droite = 1. ✓
Hérédité : \(\sum_{k=1}^{n+1}(2k-1)=n^2+2(n+1)-1=n^2+2n+1=(n+1)^2\). ✓ □
b) P(n) : \(\sum_{k=1}^n k^3=[n(n+1)/2]^2\).
Init. (n=1) : gauche = 1, droite = \([1\times2/2]^2=1\). ✓
Hérédité : \(\sum_{k=1}^{n+1}k^3=[n(n+1)/2]^2+(n+1)^3=(n+1)^2[n^2/4+(n+1)]\)
\(=(n+1)^2\cdot\frac{n^2+4n+4}{4}=(n+1)^2\cdot\frac{(n+2)^2}{4}=\left[\frac{(n+1)(n+2)}{2}\right]^2\). ✓ □
- a) Démontrer que pour tout \(n\geq1\) : \(2^n\geq n+1\).
- b) Démontrer que pour tout \(n\geq4\) : \(2^n\geq n^2\).
- c) En déduire sans récurrence supplémentaire : pour tout \(n\geq4\), \(2^n>n^2-1\).
Hérédité : \(2^{n+1}=2\cdot2^n\geq2(n+1)=2n+2\geq n+2=(n+1)+1\) (car \(n\geq0\)). ✓ □
b) Init. (n=4) : \(16\geq16\). ✓
Hérédité : \(2^{n+1}=2\cdot2^n\geq2n^2\). Il faut \(2n^2\geq(n+1)^2\), i.e. \(n^2-2n-1\geq0\).
Pour \(n\geq4\) : \((n-1)^2-2=(n^2-2n+1)-2=n^2-2n-1\geq9-2=7>0\). ✓ □
c) Pour \(n\geq4\) : \(2^n\geq n^2>n^2-1\). Immédiat par b). □
Démontrer par récurrence que pour tout entier \(n\geq0\) :
- a) \(6\mid n(n+1)(n+2)\) (produit de trois entiers consécutifs)
- b) \(7\mid(8^n-1)\)
Hérédité : \((n+1)(n+2)(n+3)=n(n+1)(n+2)+3(n+1)(n+2)\).
Par HR, \(6\mid n(n+1)(n+2)\). Et \((n+1)(n+2)\) est produit de deux consécutifs donc pair, d'où \(6\mid3(n+1)(n+2)\). Somme de deux multiples de 6 → divisible par 6. ✓ □
b) Init. (n=0) : \(8^0-1=0=7\times0\). ✓
Hérédité : \(8^{n+1}-1=8\cdot8^n-1=8(8^n-1)+7\). Par HR, \(7\mid8(8^n-1)\). Et \(7\mid7\). Donc \(7\mid(8^{n+1}-1)\). ✓ □
Une suite \((u_n)\) est définie par \(u_0=2\) et \(u_{n+1}=3u_n-4\) pour tout \(n\geq0\).
- a) Calculer \(u_1,u_2,u_3\). Émettre une conjecture.
- b) Démontrer cette conjecture par récurrence.
- c) Expliquer pourquoi 2 est le seul point fixe de \(f(x)=3x-4\) et ce que cela signifie pour la suite.
b) Init. (n=0) : \(u_0=2\). ✓
Hérédité : Si \(u_n=2\), alors \(u_{n+1}=3\times2-4=2\). ✓ □
c) Point fixe de \(f\) : \(3x-4=x\Rightarrow x=2\). La suite part de 2, et \(f(2)=2\), donc elle ne bouge jamais — constante égale à sa valeur initiale.
Une ONG à Djibo distribue des vivres selon un plan croissant : le premier jour elle atteint 3 familles, chaque jour suivant elle en atteint 2 de plus. Après \(n\) jours, le total de familles ayant reçu des vivres est \(S_n\).
- a) Calculer \(S_1,S_2,S_3,S_4\) en comptant le nombre de familles par jour.
- b) Conjecturer une formule pour \(S_n\) en fonction de \(n\).
- c) Démontrer cette formule par récurrence.
- d) Après combien de jours aura-t-on atteint au moins 500 familles au total ?
\(S_1=3\), \(S_2=3+5=8\), \(S_3=8+7=15\), \(S_4=15+9=24\).
b) Remarquer : \(3=1\times3\), \(8=2\times4\), \(15=3\times5\), \(24=4\times6\). Conjecture : \(S_n=n(n+2)\).
c) Init. (n=1) : \(S_1=3=1\times3=1\times(1+2)\). ✓
Hérédité : Le \((n+1)\)ème jour, l'ONG atteint \(3+2n\) familles.
\(S_{n+1}=S_n+(3+2n)=n(n+2)+(2n+3)=n^2+2n+2n+3=n^2+4n+3=(n+1)(n+3)=(n+1)((n+1)+2)\). ✓ □
d) \(n(n+2)\geq500\iff n^2+2n-500\geq0\). Discriminant : \(4+2000=2004\), \(\sqrt{2004}\approx44{,}7\). Solution positive : \(n\geq\frac{-2+44{,}7}{2}\approx21{,}4\). Donc à partir du 22ème jour.
À retenir
- Principe : pour prouver \(P(n)\) pour tout \(n\geq n_0\), montrer P(n₀) (initialisation) et P(n) ⟹ P(n+1) (hérédité).
- Structure : énoncer P(n) clairement, distinguer les 3 étapes, encadrer l'hypothèse de récurrence (HR).
- Sommes clés : \(\sum k=\frac{n(n+1)}{2}\) ; \(\sum k^2=\frac{n(n+1)(2n+1)}{6}\) ; \(\sum k^3=\left[\frac{n(n+1)}{2}\right]^2\) ; \(\sum q^k=\frac{1-q^{n+1}}{1-q}\).
- Inégalité de Bernoulli : \((1+x)^n\geq1+nx\) pour \(x\geq-1\), \(n\geq1\).
- Divisibilité : souvent écrire \(a^{n+1}-1=a(a^n-1)+(a-1)\) pour faire apparaître l'HR.
- Récurrence forte : utiliser quand P(n+1) dépend de plusieurs rangs antérieurs ; initialiser autant de cas de base que nécessaire.
- Application : intérêts composés, suites géométriques — la récurrence prouve rigoureusement leurs formules.