On étudie ici la technique de preuve par récurrence. Il s’agit d’une technique très générale s’appliquant à de nombreux domaines des mathématiques, non seulement à l’algèbre linéaire.
Si \(n=3\text{,}\) alors \(2^{2n}-1 = 2^6 -1 = 63\) qui est divisible par \(3\) car la somme de ses chiffres est \(6+3 = 9\) est elle-même un multiple de \(3\text{;}\)
Si \(n=4\text{,}\) alors \(2^{2n}-1 = 2^8 -1 = 255\) qui est divisible par \(3\) car la somme de ses chiffres est \(2+5+5 = 12\) est elle-même un multiple de \(3\text{.}\)
À la lumière de ces calculs on peut être tentés de penser que peu importe la valeur du naturel \(n\text{,}\) l’entier \(2^{2n}-1\) est toujours un multiple de \(3\text{.}\) C’est en effet le cas, comme on le verra sous peu. Afin d’en donner une preuve, on utilise le principe de preuve par récurrence.
On suppose que les conditions (a) et (b) sont remplies. On veut montrer que \(P(n)\) est vraie pour tout entier \(n \geqslant n_0\text{.}\) On procède par l’absurde, en supposant que l’ensemble
\begin{equation*}
\mathcal{E} = \{ n \in \N \mid \geqslant n_0 \mid P(n) \text{ est fausse} \}
\end{equation*}
est non vide. Cet ensemble contient un plus petit élément \(m_0\geqslant n_0\) dans \(\mathcal{E}\text{.}\) En particulier, \(P(m_0)\) est fausse. Par la condition (a), on sait que \(m_0 \neq n_0\text{.}\) Donc \(m_0 \gt n_0\) et ainsi \(m_0 - 1 \geqslant n_0\text{.}\) Par la minimalité de \(m_0\text{,}\) la propriété \(P(m_0 - 1)\) est vraie. Par la condition (b), cela implique que la propriété \(P((m_0 - 1) + 1) = P(m_0)\) est aussi vraie, ce qui contredit notre supposition que \(P(m_0)\) est fausse. On conclut que notre supposition initiale est fausse et donc que la propriété \(P(n)\) est vraie pour tout entier \(n \geqslant n_0\text{.}\)
Les images ci-bas illustrent une façon usuelle d’expliquer le principe de récurrence. Imaginez que vous placez des dominos, une infinité de dominos, debout les uns à la suite des autres, le premier étant numéroté par \(n_0\) (figure de gauche).
Le principe de récurrence dit que si le premier domino tombe (\(P(N_0)\) est vraie) et les dominos sont placés de sorte à ce que quand l’un d’eux tombe, le suivant tombe aussi (\(P(k)\) vraie entraîne \(P(k+1)\) vraie) alors tous les dominos tomberont (figure de droite).
Cas de base: on vérifie que la propriété \(P(n_0)\) est vraie pour une valeur initiale \(n_0\) de \(n\text{.}\) Souvent, cette valeur initiale sera \(n_0 = 0\) ou \(n_0 = 1\text{.}\)
Pas de récurrence: On suppose que pour un certain entier \(k \geqslant 0\text{,}\) la propriété \(P(k)\) est vraie. C’est-à-dire qu’il existe un entier \(a\) tel que \(2^{2k} - 1 = 3a\text{.}\) On veut montrer que la propriété \(P(k+1)\) est aussi vraie. On calcule alors
On pose pour un naturel \(n\text{,}\) donné \(P(n) : \sum_{j=0}^n (2j-1) = n^2\text{.}\) On va montrer par récurrence que \(P(n)\) est vraie pour tout naturel \(n\text{.}\)
On pose, pour un naturel \(n \geqslant 1\) donné \(P(n) : \text{ si } f(x) = x^n, \text{ alors } f'(x) = n x^{n-1}\text{.}\) On va montrer par récurrence que \(P(n)\) est vraie pour tout naturel \(n\text{.}\)
Cas de base: pour \(n=1\text{,}\) on a \(f(x) = x\) et donc \(f'(x) = 1 = 1 \cdot x^{1-1}\text{.}\) Donc \(P(1)\) est vraie.
Pas de récurrence: On suppose que pour un certain naturel \(k \geqslant 1\text{,}\) la propriété \(P(k)\) est vraie, c’est-à-dire que si \(f(x) = x^k\text{,}\) alors \(f'(x) = k x^{k-1}\text{.}\) On veut montrer que la propriété \(P(k+1)\) est également vraie. On considère la fonction \(g(x) = x^{k+1} = x \cdot x^k = g_1(x) \cdot g_2(x)\text{.}\) En utilisant la règle du produit pour la dérivation, on obtient :
