2.1.1.2 Le raisonnement par récurrence

Théorème 2.1.1 (Le principe de récurrence)
Soient $p(n)$ un prédicat sur ${\mathbb{N}}$ et $n_0 \in {\mathbb{N}}$. On suppose que :

• $p(n_0)$ est vrai.
• $\forall\: k \geqslant n_0, p(k) \Longrightarrow p(k+1)$.

Alors, $p(n)$ est vrai pour tout $n \geqslant n_0$.

Démonstration :

^2.3

En remplaçant $p(n)$ par $q(n)=p(n+n_0)$, on peut supposer que $n_0=0$. Soit $A = \{n \in {\mathbb{N}} /  p(n)\}$. Si $A^c \neq \emptyset$, $A^c$ a un plus petit élément $m$. $k=m-1 \in A$, donc $p(k)$ est vraie, ainsi que $p(k+1)=p(m)$ d'après la deuxième hypothèse, c'est-à-dire $m \in A$, en contradiction avec le fait que $m\in A^c$. Donc $A^c = \emptyset$ et $A={\mathbb{N}}$.

C.Q.F.D.

Commentaires :

1. Le principe de récurrence permet donc de faire une hypothèse supplémentaire, l'hypothèse de récurrence $p(k)$. On l'a noté $p(k)$ et non $p(n)$ pour souligner qu'on n'utilise pas la conclusion $\forall\:n \geqslant n_0, p(n)$.

2. Il ne faut pas oublier de « commencer » la récurrence, i.e.^2.4 de démontrer que $p(n_0)$ est vraie. En effet, sans cette précaution, on peut démontrer n'importe quelle propriété des entiers. Par exemple « montrons » que pour tout $n \in {\mathbb{N}}$, $n \not= n$. Supposons donc $k \not= k$. Il est alors clair que $k+1 \not= k+1$ !! On voit bien qu'on pourrait remplacer $n \not= n$ par n'importe quel prédicat tout aussi faux, sinon aussi absurde.

Exercice 2..1 (progression arithmétique)
^2.5Montrez par récurrence que $\forall n \geqslant 1, 1+2+3+\dots+n=\dfrac{n(n+1)}{2}$

Exercice 2..2
Montrez par récurrence que $\forall n \geqslant 1, 1^2+2^2+3^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}$

Exercice 2..3
Montrez par récurrence que $\forall n \geqslant 1, 1^3+2^3+3^3+\dots+n^3=\dfrac{n^2(n+1)^2}{4}$

Exercice 2..4 (progression géométrique)
^2.6Montrez par récurrence que, si $x$ est un nombre réel, ou même complexe, et $x\not=1$, alors $\forall n \geqslant 1, 1+x+x^2+\dots+x^n=\dfrac{1-x^{n+1}}{1-x}$

Les résultats des exercices 2.1 et 2.4 sont importants, et sont donc à connaître parfaitement.

Exercice 2..5
Montrez par récurrence que

$$\forall n \geqslant 2, x \in A_1 \oplus A_2 \oplus \dots \o... ...nt n)\\ tels que x \in A_i est impair. \end{array}\right.$$

On s'inspirera de la démarche utilisée dans l'exercice 1.13.