Suites : Raisonnement par récurrence

Qu'appelle-t-on "raisonnement par récurrence" ? - - Quelques exemples de démonstrations
Quand faut-il utiliser un raisonnement par récurrence ?

1. Le raisonnement par récurrence exposé sur un exemple

· Le problème posé

Quels sont les entiers naturels n tels que 9ⁿ-1 est divisible par 8 ?

La table des valeurs de la fonction f définie par

permet d'observer que la propriété "

est divisible par 8 "est vraie pour les premières valeurs de n.
On peut faire la conjecture que la propriété est vraie pour tout n de N.
Voici une méthode (il y en a d'autres), qui permet de le démontrer. On notera P(n)la propriété "9_n-1 est divisible par 8 ".

· La démonstration

Les deux étapes étapes de la démonstration et la conclusion	L'échelle, une image "parlante" ®
· 1. Pour tout entier n fixé dans N , si P(n) est vraie, alors P(n+1)est vraie. Démonstration On dit que P(n) est héréditaire dans N.	· 1. On sait passer d'un échelon à l'autre
· 2. P(0) est vraie En effet 9₀-1=0, c'est bien un nombre divisible par 8.	· 2. On peut mettre le pied sur le premier échelon
· Donc P(n) est vraie pour tout n de N.	· Donc on peut mettre le pied sur n'importe quel échelon, aussi haut soit-il.

Une démonstration de ce type s'appelle une démonstration par récurrence.
Elle se déroule en deux étapes : vérification que P(n) est vraie pour le premier indice et démonstration que P(n) est héréditaire

2. Le principe

Toute démonstration par récurrence s'appuie sur la propriété de l'ensemble N qui suit :

Soit I une partie de N.

Si les deux propriétés suivantes sont vraies :

{

I contient l'entier 0
pour tout entier naturel n, si n est dans I,alors n+1 est dans I

alors I=N .

D'où le résultat (pour le démontrer, il suffit de considérer l'ensemble I des nombres n tels que P(n) est vraie) :

Soit P(n) une propriété dépendant d'un entier naturel n.

Si les deux propriétés suivantes sont vraies :

{

P(0) est vraie
P(n) est héréditaire dans N

alors P(n) est vraie pour tout n de N.

3. Deux exemples pour bien comprendre le rôle des deux étapes dans une démonstration par récurrence

· Premier exemple: Q(n) est la propriété "9ⁿ+1 est divisible par 8"

Que peut-on dire de Q(n) ?	L'image de l'échelle ®
· Q(n) est héréditaire dans N. Démonstration	· On sait passer d'un échelon à l'autre
· Pour tout entier n, Q(n) est fausse. Démonstration	· On ne peut mettre le pied sur aucun échelon

· Second exemple: R(n) est la propriété "4ⁿ-1 est divisible par 5"

Que peut-on dire de R(n) ?	L'image de l'échelle ®
· Quel que soit n de N, R(n) n'est pas héréditaire. Démonstration	· On ne sait pas passer d'un échelon à l'autre
· R(2) est vraie. En effet 4²-1=15, c'est bien un nombre divisible par 5.	· On peut mettre le pied sur un échelon (le premier ici)

Retour à la page Suites

Source : académie de grenoble.

mesure audience

Annuaire-NORD-FRANCE

Dernier post du Forum

Warning: main(http://mathemitec.free.fr/forum/extern.php?action=new&show=1) [function.main]: failed to open stream: Network is unreachable in /mnt/116/sdb/f/c/mathemitec/frames/left.php on line 7

Warning: main() [function.include]: Failed opening 'http://mathemitec.free.fr/forum/extern.php?action=new&show=1' for inclusion (include_path='/mnt/116/sdb/f/c/mathemitec/include:.:/usr/php4/lib/php') in /mnt/116/sdb/f/c/mathemitec/frames/left.php on line 7

Warning: main(/mnt/116/sdb/f/c/mathemitec/myspeach/chat.php) [function.main]: failed to open stream: No such file or directory in /mnt/116/sdb/f/c/mathemitec/frames/left.php on line 14

Fatal error: main() [function.require]: Failed opening required '/mnt/116/sdb/f/c/mathemitec/myspeach/chat.php' (include_path='/mnt/116/sdb/f/c/mathemitec/include:.:/usr/php4/lib/php') in /mnt/116/sdb/f/c/mathemitec/frames/left.php on line 14