cours : Initiation au raisonnement par récurrence

Eliane Bazillais

Description

² 1. Initiation au raisonnement par récurrence Il s'agit d'un raisonnement inductif, c'est-à-dire un raisonnement visant à produire des connaissances par des conclusions plus générales que les prémisses. A partir du constat de la validité d'une propriété dépendant d'un entier naturel n sur des cas particuliers, on la valide par une démonstration pour une situation générale. Cette démonstration est donc réalisée en enchaînant trois étapes : La phase 1 consiste à vérifier la propriété proposée sur un cas particulier. Elle correspondra à la plus petite valeur n du naturel n à partir de laquelle la propriété proposée à la odémonstration sera vraie (en général pour n = 0 ou n = 1). Cette phase est celle de l'initialisation, on contrôle qu'il existe bien une première valeur qui enclenche le processus. La phase 2 consiste à démontrer que si la propriété est vraie pour une valeur p indéfinie supérieure ou égale à la valeur particulière n , elle est alors vraie pour la valeur suivante p + 1. oCette étape est celle de l'hérédité, tout successeur reçoit la propriété de son prédécesseur. La phase 3 consiste à formuler la procédure et sa conclusion : la propriété est vraie pour la valeur n . oSi elle est vraie pour p, alors elle est vraie pour p + 1, on peut donc en conclure qu'elle s'étend à tout entier n  n . La propriété est vraie pour toute valeur de n supérieure ou égale à n .o o Cette dernière phase, en s'appuyant sur les phases 1 et 2, ...

Informations

• Publié par: Voof
• Nombre de lectures: 363
• Langue: Français

Extrait

1. Initiation au raisonnement par récurrence Il s'agitd'unraisonnementinductif,c'est-à-dire un raisonnement visant à produire des connaissances par des conclusions plus générales que les prémisses. A partir du constat de la validitéd'une propriété dépendant d'un entier naturelnsur des cas particuliers, on la valide par une démonstration pour une situation générale. Cette démonstration est donc réalisée en enchaînant trois étapes : La phase 1 consiste à vérifier la propriété proposée sur un cas particulier. Elle correspondra à la plus petite valeurn o du naturelnà partir de laquelle la propriété proposée à la démonstration sera vraie (en général pourn =0ou n =1). Cette phase est celle del'initialisation,on contrôle qu'il existe bien une première valeur qui enclenche le processus. La phase 2 consiste à démontrer que si la propriété est vraie pour une valeur p indéfinie supérieure ou égale à la valeur particulièren o ,elle est alors vraie pour la valeur suivantep +1. Cette étape est celle del'hérédité,tout successeur reçoit la propriété de son prédécesseur. La phase 3 consiste à formuler la procédure et sa conclusion : la propriété est vraie pour la valeurn o . Si elle est vraie pourp,alors elle est vraie pourp +1, on peut donc enconclure qu'elle s'étend à tout entier n n o .La propriété est vraie pour toute valeur densupérieure ou égale àn o . Cette dernière phase, en s'appuyant sur les phases 1 et 2,valide à l'infinila propriété énoncée et lui confère son caractère de généralité. Cette procédure « démonstration par récurrence » approchée par divers mathématiciens anciens, al-Karaji (? – 1023),as-Samw'al ( ? – 1175),Pascal (1623 – 1662), a été théorisée définitivement au siècle dernier par Henri Poincaré (1854 – 1912). Il faut remarquer que cette méthode ne fait rien découvrir, elle permet seulement de valider des propriétés inventées » par ailleurs. C'est dans l'élaboration de la formule de récurrence que réside la difficulté essentielle. Exemple. Vérifier à l'aide du tableur ou de la calculatrice que 2n² + 2n+ 8 est divisible par 4 , pour tout entier natureln. Le démontrer par récurrence. Initialisation Hérédité

2. Division euclidienne dans Théorème et définition : Soitaetbdeux entiers naturels,bétant non nul. Il existe des entiers naturelsqetruniquestels quea =b q+ ra v e c0r<b. On dit queaest ledividende,blediviseur,qlequotientetrle reste dans ladivision euclidiennedeaparb. Remarque:y a de multiples écritures de Ilasous la formeb x q + rmais une seule est la relation de la division euclidienne deaparb. Par exemple 103 = 13´7 + 12 mais on a aussi 103 = 13´6 + 25. Seule l'égalité ………………………… est la relation de la division euclidienne de 103 par 13 car ………… Écriture d'un algorithme de division euclidienne Un algorithmeest un procédé de calcul. Il s'agit donc ici de mettre en évidence une méthode dont l'exécution pas à pas, appliquée à deux entiers naturelsaetb,conduit à la connaissance des entiersqetr, lorsque l'on ne dispose que de la commande de division notée « / » ou «¸» . AlgorithmeProgramme sur TI Initialisation :Donner à A la valeur du dividende  Donnerà B la valeur du diviseur Traitement :Calculer A/B  Donnerà Q la valeur ENT (A/B)  Donnerà R la valeur ……………….. Sortie :Afficher Q Afficher R Exercice. Sachant que 38 367 = 152´251 + 215 , effectuer , sans calculatrice et sans la poser , la division euclidienne de 38 367 par :251152 3. Multiplesdans  Le programme de première a défini les multiples d'un entier naturel dans. Dire qu'un entier naturelaest multiple d'un entier naturelbnon nul signifie qu'il existe un entier naturelktel quea = b ´ kou encorebk.On dit aussi quebest un diviseur dea.Ainsi a–t–on 28 multiple de 4 car 28 = 4´7 et 4 qui est diviseur de 28. Dire que l'entier naturelaest divisible par l'entier naturelbest équivalent à dire queaest multiple deb.Les propositions «a est multiple de b »et «b est diviseur de a»signifient la même chose. L'extension à l'ensemble des entiers relatifsconduit à la définition qui suit. Définition : Dire que l'entier relatifaest multiple de l'entier naturelbnon nul signifie qu'il existe un entier relatifktel quea = b´ kou encorebk.Cela consiste donc à compléter la liste des naturels multiples debpar leurs opposés (à chaque entier naturelkon associe son opposé –k). Exemple. Dans, les multiples de 7 sont …………………………………………………………………… 4. Congruencesdans Définition :nétant un entier naturel non–nul, on dira que deux nombres entiers relatifsaetbsont congrus modulon siet seulement si leur différencea–best un multipledendans. On noteaºb(modulon) ouaºb(modn) ouaºb(n) . Le nombrenétant un entier naturel non–nul, «aºb(modn) »est équivalent à « Il existe un entier relatifktel quea – b= k´ n». Exemples 1.

Vérifier que 62º27 (mod 7) ………………………………………………………………………... Vérifier que 255º107 (mod 37) ……………………………………………………………………... Vérifier que 107º255 (mod 37) ……………………………………………………………………... Vérifier que 86º– 5 (mod 7) ………………………………………………………………………... Exemples 2. Les nombres 136 et 7 sont-ils congrus modulo 7 ? …………………………………………………………………………... Les nombres 14 533 et 6 742 sont-ils congrus modulo 7 ? …………………………………………………………………………... Exemples 3. A-t-on 4º4 (1) ?197º– 9197 (1) ?º–/ (1! 3Conjecturer une propriété , puis démontrer-la. Exemples 4. Soitaun entier relatif tel queaº0 (3). Que peut-on affirmer sura? Soitbun entier relatif tel quebº0 (19). Que peut-on affirmer surb? Premières propriétés oPour tout entier relatif a,aºa(modn) oaº0 (n) si et seulement si………………………………………………………………………... oPour tous lesentiers relatifs aetb, siaºb(modn) , alorsbº…(modn) oPour tous lesentiers relatifs a , betc siaºb(modn) etbºc(modn) alors…º…(modn) Lien avec la division euclidienne Tout nombre est congru modulonau reste de sa division euclidienne parn. Applications. Effectuer la division euclidienne de 237 par 5. L'écrire sous forme de congruence. Effectuer la division euclidienne de 122 par 5. L'écrire sous forme de congruence. Propriété caractéristique, Deux nombres entiers relatifs aetbsont congrus modulonsiet seulement si ils ont même resterpar leur division euclidienne parn.Dans ce casaetbsont congrus à ce rester. Application1. A-t-on 237º122 (mod5) ? ( sans calcul). Application2. Effectuer la division euclidienne de 342 par 5. Effectuer la division euclidienne de 5428 par 5. A-t-on 342º5428 (mod5) ? ( sans calcul).

Compatibilité avec l'addition etla multiplication Addition :siaºa'(modn) etbºb'(modn) a–t–ona+bºa'+b'(modn) ? Considérons d'abord un cas particulier avec les nombres 125 et 334 et la congruence modulo 7. 125º7) et… (mod334º… (mod7) .D'une part 125 + 334 = …….et …….º… (mod7) . Sur ce cas particulier, on constate qu'il y a compatibilité des congruences modulo 7 avec l'addition. Multiplication:siaºa'(modn) etbºb'(modn) a–t–ona´bºa'´b'(modn) ? Considérons d'abord un cas particulier avec les nombres 125 et 334 et la congruence modulo 7. 125º… (mod7) et334º… (modD'une part 1257) .´334 = …….et …….º7) .… (mod Sur ce cas particulier, on constate qu'il y a compatibilité des congruences modulo 7 avec la multiplication. Propriétés. Pour tous lesentiers relatifs a,b,a' etb' et pour tout entier naturel non-nuln, Compatibilité avec l'addition :siaºb(modn) eta'ºb'(modn… + …..) alors…º…… + ..…(modn) Compatibilité avec la multiplication :siaºb(modn) eta'ºb'(modn……..) alors…º……..…(modn)

Conséquences Sikest un entier relatifet siaºb(modn) etalorskaº……..…(modn) Siketk' sont des entiers relatifs etsiaºb(modn) eta'ºb'(modn) alorska+k'a'º……..…(modn) En particulier, siaºb(modn) eta'ºb'(modn… – …..) alors…º…… – ..…(modn) k Siket siest un entier naturel supérieur ou égal à 1aºb(modn) etalorsaº……..…(modn) Exercice.entiers Deuxaetb sont tels queaº3(mod 7) etbº6 (mod 7) . Démontrer que 2a+b² est divisible par 7. Compatibilité avec l'addition etla multiplication Addition :siaºa'(modn) etbºb'(modn) a–t–ona+bºa'+b'(modn) ? Considérons d'abord un cas particulier avec les nombres 125 et 334 et la congruence modulo 7. 125º3347) et… (modº… (mod7) .D'une part 125 + 334 = …….et …….º… (mod7) . Sur ce cas particulier, on constate qu'il y a compatibilité des congruences modulo 7 avec l'addition. Multiplication:siaºa'(modn) etbºb'(modn) a–t–ona´bºa'´b'(modn) ? Considérons d'abord un cas particulier avec les nombres 125 et 334 et la congruence modulo 7. 125º334… (mod7) etº7) .… (modD'une part 125´et …….334 = …….º… (mod7) . Sur ce cas particulier, on constate qu'il y a compatibilité des congruences modulo 7 avec la multiplication. Propriétés. Pour tous lesentiers relatifs a,b,a' etb' et pour tout entier naturel non-nuln, Compatibilité avec l'addition :siaºb(modn) eta'ºb'(modn… + …..) alors…º…… + ..…(modn) Compatibilité avec la multiplication :siaºb(modn) eta'ºb'(modn……..) alors…º……..…(modn)

Conséquences Sikest un entier relatifet siaºb(modn) etalorskaº……..…(modn) Siketk' sont des entiers relatifs etsiaºb(modn) eta'ºb'(modn) alorska+k'a'º……..…(modn) En particulier, siaºb(modn) eta'ºb'(modn… – …..) alors…º…… – ..…(modn) k Siket siest un entier naturel supérieur ou égal à 1aºb(modn) etalorsaº……..…(modn) Exercice. Deuxentiersaetb sont tels queaº3(mod 7) etbº6 (mod 7) . Démontrer que 2a+b² est divisible par 7.

5. Quelques applications des congruences : les cles de controle Le numéro INSEE: Institut National des Statistiques et des Études Économiques. Ce numéro est aussi notre numéro de Sécurité Sociale. Il est constitué de 15 chiffres. En lisant de gauche à droite : er o2 s'il s'agit d'une femme ;1 s'il s'agit d'un homme etchiffre estLe 1 ochiffres suivants désignent les deux derniers chiffres de votre année de naissance ;les 2 onaissance ;les 2chiffres suivants désignent le mois de oles 2 chiffres suivants désignent, du numéro de département de naissance ; oles 3 chiffres suivants désignent le numéro de la commune de naissance (les communes d'un département sont numérotées relativement à l'ordre alphabétique), oles 3rang de déclaration de naissance à la mairie au cours du mois ;chiffres suivants désignent le ochiffres désignent la clé de contrôle K , calculée de la manière suivante :les deux derniers soit Ale nombre entier constitué par les 13 chiffres de gauche ; soitrle reste de la division euclidienne du nombre Apar 97 alors K = 97 –r. Exemple 1 : Relevé sur une carte Vitale (identique au code INSSE) : 1 47 01 35 238 246. La clé de contrôle est 02. Est-elle juste ? Effectuons la division euclidienne de 1 470 135 238 246 par 97, on obtient 1 470 135 238 246 = 97´…………………………15156033383 + ……. et donc K = Exemple 2 :Vérifier votre carte vitale Les codes barres Pour désigner un produit de consommation on utilise le code UPC (Universel Product Code) constitué de 13 chiffres. Les douze premiers désignent le produit : le premier à gauche désigne le pays où l'article a été codifié (France 3), les cinq suivants (22888) identifient le fournisseur et les six qui suivent (104729) permettent une codification interne au fournisseur. Le treizième chiffre (8) est une clé de contrôle utile à la détection d'une erreur d'écriture de l'un des douze premiers chiffres. La clé est conçue de sorte que, si le code s'écrit C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 C 10 C 11 C 12 C 13 , lasomme du triple de la somme des chiffres d'indice pair et de la somme des chiffres d'indice impair soit congrueà 0 modulo 10. Exemple 1 : Le code est donc 3 22888 104729 8. Le triple de la somme des termes d'indice pair est………………………………………………………… la somme des chiffres d'indice impair est ………………………………………………………………… d'où la somme …….., nombre congru à 0 modulo 10. La lecture de ce code ne détecte pas d'erreur. Exemple 2 :Le produit est codé par la série 5 432 664 272 77, déterminer la cléassociée.