Définition

Le raisonnement par récurrence est une forme de raisonnement permettant de démontrer des propriétés sur les entiers naturels.

Le raisonnement par récurrence se fait toujours de la même manière :
– La propriété est vraie pour un premier rang n0, souvent 0 ou 1. Cette étape s’appelle l’initialisation.
– Si on suppose que la propriété est vrai pour un rang n ≥ n0 alors on montre la propriété au rang n+1. Cette étape s’appelle l’hérédité.
Et finalement la conclusion à cela c’est que la propriété est vraie au rang pour tout n ≥ n0

On a une sorte d’effet domino. Au jeu des dominos, si le premier domino tombe alors normalement les dominos suivants tomberont ensuite, l’un après l’autre. C’est comme cela que fonctionne la récurrence. Mais le mieux pour comprendre cette notion est de la voir à travers des exemples.

Exemples

Exemple 1 : La somme des entiers impairs

Le n-ième entier impair est de la forme 2n+1. Montrer que pour tout n positif, la somme des n premiers entiers impairs vaut n2. Autrement dit, écrit mathématiquement :

\forall n\in \N,\sum_{k=0}^{n-1} 2k + 1  = n^2 

La somme s’arrête bien à n-1 car entre 0 et n – 1 il y a précisément n termes. On va donc démontrer ce résultat par récurrence.


Etape 1 : Initialisation
La propriété est voulue à partir du rang 1. On va donc démontrer l’inégalité pour n = 1.
On a, d’une part :

\sum_{k=0}^{1-1} 2k + 1  = \sum_{k=0}^{0} 2k+ 1  = 2 \times 0 + 1 = 1

D’autre part,

1^2 = 1

L’égalité est donc bien vérifiée au rang 1

Etape 2 : Hérédité
On suppose que la propriété est vraie pour un rang n fixé. Montrer qu’elle est vraie au rang n+1.
Supposer que la propriété est vraie au rang n, cela signifie qu’on suppose que pour ce n, fixé, on a bien

\sum_{k=0}^{n-1} 2k + 1 = 1 + 3 + \ldots + 2n - 1 = n^2 

C’est ce qu’on appelle l’hypothèse de récurrence.

Notre but est maintenant de montrer la même propriété en remplaçant n par n+1, c’est à dire que :

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

On va donc partir de notre hypothèse de récurrence et essayer d’arriver au résultat voulu, c’est parti pour les calculs :

\begin{array}{l}\sum_{k=0}^{n-1}2k+1\ =1+3+\ldots+2n-1\ =\ n^2\\ \\
\Leftrightarrow\ 1\ +\ 3\ +\ \ldots\ +\ 2n-1\ =n^2\\ \\
\Leftrightarrow\ 1\ +\ 3\ +\ \ldots\ +\ 2n\ -\ 1\ +\ 2n\ +\ 1\ =\ n^{2\ }\ +2n\ +\ 1\\ \\
On\ reconnait\ une\ identité\ remarquable\ :\ \\  \\
\Leftrightarrow\ \sum_{k=0}^n2k\ -1\ =\ \left(n+1\right)^2\end{array}

Donc l’hérédité est vérifiée.
On peut donc maintenant conclure en disant que

\forall n  \in \N^*, \sum_{k=0}^{n-1} 2k-1 = n^2 

Exemple 2 : Une inégalité démontrée par récurrence

Montrons cette fois une inégalité par récurrence :

\forall n \in \N, \forall x \in \R_+,  (1+x)^n  \ge 1+nx

Etape 1 : Initialisation
On prend n = 0, on montre facilement que

\begin{array}{l}\forall\ x\ \in\ \mathbb{R}_+,\ \left(1+x\right)^0\ =\ 1\\
\forall\ x\ \in\ \mathbb{R}_+,\ 1+0\ \times\ x\ =\ 1\\
Et\  on\ a\ bien\ 1\ \ge\ 1\end{array}

L’initialisation est donc vérifiée

Etape 2 : Hérédité
On suppose que la propriété est vrai pour un rang n fixé. Ce qui fait que pour ce n, on a cette hypothèse de récurrence :

\forall x \in \R_+,  (1+x)^n  \ge 1+nx

On veut montrer la propriété au rang n+1, c’est à dire que

\forall x\in\mathbb{R}_+,\ (1+x)^{n+1}\ge1+\left(n+1\right)x

Une fois de plus, on va partir de l’hypothèse de récurrence pour arriver à ce résultat voulu :

\begin{array}{l}\forall x\in \mathbb{R}_+,\ (1+x)^n\ge 1+nx\\
\forall x\in \mathbb{R}_+,\ (1+x)^n\left(1+x\right)\ge \left(1+nx\right)\left(1+x\right)\ \\
\left(on\ a\ multiplié\ par\ \left(1+x\right)\ de\ chaque\ côté\right)\\
\forall x\in \mathbb{R}_+,\ (1+x)^{n+1}\ge \left(1+nx\right)\left(1+x\right)\ \\
\left(\left(1+x\right)^n\left(1+x\right)\ =\ \left(1+x\right)^{n+1}\right)\\
Puis\ on\ développe\ le\ membre\ de\ droite\ :\ \\
\forall x\in \mathbb{R}_+,\ (1+x)^{n+1}\ge \ 1\ +\ nx\ +x\ +nx^2\ \\
\end{array}

Puis on continue sur le membre de droite :

\begin{array}{l}1+nx+x+nx^2\ \ge\ 1+nx+x\ =\ 1+\left(n+1\right)x\\
Ainsi,\\
\left(1+x\right)^{n+1}\ge\ 1\ +\ \left(n+1\right)x\end{array}

L’hérédité est donc bien vérifiée.
Conclusion :

\forall n \in \N, \forall x \in \R_+,  (1+x)^n  \ge 1+nx

Exercices

Exercice 1 : Somme des carrés
Démontrer que pour tout entier n non nul, on a :

\sum_{k=1}^nk^2\ =\ 1^2+2^2+\ldots+\ n^2\ =\ \frac{n\left(n+1\right)\left(2n+1\right)}{6}

Exercice 2
Soit la suite définie par

\begin{array}{l}u_0=1\\
u_{n+1}=\ \sqrt{6+u_n}\end{array}

Montrer par récurrence que

\forall\ n\ \in\mathbb{N},\ 0\ \le\ u_n\ \le\ 3

Exercice 3
Soit la fonction f définie pour tout x ≠ 1 par

f(x)=\ \frac{1}{1+x}

Démontrer par récurrence que

\begin{array}{l}\forall n\ge1,\ f^{\left(n\right)}\ \left(x\right)=\ \frac{\left(-1\right)^nn!}{\left(1+x\right)^{n+1}}\\ \\
Indication\ :\ -\left(-1\right)^{n\ }=\left(-1\right)^{n+1}\\  \\
f^{\left(n\right)}\ désigne\ la\ dérivée\ n^{ième\ }de\ f\end{array}

Si vous n’êtes pas familiers avec ce « n ! », allez voir notre article sur les factorielles.

Exercice 4
Démontrer que pour tout n entier, 10n-1 est un multiple de 9.

Exercice 5
Soit A,D et P 3 matrices telles que

\begin{array}{l}A\ =\ PDP^{-1}\end{array}

Montrer par récurrence que

\begin{array}{l}A^n\ =\ PD^nP^{-1}\end{array}

Cet article vous a plu ? Retrouvez nos autres articles de révision du bac :