Récurrence : Cours et exercices

Tout savoir sur la récurrence : Définitions, divers exemples et quelques exercices pour bien comprendre la notion.
Domino récurrence

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 vraie 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}{ll}&\displaystyle \sum_{k=0}^{n-1}2k+1\ =1+3+\ldots+2n-1\ =\ n^2\\
\iff& 1 + 3\ + \ldots\ + 2n-1 =n^2\\
\iff&1 + 3 + \ldots\ + 2n - 1 + 2n + 1 = n^{2} +2n + 1 \\
&\text{On reconnait une identité remarquable : }  \\
\iff&\displaystyle\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\\
\text{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)\ \\
\text{(On a multiplié par (1+x) de chaque côté)}\\
\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)\\
\text{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\\
\text{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

Si vous voulez aller plus loin, nous vous conseillons notre article sur la récurrence double et la récurrence forte

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)= \dfrac{\left(-1\right)^nn!}{\left(1+x\right)^{n+1}}\\ 
\text{Indication : } -\left(-1\right)^{n\ }=\left(-1\right)^{n+1}\\  
f^{\left(n\right)} \text{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}

Si vous voulez des exercices plus compliqués, allez voir nos exercices de prépa sur les récurrences
Cet article vous a plu ? Retrouvez nos autres articles de révision du bac :

Total
0
Shares
1 commentaire

Laisser un commentaire

Articles similaires
Des idées de cadeaux pour Noël ? Vous voulez profiter du Black Friday ? Voici nos propositions de livres et objets mathématiques !
Découvrez nos idées