Fiche de mathématiques
> >

Raisonnement par récurrence

Partager :

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é le
ceci n'est qu'un extrait
Pour visualiser la totalité des cours vous devez vous inscrire / connecter (GRATUIT)
Inscription Gratuite se connecter


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !