Méthode N°13: Entiers naturels, dénombrement

Description

MPSI du lyc´ee Rabelais http://mpsi.saintbrieuc.free.fr semaine du 3+28 d´ecembre 2011 ´TECHNIQUES & METHODES S11 NB : cette fiche reprend les techniques n´ecessaires minimales; elle ne constitue donc pas un objectif, mais un pr´erequis! ´ENTIERSNATURELS,DENOMBREMENTS Entiers naturels Pour d´emontrer une propri´et´e universelle des entiers naturels : ∀n≥ n ,P(n)0 on peut toujours proc´eder par r´ecurrence car il s’agit de d´emontrer un ´enonc´e ´equivalent. Pour la r´edaction, il faut ˆetre tr`es rigoureux : La r´ecurrence simple La r´edaction d’une d´emonstration par r´ecurrence s’articule en trois ´etapes : • Initialisation : je v´erifie que P(n ) est vraie.,...0 • H´er´edit´e : ”Soit n≥ n tel que P(n) est vraie. Je montre que P(n+1) est vraie.”...0 • Conclusion : par r´ecurrence, nous avons ´etabli ... La r´ecurrence double La r´edaction d’une d´emonstration par r´ecurrence double s’articule en trois ´etapes : • Initialisation : je v´erifie que P(n ) et P sont vraies,...0 n +10 • H´er´edit´e : ”Soit n≥ n tel que P(n) et P(n+1) sont vraies. Je montre que P(n+2) est vraie.”...0 • Conclusion : d’apr`es le principe de r´ecurrence, nous avons ´etabli ... La r´ecurrence forte La r´edaction d’une d´emonstration par r´ecurrence s’articule en trois ´etapes : • Initialisation : je v´erifie que P(n ) est vraie...0 • H´er´edit´e : ”Soit n≥ n tel que pour tout k ∈ [n ,n]], P(k) est vraie. Je montre que P(n+1) est vraie.”...0 0 • Conclusion : par r´ecurrence forte, nous avons ´etabli ...

Sujets

• Classe préparatoire aux grandes écoles
• Mathématiques, physique et sciences de l'ingénieur
• Public Readiness and Emergency Preparedness Act
• exercices
• Mathématiques

Informations

• Publié par: methode-mpsi
• Nombre de lectures: 44
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

MPSIdulyc´eeRabelaishtt:p//pmisai.sbrntuciere.frf.e

´
TECHNIQUES & METHODES S11

semainedu3+28d´ecembre2011

NB :ecssiaerqieunse´schefittcednerperenhcetselminimales;ellenodeuapcnnocetitsf,tiismanosuecbj!uqsie´ernurp
´
ENTIERS NATURELS, DENOMBREMENTS

Entiers naturels
Pourde´montreruneproprie´te´universelledesentiersnaturels:

∀n≥n0P(n)

onpeuttoujoursproce´derparre´currencecarils’agitded´emontrerune´nonce´e´quivalent.Pourlare´daction,ilfaut
eˆtretre`srigoureux:
Lar´ecurrencesimple
Lare´dactiond’unede´monstrationparr´ecurrences’articuleentrois´etapes:
•Initialisation :´jeueeqifierP(n0) est vraie.,. . .
v
•H´er´edit´e:”Soitn≥n0tel queP(n) est vraie. Je montre queP(n vraie.” . . .+ 1) est
•Conclusion :te´snovasuon,ecn...liaburrer´ecpar
L ´ ence double
a recurr
Lar´edactiond’uned´emonstrationparrecurrencedoubles’articuleentrois´etapes:
´
•Initialisation :jeeuifieqv´erP(n0) etPn0+1sont vraies,. . .
•de´re´ti:´eH”Soitn≥n0tel queP(n) etP(n Je montre que+ 1) sont vraies.P(n . . . est vraie.”+ 2)
•Conclusion :ereipedrincsleprpe`da’..i.´ensbltauon,ovasrrucecne
´
Lar´ecurrenceforte
Lar´edactiond’uned´emonstrationparr´ecurrences’articuleentrois´etapes:
•Initialisation :equeerifijev´P(n0) est vraie. . .
•:´eitedr´´eH”Soitn≥n0tel que pour toutk∈[n0 n]],P(k) est vraie. Je montre queP(n+ 1) est vraie.” . . .
•Conclusion :apucrrrre´fortenceusave,nobate´sno...il
D´nombrement
e
Il existedeux principesselprttee`rtmiss,es`esefficactmorbmeneend´en:
La discussion exclusive de cas

Pourde´nombrerunensemble,jepeuxdistinguerplusieurscasquis’excluentl’unl’autre.Cecirevient`ae´crireEcomme
unere´uniondisjointe
E=E1∪E2∪ ∙ ∙ ∙ ∪Ep
Danscecas,vouspouvezconclureeninvoquantl’additivite´ducardinalque

CardE=Card(E1) +Card(E2) +∙ ∙ ∙+Card(Ep)
Enpratique,jer´edigececicommeunediscussionexclusivedecas:
◮Cas 1soit (exclusif)x∈E1
◮Cas 2soit (exclusif)x∈E2



.
Cas psoit (exclusif)x∈Ep

Au total,Card(E) =Card(E1) +Card(E2) +∙ ∙ ∙+Card(Ep).
Le principe du berger

Card(E1)possibilites
´
Card(E2)psoisiblit´es

Card(Ep)osepsbti´slii

Pourd´enombrerunensemble,jepeuxaussid´ecrirelese´tapesquime`nent`alaconstructiond’une´l´ementdeE:
´
Etape 1oisijechaleuslavrepudrimerrcree`tin1ospbisit´lise
´
Etape 2sislavaleurdudeuxi`emecrit`eejrhecion2psoisibil´tse

.
´Epetapje choispi`meit`ecrrenpil´tisibsepos
is la valeur due
Sieloneetsahca`se´pate´euqpoderembitilibsspeneadtnni´ddutatr´esuldel’´e,e´cetnedpate´rpeles nombres de
possibilite´sa`chaquee´tapesemultiplient.

Au total, il y an1×n2× ∙ ∙ ∙ ×npf ¸
aconsdeconstruireune´l´ementdeE. Donc
CardE=n1×n2× ∙ ∙ ∙ ×np
1

1.

2.

Analyse combinatoire
Pouraborderunexerciced’analysecombinatoire,jepense`a
tenterdereconnaˆıtreundesmod`elescanoniques. Je me pose les questions simples suivantes :
–eetsrigadrnoi-oln´e?etl
–opnse?utitiyeapv´oeitr-irl´
`
Apartirdecesdeuxquestions,jed´eterminevdansquellesituationjemetrouvevis-a-visdesmod`elescanoniques
en me reportant au tableau suivant :

choix depobjets parmin
´
avecre´petition
sans repetition
´ ´

ordonne´
np
Apn

non ordo ´
nne
? ?
n

Remarque :Il est parfois utile de penser en termes d’applications,
J’adopte le point de vue pertinent !.

ou de suites ou bien

encore de listes

Lorsqu’aucunneconvient,ilfautalorspassera`l’e´tapesuivante:
utiliserlesformulesdud´enombrement
–comple´mentaire(pourles”aumoinsunroi...)
”
–r´euniondisjointe(pourlesdiscussionsexclusivesdecas”soitilya3roissoitilya4rois”)
Jefaisunediscussionexclusivedecaset`alafin:
{tout}=XCard{cas possibles}
diff´erentscas

Card

–produitcarte´sien
Si rien de tout cela, ne semble fonctionner, j’utilise leprincipe des bergers
Coefficients du binˆme
o
Troisme´thodesded´emonstrationpourlesformulesaveclescoefficientsdubinˆome
Ilyatroisstrat´egiespourd´emontreruneformulemettantenjeudescoefficientsbinomiaux:
– la preuve parrecurrence,
´
– un raisonnement deeremtnde´onbm,
– l’utilisation de laformule du binome.
ˆ

2

...