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

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 ...