par sos-math(21) » dim. 23 nov. 2014 21:22
La démonstration par récurrence est une méthode de démonstration particulière pour des propriétés qui dépendent d'un entier naturel n.
Si on considère une "formule" P(n) qui dépend d'un entier naturel n et qu'on veut montrer que P(n) est vraie pour tout n.
1) On montre que P(0) (ou P(1)) est vraie, c'est-à-dire qu'on vérifie qu'en remplaçant n par 0 (ou 1) dans la formule, celle-ci est vraie. C'est l'initialisation ;
2) On se place à un entier n quelconque fixé et on suppose que P(n) est vraie. Il faut ensuite obtenir par des calculs, d'autres propriétés que P(n+1) est vraie.
Cette étape est le corps de la récurrence, on l'appelle l'hérédité (qui signifie bien transmettre quelque chose.
3) On conclut : pour tout entier n, P(n) est vraie.
Par exemple montrons par récurrence sur \(n\geq 1\) la propriété P(n) : "\(2^n\geq n\)" ;
1) initialisation : \(2^1=2\geq 1\) donc la propriété P(1) : \(2^1\geq 1\) est vérifiée.
2) hérédité : soit un entier \(n\geq 1\) quelconque fixé tel que P(n) soit vraie. Alors on a \(2^n\geq n\).
On essaie de comparer \(2^{n+1}\) en écrivant que \(2^{n+1}=2^n\times 2\) or comme \(2^n\geq n\), on a \(2^{n+1}\geq n\times 2\geq n+1\) (le double d'un entier \(n\geq 1\) est toujours supérieur à son suivant)
On a donc obtenu l'inégalité avec des n+1 à la place des n donc P(n+1) est vraie et l'hérédité est prouvée.
3) On conclut : pour tout entier \(n\geq 1\), P(n) est vraie : "\(2^n\geq n\).
Est-ce plus clair ?
La démonstration par récurrence est une méthode de démonstration particulière pour des propriétés qui dépendent d'un entier naturel n.
Si on considère une "formule" P(n) qui dépend d'un entier naturel n et qu'on veut montrer que P(n) est vraie pour tout n.
1) On montre que P(0) (ou P(1)) est vraie, c'est-à-dire qu'on vérifie qu'en remplaçant n par 0 (ou 1) dans la formule, celle-ci est vraie. C'est l'initialisation ;
2) On se place à un entier n quelconque fixé et on suppose que P(n) est vraie. Il faut ensuite obtenir par des calculs, d'autres propriétés que P(n+1) est vraie.
Cette étape est le corps de la récurrence, on l'appelle l'hérédité (qui signifie bien transmettre quelque chose.
3) On conclut : pour tout entier n, P(n) est vraie.
Par exemple montrons par récurrence sur [tex]n\geq 1[/tex] la propriété P(n) : "[tex]2^n\geq n[/tex]" ;
1) initialisation : [tex]2^1=2\geq 1[/tex] donc la propriété P(1) : [tex]2^1\geq 1[/tex] est vérifiée.
2) hérédité : soit un entier [tex]n\geq 1[/tex] quelconque fixé tel que P(n) soit vraie. Alors on a [tex]2^n\geq n[/tex].
On essaie de comparer [tex]2^{n+1}[/tex] en écrivant que [tex]2^{n+1}=2^n\times 2[/tex] or comme [tex]2^n\geq n[/tex], on a [tex]2^{n+1}\geq n\times 2\geq n+1[/tex] (le double d'un entier [tex]n\geq 1[/tex] est toujours supérieur à son suivant)
On a donc obtenu l'inégalité avec des n+1 à la place des n donc P(n+1) est vraie et l'hérédité est prouvée.
3) On conclut : pour tout entier [tex]n\geq 1[/tex], P(n) est vraie : "[tex]2^n\geq n[/tex].
Est-ce plus clair ?
