[PDF] Chapitre 1 - Raisonnement par récurrence

View - Download Chapitre 1 - Raisonnement par récurrence

Previous PDF

Next PDF

Chapitre 1

Raisonnement par r´ecurrence

1.1 Cours en bref

Le raisonnement par r´ecurrence est une m´ethode de r´esolution. Elle per- met de d´emontrer une propri´et´e pour tout ou presque tout entier naturel. La question de son utilisation se pose donc naturellement lorsqu"il est demand´e de d´emontrer qu"une certaine propri´et´e est vraie quel que soitnentier naturel. Cependant, il ne faut pas croire que d`esquecetypedequestionestpos´e, il s"agira alors d"une r´ecurrence. Il existe quelques signes qui permettent de nous mettre sur la voie. Mais avant cela voyons en quoi consiste le raisonnement par r´ecurrence. L"id´ee est en fait assez simple. Elle repose sur 2 ´etapes : (1) d´emontrer que la propri´et´e est vraie pour un certain rangn0 (qui estsouvent0ou1) et (2) d´emontrer quesila propri´et´e est vraie pour un rangn≥n0 quelconquealorselle l"est pour le rangn+1 (c"est-`a-dire le rang juste apr`es). Une fois ces 2 ´etapes franchies on peut affirmer que la propri´et´eest vraie pour tous les rangs sup´erieurs `an0 . En effet, (1) nous dit que la propri´et´e est vraie pour le rangn 0 , (2) nous permet alors de dire qu"elle l"est pour le rangn 0 +1,onr´eutilise (2) pour obtenir le rangn0 +2etainside suite, on obtient tous les rang sup´erieurs. Ce qui permet de montrer l"h´er´edit´e est l"utilisation du lien entre le rangnet le rangn+ 1, on y reviendra dans les exemples donn´es car c"est l"id´ee centrale. L"´etape (1) est appel´eeinitialisationet l"´etape (2)h´er´edit´e.

9782340-020054_001_192.indd 79782340-020054_001_192.indd 710/07/2017 15:4410/07/2017 15:44

8 CHAPITRE 1. RAISONNEMENT PAR R´ECURRENCE

1.2 Premier exemple

La r´eussite d"un raisonnement par r´ecurrence passe par la r´edaction. Une r´ecurrence mal r´edig´ee donne une tr`es mauvaise impression au correcteur. Il faut donc respecter scrupuleusement le mod`ele donn´e.

Exemple :

On consid`ere la suite d´efinie pour tout entiern?Npar :? ?u 0 =1 u n+1 =5u n -2

D´emontrer que pour tout entiern?Nu

n =1 2(5 n +1).

Solution :

Pour tout entiern?N,onposeH

n :u n =1 2(5 n +1). (1)Initialisation :Montrons queH 0 :u 0 =1 2(5 0 +1)estvraie.

D"une part,u

0 =1pard´efinition, et d"autre part,1 2(5 0 +1)=1

2(1 + 1) = 1.

On a donc bienu

0 =1 2(5 0 + 1), doncH 0 est vraie. (2)H´er´edit´e: Supposons queH n est vraie pour un certain rang n≥0 (c"est ce que l"on appelle l"hypoth`ese de r´ecurrence). Montrons alors que H n+1 :u n+1 =1 2(5 n+1 +1)estvraie. u n+1 =5u n -2 =5×1 2(5 n +1)-2par d´efinition =5 n+1

2+52-2

par hypoth`eseder´ecurrence =5 n+1 2+12 1 2(5 n+1 +1)en factorisant par 1 2

AinsiH

n+1 est vraie. Par le principe du raisonnement par r´ecurrence,H n est vraie pour tout entiern?N.

D´etaillons un peu...

9782340-020054_001_192.indd 89782340-020054_001_192.indd 810/07/2017 15:4410/07/2017 15:44

1.3. D"AUTRES EXEMPLES CLASSIQUES 9

On peut l´egitimement se diriger vers un raisonnement par r´ecurrence dans ce type dexercice puisquil porte sur une suite d´e“nie par r´ecurrence. On dit souvent que la r´ecurrence appelle la r´ecurrence...

Il faut toujours ´ecrireH

n 0 dans l"initialisation etH n+1 dans l"h´er´edit´e. Cela permet de voir ce que l"on doit d´emontrer. Dans un cas comme dans l"autre il s"agit d"une ´egalit´e`ad´emontrer. On utilise pourtant 2 m´ethodes diff´erentes. Dans l"initialisation on calcule chacun des 2 membress´epar´ement pour trouver le mˆeme r´esultat, ils sont donc ´egaux. Dans l"h´er´edit´e, on part deu n+1 que l"on manipule pour obtenir le r´esultat voulu. La justification "par hypoth`ese de r´ecurrence" doittoujoursapparaitre, sinon il y a 3 possibilit´es :

•c"est un oubli,

•il y a une erreur dans le raisonnement,

•le raisonnement par r´ecurrence n"´etait pas n´ecessaire. Il faut bien comprendre que la partie difficile est souvent la partie h´er´edit´e. Ce qui permet de montrer l"h´er´edit´e est le lien entre le rangnet le rangn+1 ainsi qu"une bonne utilisation de l"hypoth`ese de r´ecurrence. La premi`ere chose `arep´erer ´etant ce lien, et ici il apparait clairement dans la d´efinition de la suite.

1.3 D"autres exemples classiques

1.3.1 Avec une somme

Exercice :

D´emontrer que pour tout entiern?N:

n k=0 k=n(n+1) 2 Cest un exercice classique faisant intervenir le symbole somme. La m´ethode pour trouver le lien entre le rangnet le rangn+ 1 est assez simple puisqu"il va suffire de couper la somme en 2.

9782340-020054_001_192.indd 99782340-020054_001_192.indd 910/07/2017 15:4410/07/2017 15:44

10 CHAPITRE 1. RAISONNEMENT PAR R´ECURRENCE

Correction :

Pour tout entiern?N,onposeH

n n k=0 k=n(n+1) 2. (1)Initialisation :Montrons queH 0 0 k=0 k=0(0 + 1)

2est vraie.

Dune part,

0 k=0 k=0.

D"autre part,

0(0 + 1)

2=0. Donc 0 k=0 k=0(0 + 1) 2etH 0 est vraie. (2)H´er´edit´e:Supposons queH n est vraie pour un certain rangn≥0.

Montrons alors queH

n+1 n+1 k=0 k=(n+1)(n+2)

2est vraie.

n+1 k=0 k= n k=0 k+(n+1)on d´ecoupe notre somme en deuxquotesdbs_dbs1.pdfusesText_1

[PDF] exercice corrigé recherche opérationnelle simplexe

[PDF] exercice corrigé redressement monophasé non commandé

[PDF] exercice corrige redressement simple alternance

[PDF] exercice corrigé redresseur triphasé

[PDF] exercice corrigé reflexe myotatique

[PDF] exercice corrigé reflexe myotatique pdf

[PDF] exercice corrigé relativité restreinte

[PDF] exercice corrigé reproduction humaine

[PDF] exercice corrigé respiration cellulaire

[PDF] exercice corrigé retraitement consolidation

[PDF] exercice corrigé saut en parachute physique

[PDF] exercice corrigé spectre seconde

[PDF] exercice corrigé statique des fluides barrage

[PDF] exercice corrigé statistique descriptive a deux variables

[PDF] exercice corrigé step 7