Colle N°13: Entiers naturels, dénombrement

MPSI du lyc´ee Rabelais http://mpsi.saintbrieuc.free.fr semaine du 3+7 janvier 2012 PROGRAMME DE COLLE S12 NB : seules les d´emonstrations des th´eor`emes, propositions ´etoil´ees ne sont pas exig´ees. ´ENTIERS NATURELS, ENSEMBLES FINIS, DENOMBREMENT Entiers naturels Th´eor`eme.— Th´eor`eme de r´ecurrence —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) est vraie0 ∀n≥ n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥n ), P(n)⇒P(n+1)0 Th´eor`eme*.— Th´eor`eme de r´ecurrence double —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) etP(n +1) sont vraies0 0 ∀n≥n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥ n ), P(n) etP(n+1)⇒P(n+2)0 Corollaire*.— Th´eor`eme de r´ecurrence forte —. SoitP une propri´et´e des ´el´ements de N, et n ∈N.0 • Initialisation : P(n ) est vraie0 ∀n≥ n ,P(n) ⇐⇒0 • H´er´edit´e : (∀n≥n ), P(n ) et ··· et P(n) ⇒P(n+1)0 0 En pratique : pour r´ediger une d´emonstration par r´ecurrence, proc´edez en trois ´etapes : • Initialisation : vous v´erifiezP(n )0 1• H´er´edit´e : soit n≥ n tel que P(n ) est vraie , on montre que P(n+1) est vraie.0 0 • Conclusion : invoquez le principe de r´ecurrence pour conclure. Ensembles finis D´efinition : Soit E un ensemble. On dit que E est fini s’il est en bijection avec un intervalle d’entiers F . L’entiern n, s’il existe est unique. On l’appelle le cardinal de E. On note Card E = n. Th´eor`eme*.— Cardinal des parties —. Soit E un ensemble fini et A∈P(E) une partie de E.