Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TS Raisonnement par récurrence 1 Une histoire de plomberie Imaginons un immeubl

TS Raisonnement par récurrence 1 Une histoire de plomberie Imaginons un immeuble (mathématique) très vétuste dans lequel il peut y avoir des problèmes de fuite d’eau. Cet immeuble a un nombre inﬁni d’appartements situés les uns en- dessous des autres, et l’appartement le plus en haut a pour étage 0. L’immeuble est tellement vétuste que les parois séparant deux appar- tements successifs sont poreuses et, si un appartement a une fuite d’eau, alors celui d’en-dessous aussi (la fuite se répercute à l’apparte- ment de dessous). Appelons cette propriété la porosité. On se demande si tous les appartements ont une fuite d’eau. 0 1 ··· n n +1 ··· Notons, pour n ∈N, Pn la propriété "l’appartement de l’étage n a une fuite d’eau". On sait que si un appartement n quelconque a une fuite d’eau alors, par porosité, l’ap- partement n +1 a aussi une fuite d’eau (mais attention : rien ne nous permet d’afﬁrmer que l’appartement n a effectivement une fuite d’eau, c’est juste que si c’est le cas, alors l’appartement n + + +1 d’en-dessous aura aussi une fuite d’eau). On dit que la propriété Pn est héréditaire : la réalisation de Pn entraine la réalisation de Pn+1, c’est-à-dire ∀n ∈N , Pn ⇒Pn+1 . Regardons maintenant l’appartement 0 : On envoie un plombier dans l’appartement 0 et il constate (malheur ! !) qu’il y a effective- ment une fuite d’eau. Autrement dit P0 est vraie , on dit que la récurrence est initialisée. Concluons : L’appartement 0 a une fuite d’eau (P0 est vraie). Donc, par hérédité, l’appartement 1 aussi (P1 est vraie). Donc l’appartement 2 aussi (P2 est vraie)... ...etc... Au ﬁnal, tous les appartements ont une fuite d’eau : ∀n ∈N , Pn est vraie . C’est ça le principe de récurrence (exemple à méditer longuement...). maths.muller@gmail.com RÉCURRENCE 1/5 2 Principe de récurrence Le raisonnement par récurrence est un nouveau type de raisonnement qui est très puis- sant pour démontrer des propriétés qui portent sur des nombres entiers naturels. En effet l’ensemble N des entiers naturels a trois propriétés fondamentales (axiomes de Peano) : 1) N admet un plus petit élément : 0 2) Tout entier n ∈N admet un unique successeur : n +1 3) Si un ensemble contient 0 et les successeurs de chacun de ses éléments, alors cet ensemble est N. Ces propriétés permettent d’obtenir tous les entiers naturels : On part de 0 (le plus petit entier). 0 a un successeur : 0+1 = 1. 1 a un successeur : 1+1 = 2. 2 a un successeur : 2+1 = 3. etc... à partir de chaque entier n trouvé, on peut construire le suivant : n a un successeur : n +1. En répétant cette opération indéﬁniment, on obtient tous les entiers. Le principe de récurrence est basé sur cette idée : Propriété 2.1 (Principe de récurrence) On cherche à démontrer que, pour tout n ∈N, une propriété Pn (qui dépend donc de la valeur de n) est vraie. Si : • P0 est vraie (initialisation) • ∀n ∈N , Pn ⇒Pn+1 (hérédité) Alors, d’après le principe de récurrence, ∀n ∈N , Pn est vraie. Remarque 2.1 • En fait, lorsqu’on doit montrer une propriété Pn pour tout n ∈N, on doit montrer une inﬁnité de propriétés : P0, P1, P2,... • On n’est pas obligé d’initialiser la récurrence à 0. Tout entier n0 peut convenir. • Le principe de démonstration par récurrence suit toujours le plan suivant : On note, pour n ⩾n0, Pn la propriété qu’on cherche à démontrer. 1) Initialisation : on montre que Pn0 est vraie. En principe c’est immédiat et demande très peu de calculs, encore faut-il le faire... 2) Hérédité : on suppose que Pn est vraie pour un certain n ⩾n0 quelconque (c’est l’hypothèse de récurrence, HR) et on montre qu’alors Pn+1 est vraie. C’est l’étape délicate, il faut trouver un lien qui permet de passer de Pn à Pn+1. 3) Conclusion : on conclue en utilisant le principe de récurrence. • On pensera à utiliser une démonstration par récurrence lorsqu’un énoncé débute par : "Montrer que pour tout n ∈ ∈ ∈N,..." maths.muller@gmail.com RÉCURRENCE 2/5 3 Exemples Exemple 3.1 (Somme des n premiers nombres entiers non nuls) Énoncé : Soit, pour n ∈N∗, Sn = n X k=1 k = 1+2+...+n. Montrer que pour tout n ∈N∗, Sn = n(n +1) 2 . Solution : Soit, pour n ∈N∗, Pn la propriété "Sn = n(n +1) 2 ". 1) Initialisation : Pour n = 1, P1 est la propriété "S1 = 1(1+1) 2 ". On a : S1 = 1 X k=1 k = 1 et 1(1+1) 2 = 1×2 2 = 1. On a donc bien S1 = 1(1+1) 2 et P1 est donc vraie. Donc la récurrence est initialisée. 2) Hérédité : Supposons que pour un certain n ∈N∗, Pn est vraie et montrons qu’alors Pn+1 est vraie : HR : Sn = 1+2+...+n = n(n +1) 2 À montrer : Sn+1 = 1+2+...+(n +1) = (n +1)(n +2) 2 (on remplace n par n +1) On a : 1+2+...+(n +1)=1+2+...+n | {z } par HR + (n +1) = z }| { n(n +1) 2 + (n +1) (on réinjecte l’hypothèse de récurence) =n(n +1)+2(n +1) 2 (petit calcul de fractions basique) 1+2+...+(n +1)=(n +1)(n +2) 2 (factorisation par (n +1)) C’est ce qu’on voulait. La propriété est donc bien héréditaire. 3) Conclusion : • P0 est vraie (la récurrence est initialisée). • ∀n ∈N∗,Pn ⇒Pn+1 (la propriété est héréditaire). Donc d’après le principe de récurrence, ∀n ∈N∗, Pn est vraie. maths.muller@gmail.com RÉCURRENCE 3/5 Exemple 3.2 (Étude d’une suite bornée) Énoncé : Soit (un) la suite déﬁnie par : ½ u0 =0 un+1=pun +5 , pour n ∈N Montrer que, pour tout n ⩾1, 0 < un < 3. Solution : Soit, pour n ⩾1, Pn : "0 < un < 3". 1) Initialisation : u1 = p u0 +5 = p 5 et 0 < p 5 < 3. On a bien 0 < u1 < 3, donc P1 est vraie. La récurrence est donc initialisée. 2) Hérédité : Supposons Pn vraie pour un certain n ⩾1, et montrons que Pn+1 est vraie : HR : 0 < un < 3 À montrer : 0 < un+1 < 3 On a : un+1 = p un +5 Idée : on va chercher à reconstruire un+1 à partir de un HR : 0 < un < 3 ⇒5 < un +5 < 8 ⇒ p 5 < p un +5 < p 8 (car x 7→ p x est croissante sur R+) ⇒ p 5 < un+1 < p 8 ⇒0 < p 5 < un+1 < p 8 < 3 (car 0 < p 5 et p 8 < 3) ⇒0 < un+1 < 3 3) Conclusion : On a vériﬁé l’initialisation et l’hérédité donc, d’après le principe de récurrence, Pn est vraie pour tout n ⩾1 : ∀n ⩾1 , 0 < un < 3 maths.muller@gmail.com RÉCURRENCE 4/5 Exemple 3.3 (Étude d’une dérivée) Énoncé : Soit, pour n ∈N∗, fn la fonction déﬁnie sur R par fn(x) = xn. Montrer que pour tout n ∈N∗, fn est dérivable sur R et que, pour tout réel x, f ′ n(x) = nxn−1. Solution : Soit, pour n ∈N∗, Pn la propriété : "fn est dérivable et, pour tout x ∈R, f ′ n(x) = nxn−1". 1) Initialisation : On a, pour tout x ∈R, f1(x) = x1 = x. f1 est dérivable et, pour x ∈R, f ′ 1(x) = 1 = 1x0. Donc P1 est vraie. 2) Hérédité : Supposons Pn vraie pour un certain n ⩾1, et montrons que Pn+1 est vraie : HR : fn est dérivable et, pour tout x ∈R, f ′ n(x) = nxn−1 À montrer : fn+1 est dérivable et, pour tout x ∈R, f ′ n+1(x) = (n +1)xn On a, pour x ∈R, fn+1(x) = xn+1 = x × xn = x fn(x). La fonction x 7→x est dérivable (de dérivée égale à 1) sur R et, par HR, fn est dérivable sur R. Donc par dérivation d’un produit, fn+1 est dérivable sur R et, pour tout x ∈R : f ′ n+1(x) = 1× fn(x)+ x × f ′ n(x) = xn + x ×nxn−1 (par HR) = xn +nxn f ′ n+1(x) = (n +1)xn Donc, pour tout n ∈N∗, Pn ⇒Pn+1. 3) Conclusion : On a vériﬁé l’initialisation et l’hérédité donc, d’après le principe de récurrence, Pn est vraie pour tout n ∈N∗. maths.muller@gmail.com RÉCURRENCE 5/5 uploads/Philosophie/ ts-cours-recurrence.pdf