Raisonnement par récurrence
1. Étude d'un exemple
On considère la proposition \(P(n)\) dépendant d'un entier \(n\) : « \(10^n-(-1)^n\) est un multiple de \(11\) »
( On rappelle qu'un nombre est un multiple de 11 lorsqu'il s'écrit sous la forme \(11k\) avec \(k \in \mathbb{Z}\) )
Vérifions que cette proposition est vraie pour les entiers \(n = 0 ,1 ,2 , 3 , 4\)
Pour \(n=0\) : \(10^0- ( -1 )^0 = 1 - 1 = 0 = 11 \times 0\)
Pour \(n=1\) : \(10^1- ( -1 )^1 = 10 - ( -1 ) = 10 + 1 = 11 = 11 \times 1\)
Pour \(n=2\) : \(10^2- ( -1 )^2 = 100-1 = 99 = 11 \times 9\)
Pour \(n=3\) : \(10^3- ( -1 )^3 = 1 000 - ( -1 ) = 1 000 + 1 = 1 001 = 11 \times 91\)
Pour \(n=4\) : \(10^4 - ( -1 )^4 = 10 000 - 1 = 9999 = 11 \times 909\)
On pourrait continuer ainsi les vérifications mais , quel que soit le nombre de vérifications effectuées, on ne peut pas affirmer que cette proposition est vraie pour tout entier naturel \(n\).
Pour justifier que cette proposition est vraie pour tout entier naturel \(n\), démontrons le résultat suivant :
Si la proposition est vraie pour le rang \(n\), alors elle est vraie pour le rang suivant \(n+1\) .
Pour cela, supposons que la proposition est vraie pour un rang \(n\) ( \(n\) étant un entier naturel fixé ).
Alors pour cet entier naturel \(n\), on a :
\(10^n-( -1 )^n\) est un multiple de 11 c'est-à-dire \(10^n-( -1 )^n= 11 \times k\) avec \(k \in \mathbb{Z}\)
On veut alors démontrer que la proposition est vraie pour \(n+1\) c'est-à-dire que $10^{n+1}-( -1 )^{n+1} = 11 \times k', avec \(k' \in \mathbb{Z}\)
Puisque \(10^n- ( -1 )^n = 11 \times k\) avec \(k \in \mathbb{Z}\), on peut écrire :
\(10^n = 11 \times k + ( -1 )^n \Leftrightarrow 10 \times 10^n = 10 \lbrack 11 \times k+ ( -1 )^n \rbrack\)
\(\phantom{10^n = 11 \times k + ( -1 )^n} \Leftrightarrow 10^{n+1} = 110 \times k + 10 \times ( -1 )^n\)
\(\phantom{10^n = 11 \times k + ( -1 )^n} \Leftrightarrow 10^{n+1}-( -1 )^{n+1} = 110 \times k + 10 \times ( -1 )^n -( -1 )^{n+1}\)
\(\phantom{10^n = 11 \times k + ( -1 )^n} \Leftrightarrow 10^{n+1} - ( -1 )^{n+1} = 110 \times k + ( -1 )^n \lbrack 10 - (-1 )^1 \rbrack\)
\(\phantom{10^n = 11 \times k + ( -1 )^n} \Leftrightarrow 10^{n+1} - ( -1 )^{n+1} = 110 \times k + ( -1 )^n \lbrack 10 + 1 \rbrack\)
\(\phantom{10^n = 11 \times k + ( -1 )^n} \Leftrightarrow 10^{n+1} - ( -1 )^{n+1} = 11 \lbrack10k + ( -1 )^n \rbrack\)
\(k\) étant un entier, le nombre \(k' =10k+(-1)^n\) est aussi un entier.
On a donc démontré que : \(10^{n+1}-( -1 )^{n+1} = 11 \times k'\), \(k' \in \mathbb{Z}\)
On a donc démontré le caractère héréditaire de la proposition :
Si la proposition est vraie pour un entier \(n\), alors elle est vraie pour l'entier suivant \(n+1\).
On peut alors observer que : puisqu'elle est vraie pour \(n=0\), elle est vraie pour \(n=1\), puisqu'elle est vraie pour \(n=1\), elle est vraie pour \(n=2 \ldots\)
Il apparaît alors que la proposition est vraie pour tous les entiers \(n\) de \(\mathbb{N}\).
En assimilant l'ensemble \(\mathbb{N}\) des entiers naturels à une échelle sur laquelle on voudrait monter, le principe du raisonnement qui vient d'être fait est le suivant :
- si on sait monter sur le premier barreau de l'échelle
- et si l'on sait passer d'un barreau au barreau suivant,
- alors on peut atteindre tous les barreaux de l'échelle.
Le type de raisonnement ainsi effectué est appelé raisonnement par récurrence. Il est basé sur la propriété suivante :
2. Propriété
Propriété
Soit \(P(n)\) une proposition dépendant d'un entier \(n\) et \(n_0\) un entier fixé. Si \(P(n_0)\) est vraie (initialisation) et si pour tout entier \(n \geqslant n_0\) : \(P(n) \Rightarrow P(n+1)\)(hérédité) alors \(P(n)\) est vraie pour tout entier \(n \geqslant n_0\).
Remarque
Cette propriété, que l'on ne démontre pas et qui semble tenir du "bon sens" est en fait un axiome des mathématiques, c'est-à-dire un énoncé posé à priori qui sera une des bases de la théorie mathématique.
En géométrie un axiome célèbre est l'axiome d'Euclide : "Par un point donné il passe une parallèle et une seule à une droite donnée".
3. Dans la pratique
Démontrons par récurrence que pour tout \(n \in \mathbb{N}\), on a \(\(2^{n} \geqslant {n + 1}\)\)
Soit \(P(n)\) la proposition : « \(2^n\) est supérieur ou égal à \(n+1\)»
Initialisation :
pour \(n = 0\), on a :
\(2^n= 2^0 = 1\) et \(n+1=0+1 = 1\) soit \(1 \geqslant 1\) donc la proposition \(P(0)\) est vraie.
On pourrait vérifier sans difficulté la proposition \(P(n)\) pour \(n = 1, 2 , 3,\ldots\) cela peut être utile pour la compréhension, mais c'est sans utilité pour le raisonnement.
Hérédité :
Supposons que la proposition \(P(n)\) est vraie pour un entier naturel fixé \(n\).
On a donc : \(2^{n} \geqslant {n + 1}\)
Montrons que \(\text{P}{({n + 1})}\) est vraie , c'est-à-dire que: \(2^{n + 1} \geqslant { {({n + 1})} + 1}\)
On a :
\(2^{n} \geqslant {n + 1} \Leftrightarrow {2 \times 2^{n}} \geqslant {2 \times {({n + 1})}}\) \(\phantom{2^{n} \geqslant {n + 1}} \Leftrightarrow {2^{n + 1} \geqslant 2}{n + 2}\) \(\phantom{2^{n} \geqslant {n + 1}} \Leftrightarrow{ {2^{n + 1} - {({n + 2})}} \geqslant 2}{n + 2 - {({n + 2})}}\) \(\phantom{2^{n} \geqslant {n + 1}} \Leftrightarrow{2^{n + 1} - {({n + 2})}} \geqslant n\)
Or \(n\) est un entier naturel donc positif ou nul, on a donc :
La proposition \(P(n+1)\) est alors vérifiée.
Conclusion :
On a donc démontré par récurrence sur \(n\) que la proposition \(\text{P}{(n)}\) est vraie pour tout entier \(n \geqslant 0\).
c'est-à-dire que : \(2^{n} \geqslant {n + 1}\) pour tout \(n\) de \(\mathbb{N}\)