Fiche de mathématiques

Ile mathématiques > maths T^ale > Suites

Raisonnement par récurrence

I- Introduction :

Le raisonnement par récurrence est utilisé pour montrer des résultats faisant intervenir une variable entière de l'ensemble $\mathbb{N}$ ou d'une partie de cet ensemble, comme par exemple $\mathbb{N}^{*}$ , $\mathbb{N}^{*}-\lbrace 1,2 \rbrace$ etc.
Cette démonstration s'effectue en trois étapes :

L'étape initialisation : Montrer que le résultat est vrai pour le tout premier rang (en général le premier rang est 0, mais il se peut que le premier rang soit 1, 2 ou autre, cela dépend du résultat à démontrer).
L'étape hérédité : Montrer que le résultat est héréditaire, c'est-à-dire montrer que le résultat peut être "transmis" d'un rang fixé quelconque $k$ au rang suivant $k+1$ .
La conclusion
Pour expliquer ce principe assez intuitivement, prenons les deux exemples suivants :

Exemple 1 : La file de dominos
Si l'on pousse le premier domino de la file (Initialisation).
Et si les dominos sont posés l'un après l'autre d'une manière à ce que la chute d'un domino entraîne la chute de son suivant (Hérédité).
Alors : Tous les dominos de la file tombent. (la conclusion)

Exemple 2 : L'échelle
Si on sait monter le premier barreau de l'echelle (Initialisation).
Et si l'on sait toujours passer d'un barreau au barreau qui le suit (Hérédité).
Alors : On peut monter l'échelle. (la conclusion)

II- Énoncé :

Raisonnement par récurrence

Soit $\mathcal{P}(n)$ une propriété définie sur $\mathbb{N}$ . Si :

La propriété est initialisée à partir du premier rang $n_0$ , c'est-à-dire :
$\mathcal{P}(n_0)\text{ est vraie}$ .
Et la propriété est héréditaire, c'est-à-dire :
$\text{ Pour un entier k fixé quelconque, }k\ge n_0\; :\; \mathcal{P}(k) \Longrightarrow\mathcal{P}(k+1)$ .

Alors la propriété $\mathcal{P}(n)$ est vraie pour tout $n\geq n_0$

On commence par énoncer la propriété à démontrer, en précisant pour quels entiers naturels cette propriété est définie, notamment le premier rang.
Il est fortement conseillé de toujours noter la propriété à démontrer $\mathcal{P}(n)$ , cela facilite grandement la rédaction et nous évite des ambiguités.

Un raisonnement par récurrence se rédige en trois étapes :
1-On vérifie l'initialisation, c'est-à-dire que la propriété est vraie au premier rang (qui est souvent 0 ou 1).

2-On prouve le caractère héréditaire de la propriété, on suppose que la propriété est vraie pour un entier $k$ fixé et on démontre que la propriété est encore vraie au rang $k+1$ .
Ici, on utilise toujours la propriété pour $k$ pour montrer qu'elle est vraie aussi pour $k+1$
Il est conseillé de mettre dans un coin le résultat au rang $k+1$ à démontrer pour éviter des calculs fastidieux inutiles.

3-On conclut en invoquant le principe de récurrence.

Pour ceux qui veulent aller plus loin (supérieur), cela peut s'écrire :

$\;{\blue [ \underbrace{P(0)}_{\text{initialisation}} \text{ et } \underbrace{(\forall n)\;(\;(n \in \N \text{ et }P(n)) \Rightarrow P(n+1)\;)}_{\text{hérédité}}\;]} \Rightarrow \red (\forall n)(n \in \N \Rightarrow P(n))$
Concrètement dans les exercices, c'est la partie en bleu qu'on démontre et on conclut par la partie en rouge.

III-Exemples :

Exemple 1 :

Exercice :

Montrer par récurrence que : $\text{ Pour tout }n\in\mathbb{N}\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$

Puisqu'il s'agit d'un premier exemple, on va détailler (peut-être trop) en expliquant chaque étape. Nous exposerons ensuite une deuxième rédaction plus légère pour montrer comment bien rédiger un raisonnement par récurrence.

Résolution étape par étape bien détaillée aux fins d'explication :
Il faut montrer par récurrence que pour tout $n\in\mathbb{N} \text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$
On pose pour cela : $\mathcal{P}(n)\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$
Et puisqu'il s'agit des entiers $n$ appartenant à $\mathbb{N}$ , le premier rang est $0$ car il est le premier élément dans l'ensemble $\mathbb{N}$

1-Initialisation : Pour $n=0\text{ : }\dfrac{0\times (0+1)}{2}=\dfrac{0\times 1}{2}=0$
Donc la proposition $\mathcal{P}(0)$ est vraie.

Remarques :
La somme $0+1+2+\cdots+n$ veut dire qu'on additionne les nombres de $0$ à $n$ . Donc pour le cas $n=0$ , on additionne les nombres de $0$ à $0$ , ce qui implique que la somme vaut $0$ et pas $0+1+2+\cdots+0$ .
On peut écrire les sommes en utilisant le symbole de la somme $\sum$ qu'on exposera après dans le paragraphe suivant.

On n'écrit pas $\mathcal{P}(0)=0$ car $\mathcal{P}(n)$ n'est pas un nombre qu'on calcule et on N'écrit PAS $\mathcal{P}(n)\color{red}=\color{black}0+1+2+\cdots+n=\dfrac{n(n+1)}{2}$ .
$\mathcal{P}(n)$ est plutôt une proposition ("une phrase" mathématique) qui se lit : " La somme $0+1+2+\cdots+n$ est égale à $\dfrac{n(n+1)}{2}$ "

2-Hérédité : Soit $k\in\mathbb{N}$ un entier naturel.
Supposons que $\mathcal{P}(k)\text{ : } 0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$ est vraie, et montrons que dans ce cas, $\mathcal{P}(k+1)$ est vraie.
Pour pouvoir démontrer une propriété mathématique, il faut tout d'abord la connaître. Dans notre cas, il faut, avant de commencer, trouver ce qu'est l'expression de $\mathcal{P}(k+1)$ .
En général, on remplace tout simplement $k$ dans l'expression de $\mathcal{P}(k)$ par $k+1$ pour trouver l'expression de $\mathcal{P}(k+1)$
$\mathcal{P}(k+1)\text{ : } 0+1+2+\cdots+\color{red}(k+1)\color{black}= \dfrac{\color{red}(k+1)\color{black}[\color{red}(k+1)\color{black}+1]}{2}$
On simplifie et on trouve : $\mathcal{P}(k+1)\text{ : } 0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$

On va montrer que $0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$ à partir de $\mathcal{P}(k)\text{ : } 0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$

Pour ne pas se perdre, on écrit dans un coin :
Hypothèse : $\mathcal{P}(k) :0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$
Résultat à prouver : $\mathcal{P}(k+1) :0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$
On sait que $0+1+2+\cdots+(k+1)=0+1+2+\cdots+k+(k+1)$ car elle est la somme de $0$ à $k+1$ et le nombre qui précède $k+1$ est $k$ .
Donc :
$0+1+2+\cdots+(k+1)=\underbrace{0+1+2+\cdots+k}_{=\frac{k(k+1)}{2} \text{ d'après la supposition}}+(k+1)=\dfrac{k(k+1)}{2} + (k+1)=\dfrac{k(k+1)+2(k+1)}{2} =\dfrac{(k+1)(k+2)}{2}$

Donc on a bien $0+1+2+\cdots+(k+1)=\dfrac{(k+1)(k+2)}{2}$ est donc $\mathcal{P}(k+1)$ est vraie
3- Conclusion :
On a vu que la propriété était vraie au rang 0 et qu'elle est héréditaire, donc elle est vraie au rang 1, donc au rang 2...et de proche en proche elle est donc toujours vraie

Par récurrence, on obtient : $\boxed{\text{ Pour tout }n\in\mathbb{N}\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}}$

Rédaction de la résolution :
Montrons par récurrence que pour tout $n\in\mathbb{N} \text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$
Notons pour cela : $\mathcal{P}(n)\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$
Initialisation : Pour $n=0 \text{ : }\dfrac{0(0+1)}{2}=0 \text{ , donc : } \mathcal{P}(0) \text{ est vraie }$
Hérédité : Soit $k$ un entier naturel et supposons que $\mathcal{P}(k)$ est vraie.

Hypothèse : $\mathcal{P}(k) :0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$
Résultat à prouver : $\mathcal{P}(k+1) :0+1+2+\cdots+k+(k+1)= \dfrac{(k+1)(k+2)}{2}$

On a :
$0+1+2+\cdots+(k+1)=0+1+2+\cdots+k+(k+1)=\dfrac{k(k+1)}{2} + (k+1)=\dfrac{k(k+1)+2(k+1)}{2} =\dfrac{(k+1)(k+2)}{2}$
On en déduit que $\mathcal{P}(k+1)$ est vraie.
On conclut par récurrence que : $\boxed{\text{ Pour tout }n\in\mathbb{N}\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}}$

Exemple 2 :

Exercice :

Montrer par récurrence que : $\text{ pour tout entier } n\geq 5 \text{ : }2^n\geq 6n$

Montrons par récurrence que pour tout $n\geq 5 \text{ : }2^n\geq 6n$
On pose : $\mathcal{P}(n)\text{ : }2^n\geq 6n$
Initialisation : Pour $n=5$ : $\left\lbrace\begin{matrix}2^5& = & 32\\ 6\times 5& = & 30\leq 32\end{matrix}\right.$
Donc $\mathcal{P}(5)$ est vraie.
Hérédité : Soit $k$ un entier naturel tel que $k\geq 5$ et supposons que $\mathcal{P}(k)$ est vraie.
Montrons que $\mathcal{P}(k+1)$ est vraie.

Hypothèse : $\mathcal{P}(k) :2^k \geq 6k$
Résultat à prouver : $\mathcal{P}(k+1) :2^{k+1} \geq 6(k+1)$

$2^{k+1}=2\times 2^k\geq 2\times 6k =12k=6k+6k= 6k+6k+6-6=6k+6+6k-6=6(k+1)+6(k-1)\text{ (En effet : on essaye de faire apparaître } 6(k+1)\text{ )}$
Or, puisque $k\geq 5 \text{ alors } k-1\geq 4 \text{ et } 6(k-1)\geq 24\geq 0$
On en déduit $6(k+1)+6(k-1)\geq 6(k+1)$ et il s'ensuit que $2^{k+1}\geq 6(k+1)$
$\mathcal{P}(k+1)$ est donc vraie.
On conclut par récurrence que : $\boxed{\text{ Pour tout }n\geq 5\text{ : } 2^n\geq 6n}$

Exemple 3 : Application aux suites

Prérequis : Les suites numériques

Exercice :

Soit une suite $(U_n)$ avec $n\in\mathbb{N}$ définie par : $\left\lbrace\begin{matrix} U_0 & = &7 \\ U_{n+1}& = & 2U_n+5 \end{matrix}\right$
$\text{Montrer que pour tout } n\in\mathbb{N} \text{ : } 7\le U_n$

Montrons par récurrence que $\text{ pour tout } n\in\mathbb{N} \text{ : } 7\leq U_n$ .
On pose $\mathcal{P}(n)\text{ : }7\leq U_n$
Initialisation : Pour $n=0$ on a : $U_0=7\geq 7$
La proposition $\mathcal{P}(0)$ est vraie.
Hérédité : Soit $k$ un entier naturel et supposons que $\mathcal{P}(k)$ est vraie.
Montrons que dans ce cas, $\mathcal{P}(k+1)$ l'est aussi.

Hypothèse : $\mathcal{P}(k) :7 \le U_k$
Résultat à prouver : $\mathcal{P}(k+1)\text{ : } 7\leq U_{k+1}$
On a $7 \le U_k$
Donc $19\le 2U_{k}+5$
Donc $19 \le U_{k+1}$
Or, puisque $7\le 19$ , on a : $7 \le U_{k+1}$
Cela veut dire que $\mathcal{P}(k+1)$ est vraie.
On conclut par récurrence que : $\boxed{\text{ Pour tout entier }n\text{ : } U_n\geq 7}$

IV- Supplément : les symboles somme $\color{orange}\sum$ et produit $\color{orange}\prod$ :

1- Symbole $\sum$

Le symbole mathématique $\sum$ permet d'exprimer plus simplement des sommes et donc des expressions mathématiques, par exemple, la somme $0+1+\cdots +10$ peut s'écrire :

$0+1+\cdots +10=\displaystyle \sum_{k=0}^{10} \color{black}k$
Ce terme se lit "somme pour $k$ allant de 0 à 10 de $k$ ".
Cela signifie que l'on fait prendre au nombre $k$ toutes les valeurs entières entre 0 et 10 et qu'on fait la somme des nombres $k$ :
On met la première valeur entière en bas du symbole, dans notre cas c'est 0.
On met la dernière valeur entière en haut du symbole sugma, ici c'est 10.
La lettre $k$ est muette, elle ne sert qu'à compter et n'intervient pas dans le résultat final, on peut la remplacer par n'importe quelle autre variable $i, j, \cdots$ (on évite l'utilisation des lettres déjà utilisées dans l'exercice) :

$\displaystyle \sum_{k=0}^{10} \color{black}k=\displaystyle \sum_{i=0}^{10} \color{black}i=\displaystyle \sum_{j=0}^{10} \color{black}j$
Prenons la somme du premier exemple du paragraphe précédent, on pouvait écrire :

$\displaystyle \sum_{k=0}^{n}k =0+1+2+\cdots+n$

$\displaystyle \sum_{k=0}^{n+1}k =0+1+2+\cdots+n+(n+1)$

Autres exemples :
1- $\displaystyle \sum_{k=1}^{3}\dfrac{1}{k}=\dfrac{1}{1}+\dfrac{1}{2}+\dfrac{1}{3}=\dfrac{6+3+2}{6}=\dfrac{11}{6}$
2- $\displaystyle \sum_{p=0}^{n}2p =(2\times 0)+(2\times 1)+(2\times 2)+(2\times3)+\cdots+[2\times(n-1)]+(2\times n) = 0+2+4+6+8+\cdots 2n$
3- $\displaystyle \sum_{j=0}^{n}2j+1 =(2\times 0+1)+(2\times 1+1)+(2\times 2+1)+(2\times 3+1)+\cdots+[2\times(n-1)+1]+(2\times n+1) = 1+3+5+7+\cdots 2n+1$

Remarque : Dans l'exemple 1-, on ne pouvait pas débuter par $k=0$ car le dénominateur ne peut pas être nul.

2- Symbole $\prod$

Comme son homologue $\sum$ pour les sommes, le symbole mathématique $\prod$ permet d'exprimer plus simplement des produits, par exemple, le produit $1\times2\times\cdots \times10$ peut s'écrire :

$1\times\cdots \times10=\displaystyle \prod_{k=1}^{10} \color{black}k$
Exemples :
$\displaystyle\prod_{k=0}^4 (2k+1)=1\times3\times5\times7\times9=945$
$\displaystyle\prod_{k=2}^n k^2=4\times 9\times \cdots\times n^2$
Remarquer que le produit présenté précédemment : $\displaystyle \prod_{k=1}^{10} \color{black}k=1\times\cdots \times10=10!$

3- Exercice d'application :

Énoncé :

Montrer que :
1- $\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$
2- $\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(n+1)!}$

Solution :
1-Montrons par récurrence que $\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$ .
Notons $\mathcal{P}(n)\text{ : } \displaystyle\sum_{k=0}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}$
Il est conseillé d'écrire les termes avec sigma sous forme d'addition : $\displaystyle\sum_{k=0}^{n}k^2=0^2+1^2+2^2+\cdots+n^2$
Initialisation : Pour $n=0$ , on a : $\left\lbrace\begin{matrix} \displaystyle\sum_{k=0}^{0}k^2 =0^2 = 0 \\ \\ \dfrac{0\times(0+1)(2\times 0+1)}{6}=0\end{matrix}\right$
Donc : $\displaystyle\sum_{k=0}^{0}k^2=\dfrac{0\times(0+1)(2\times 0+1)}{6}=0$ et $\mathcal{P}(0)$ est vraie.
Hérédité :Soit $p$ un entier de $\mathbb{N}$ , supposons que $\mathcal{P}(p)$ est vraie et montrons que $\mathcal{P}(p+1)$ est vraie (On évite l'utilisation de la lettre $k$ pour l'hérédité car déjà utilisée comme variable muette de la somme).

Hypothèse : $\mathcal{P}(p) :\displaystyle\sum_{k=0}^{p}k^2=\dfrac{p(p+1)(2p+1)}{6}$
Résultat à prouver : $\mathcal{P}(p+1) :\displaystyle\sum_{k=0}^{p+1}k^2=\dfrac{(p+1)(p+2)(2p+3)}{6}$
On a :

$\begin{array}{cl} \\ \displaystyle\sum_{k=0}^{p+1}k^2 &= 0^2+1^2+\cdots+p^2+(p+1)^2 \\ &=\left(\displaystyle\sum_{k=0}^{p}k^2\right)+(p+1)^2 \\\\ &= \dfrac{p(p+1)(2p+1)}{6} + (p+1)^2\\\\&= \dfrac{p(p+1)(2p+1)+6(p+1)^2}{6} \\\\ &=\dfrac{(p+1)[p(2p+1)+6(p+1)]}{6} \\\\&=\dfrac{(p+1)(2p^2+7p+6)}{6} \end{array}$

Or, on a : $(p+2)(2p+3)=2p^2+3p+4p+6=2p^2+7p+6$

Donc : $\displaystyle\sum_{k=0}^{p+1}k^2=\dfrac{(p+1)(2p^2+7p+6)}{6}=\dfrac{(p+1)(p+2)(2p+3)}{6}$
Cela veut dire que $\mathcal{P}(p+1)$ est vraie.

On conclut par récurrence que : $\boxed{\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}k^2=\dfrac{n(n+1)(2n+1)}{6}}$ .

2-Montrons par récurrence que $\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(n+1)!}$
On note $\mathcal{P}(n)\text{ : } \displaystyle\sum_{k=0}^{n}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(n+1)!}$
Écriture de la somme sous forme d'addition : $\displaystyle\sum_{k=0}^{n}\dfrac{k}{(k+1)!}=\dfrac{0}{(0+1)!}+\dfrac{1}{(1+1)!}+\dfrac{2}{(2+1)!}+\cdots + \dfrac{n}{(n+1)!}$
Initialisation : Pour $n=0$ , on calcule : $\left\lbrace\begin{matrix} \displaystyle\sum_{k=0}^{0}\dfrac{k}{(k+1)!} =\dfrac{0}{1!} =\dfrac{0}{1}= 0 \\ \\ 1-\dfrac{1}{(0+1)!}=1-\dfrac{1}{1!}=1-1=0\end{matrix}\right$
Donc : $\displaystyle\sum_{k=0}^{0}\dfrac{k}{(k+1)!} =1-\dfrac{1}{(0+1)!}=0$ et $\mathcal{P}(0)$ est vraie.
Hérédité :Soit $m$ un entier de $\mathbb{N}$ , supposons que $\mathcal{P}(m)$ est vraie et montrons que $\mathcal{P}(m+1)$ est vraie.

Hypothèse : $\mathcal{P}(m) :\displaystyle\sum_{k=0}^{m}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(m+1)!}$
Résultat à prouver : $\mathcal{P}(m+1) :\displaystyle\sum_{k=0}^{m+1}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(m+2)!}$
On a :

$\begin{array}{cl} \\ \displaystyle\sum_{k=0}^{m+1}\dfrac{k}{(k+1)!} &= \dfrac{0}{(0+1)!}+\dfrac{1}{(1+1)!}+\dfrac{2}{(2+1)!}+\cdots + \dfrac{m}{(m+1)!}+\dfrac{m+1}{(m+2)!} \\ &=\displaystyle\left(\sum_{k=0}^{m}\dfrac{k}{(k+1)!} \right)+\dfrac{m+1}{(m+2)!} \\\\ &= 1-\dfrac{1}{(m+1)!}+\dfrac{m+1}{(m+2)!} \\\\&= 1-\dfrac{m+2}{(m+2)!}+\dfrac{m+1}{(m+2)!} \text{ (En effet, en multipliant (m+1)! par (m+2) on obtient (m+2)! )}\\\\ &= 1+\dfrac{-m-2+m+1}{(m+2)!} \\\\&=1-\dfrac{1}{(m+2)!} \end{array}$

Il s'ensuit que $\mathcal{P}(m+1)$ est vraie.

Conclusion, par récurrence : $\boxed{\forall n\in\mathbb{N}\text{ : } \displaystyle\sum_{k=0}^{n}\dfrac{k}{(k+1)!}=1-\dfrac{1}{(n+1)!}}$

Merci à Panter pour avoir contribué à l'élaboration de cette fiche

Publié par malou/Panter le 07-11-2024

ceci n'est qu'un extrait
Pour visualiser la totalité des cours vous devez vous inscrire / connecter (GRATUIT)
Inscription Gratuite se connecter

Cette fiche

Imprimer
Réduire / Agrandir
Pour plus d'options, Connectez vous
Forum de maths

Suites en terminale
Plus de 23 382 topics de mathématiques sur "Suites" en terminale sur le forum.