[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 deux =n(n+1)

2+(n+1)

par hypoth`ese de r´ecurrence =n(n+1)

2+2(n+1)2

mise au mˆeme d´enominateur =(n+1)(n+2) 2 en factorisant par (n+1) 2

AinsiH

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

1.3.2 Avec une suite

Exercice :

On d´efinit la suite suivante pour tout entiern?N:? ?u 0 =0 u n+1 =1 2u n +2, ainsi que la fonctionf(x)=1

2x+2surR.

1. D´eterminer les variations de la fonctionfsurR.

9782340-020054_001_192.indd 109782340-020054_001_192.indd 1010/07/2017 15:4410/07/2017 15:44

1.3. D"AUTRES EXEMPLES CLASSIQUES 11

2. D´emontrer que la suite (u

n ) est croissante.

Correction :

Dans un premier temps, on remarque que la fonctionfn"est pas l`apar hasard. En effetf(u n )=1 2u n +2=u n+1 . C"est donc cette fonction qui est le lien entre le rangnet le rangn+ 1, elle nous aidera donc `a passer l"h´er´edit´e.

1. En premi`ere, une m´ethode efficace pour d´eterminer les variations d"une

fonction est le calcul de la fonction d´eriv´ee, puis l"´etude de son signe. Ici on peut faire encore plus rapide, puisque la fonctionfest une fonction affine dont le coefficient directeur1

2est positif. Rappelons que les fonc-

tions aαnes sont repr´esent´ees graphiquement par une droite et que cette fonction aαne sera donc croissante surR. fest donc croissante surR.

2. La m´ethode qu"il ne faut jamais oublier lorsque l"on pose cette question,

repose directement sur la d´efinition; c"est montrer queu n+1 ≥u n pour tout entiern?Nce qui revient parfois `amontrerqueu n+1 -u n ≥0. C"est la seule qui ne n´ecessite aucune condition particuli`ere, et toujours la premi`ere `av´erifier. La r´ecurrence appelant la r´ecurrence....

Pour tout entiern?N,onpose:H

n :u n+1 ≥u n (1)Initialisation :Montrons queH 0 :u 1 ≥u 0 est vraie.

D"une part,u

0 =0,pard´efinition.

D"autre,u

1 =1 2u 0 +2=2.

Donconabienu

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

Montrons alors queH

n+1 :u n+2 ≥u n+1 est vraie. u n+1 ≥u n par hypoth`eseder´ecurrence ?f(u n+1 )≥f(u n )car la fonctionfest croissante surR orf(u n+1 )=u n+2 etf(u n )=u n+1 ,onaalors:u n+2 ≥u n+1 DoncH n+1 est vraie. Par le principe du raisonnement par r´ecurrence, H n est vraie pour tout entiern?N. Ainsi (u n ) est croissante.

D´etaillons un peu ...

9782340-020054_001_192.indd 119782340-020054_001_192.indd 1110/07/2017 15:4410/07/2017 15:44

12 CHAPITRE 1. RAISONNEMENT PAR R´ECURRENCE

Pour linitialisation, rien de particulier, on calculeu 1 etu 0 ,oncompare, tout se passe bien. Pour l"h´er´edit´e, cette fois on commence par exposer l"hypoth`ese de r´ecurrence. C"est ce que l"on fera toujours ou presque dans ce type d"exercice. On applique ensuite la fonctionfqui est le lien entre le rang net le rangn+ 1 et donc a fortiori entre le rangn+1etlerangn+2. Il est bon de rappeler que lorsque l"on applique une fonction sur une in´egalit´e, il faut maitriser, non pas le signe, mais les variations de la fonction appliqu´ee. Ici,fest croissante surR, elle conserve donc le sens de l"in´egalit´e, l`ao`u une fonction d´ecroissante l"aurait renvers´e.

1.3.3 En arithm´etique

Exercice :

D´emontrer que pour tout entiern?N,3

2n -2 n est divisible par 7. Remarque :Il faut dans un premier temps dire que 3 2n -2 n est divisible par 7 signifie qu"il existe un entierk?Ztel que 3 2n -2 n =7k.

Correction

(1)Initialisation :Montrons queH 0 :3

2×0

-2 0 est divisible par 7, est vraie. 3

2×0

-2 0 =3 0 -2 0 =1-1=0=7×0. DoncH 0 est vraie. (2)H´er´edit´e:Supposons queH n est vraie pour un certain rangn≥0.

Montrons alors queH

n+1 :3

2(n+1)

-2 n+1 est divisible par 7, est vraie.

Si l"on suppose queH

n est vraie, alors il existe un entierk?Ztel que 3 2n -2 n =7k.

Le but est de r´eussir `a´ecrire 3

2(n+1)

-2 n+1 =7k aveck ?Z. 3

2(n+1)

-2 n+1 =3 2n+2 -2×2 nquotesdbs_dbs32.pdfusesText_38

[PDF] controle recurrence ts

[PDF] dm de maths terminale s recurrence

[PDF] calculer u1 et u2 la suite un est elle arithmétique géométrique

[PDF] ds suites arithmétiques et géométriques 1ere s

[PDF] controle sur les suites terminale s

[PDF] controle variations suites 1ere s

[PDF] la tension electrique exercice

[PDF] tension electrique 4eme cours

[PDF] controle sur candide corrigé

[PDF] expliquer le titre candide ou l'optimisme

[PDF] l'union européenne 3ème brevet

[PDF] les contrastes territoriaux ? l'intérieur de l'union européenne

[PDF] identifier et décrire une forme de contraste de l'espace européen

[PDF] l'union européenne une union d'états cours 3ème

[PDF] les différents types d'espaces dans l'ue croquis