RAISONNEMENT PAR RÉCURRENCE
1 ) ÉTUDE D’UN EXEMPLE
On considère la proposition P(n) dépendant d'un entier n : « 10n - ( -1 )n est un multiple de 11 »
( On rappelle qu'un nombre est multiple de 11 lorsqu'il s'écrit sous la forme 11 ´ k avec k Î ZZ )
Vérifions que cette proposition est vraie pour les entiers n = 0 , 1 , 2 , 3 , 4
Pour n = 0 : 100 - ( -1 )0 = 1 - 1 = 0 = 11 ´ 0
Pour n = 1 : 101 - ( -1 )1 = 10 - ( -1 ) = 10 + 1 = 11 = 11 ´ 1
Pour n = 2 : 102 - ( -1 )2 = 100 - 1 = 99 = 11 ´ 9
Pour n = 3 : 103 - ( -1 )3 = 1 000 - ( -1 ) = 1 000 + 1 = 1 001 = 11 ´ 91
Pour n = 4 : 104 - ( -1 )4 = 10 000 - 1 = 9999 = 11 ´ 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 :
10n - ( -1 )n est un multiple de 11 c'est-à-dire 10n - ( -1 )n = 11 ´ k avec k Î ZZ
On veut alors démontrer que la proposition est vraie pour n + 1 c'est-à-dire que 10n + 1 - ( -1 )n + 1 = 11 ´ k’ , k’ Î ZZ
Puisque 10n - ( -1 )n = 11 ´ k avec k Î ZZ , on peut écrire :
10n = 11 ´ k + ( -1 )n
⇒ 10 ´ 10n = 10 [ 11 ´ k + ( -1 )n ]
⇒ 10n + 1 = 110 ´ k + 10 ´ ( -1 )n
⇒ 10n + 1 - ( -1 )n + 1 = 110 ´ k + 10 ´ ( -1 )n - ( -1 )n + 1
⇒ 10n + 1 - ( -1 )n + 1 = 110 ´ k + ( -1 )n [10 - ( -1 ) 1 ]
⇒ 10n + 1 - ( -1 )n + 1 = 110 ´ k + ( -1 )n [10 + 1]
⇒ 10n + 1 - ( -1 )n + 1 = 11 [10 k + ( -1 )n ]
k étant un entier, le nombre k’ =10 k + ( -1 )n est aussi un entier.
On a donc démontré que : 10n + 1 - ( -1 )n + 1 = 11 ´ k’ , k’ Î ZZ
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 0, elle est vraie pour 1, puisqu'elle est vraie pour 1, elle est vraie pour 2 .....
Il apparaît alors "clairement" que la proposition est vraie pour tous les entiers n de IN.
En assimilant l'ensemble IN 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.
- Raisonnement par récurrence - auteur : Pierre Lux - page 1/2
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 n0 un entier fixé.
Si P(n0) est vraie ( initialisation )
et si pour tout entier n ³ n0 : P(n) P(n + 1) ( hérédité )
alors P(n) est vraie pour tout entier n ³ n0
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 de IN, on a 2n ³ n + 1
Soit P(n) la proposition : « 2n est supérieur ou égal à n + 1 »
Initialisation :
pour n = 0, on a :
2n = 20 = 1 et n + 1 = 0 + 1 = 1, donc la proposition P(0) est vraie.
On pourrait vérifier sans difficulté la proposition P(n) pour n = 1, 2 , 3... cela peut être utile pour la compréhension, mais c'est sans utilité pour le
raisonnement.
Hérédité : L'hypothèse " P(n) est vraie" s'appelle
Supposons que la proposition P(n) est vraie pour un entier naturel fixé n. l'hypothèse de récurrence.
On a donc : 2n ³ n + 1 (HR)
Montrons que P(n + 1) est vraie , c'est-à-dire que : 2n + 1 ³ (n + 1) + 1
On a :
(HR) 2n ³ n + 1 ⇒ 2 ´ 2n ³ 2 ´ (n + 1 ) ⇒ 2n + 1 ³ 2 n + 2
Or n est un entier naturel donc positif ou nul, on a donc : 2n+2 ³ n+2, c’est à dire 2n+2 ³ (n+1)+1
Ainsi 2n + 1 ³ (n + 1) + 1
La proposition P(n + 1) est alors vérifiée.
Conclusion :
On a donc démontré par récurrence que la proposition P(n) est vraie pour tout entier n ³ 0.
c'est-à-dire que : 2n ³ n + 1 pour tout n de IN
- Raisonnement par récurrence - auteur : Pierre Lux - page 2/2
