Le raisonnement par récurrence est essentiel en mathématiques lorsqu’on travaille avec des nombres entiers. Dans cet article, définissons cette manière de raisonner et corrigeons quelques exercices pour bien comprendre.
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.
Exercices corrigés
Exercice 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, \displaystyle \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 \displaystyle \forall n \in \N^*, \sum_{k=0}^{n-1} 2k-1 = n^2
Exercice 2 : Une inégalité démontrée par récurrence
L’inégalité de Bernoulli est un incontournable lorsqu’on commence à faire des récurrences.
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\ 3Exercice 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
