Introduction
Le raisonnement par récurrence doit être considéré comme un véritable guide de rédaction. Celui-ci doit être suivi scrupuleusement
et rédigé soigneusement. Cela n’empêche pas que le cas échéant la
rédaction puisse être rapide et synthétique.
Voici quelques situations typiques où on fait un raisonnement par
récurrence qui ne présente aucune difficulté :
• (§ 4.2.4) Soit A ∈ M 3 (R), X n ∈ M 3,1 (R) telles que
∀n ∈ N, X n+1 = AX n . On montre alors par récurrence :
∀n ∈ N, X n = A
n X n
• (§ 2.3) Soit (u n ) n∈N une suite telle que ∀n ∈ N, u n+1 = f (u n ), et
u 0 = a, avec a tel que f (a) = a. On montre alors par récurrence :
∀n ∈ N u n = a
• Pour établir l’hérédité, il faut souvent utiliser une idée ou une propriété
mise en évidence dans une question précédente. C’est le cas pour le
premier exemple ci-dessus (la propriété qui permet d’établir l’hérédité
est X n+1 = AX n ), et d’une manière tout à fait typique pour l’étude de
suites récurrentes grâce à la formule des accroissements finis (cf § 2.3.3 ).
• Le raisonnement par récurrence est susceptible de nombreuses variations : l’initialisation peut être faite avec n = 1. L’hérédité permet de
passer de n − 1 à n (n ∈ N
∗ ). . .
Parfois l’initialisation devra porter sur les propriétés P (0) , P (1) , P (2),
par exemple, et pour obtenir l’hérédité on supposera qu’il existe n ∈ N
tel que P (n) , P (n + 1) , P (n + 2) sont vraies (récurrence sur plusieurs
générations). Ou bien on supposera qu’il existe n ∈ N tel que, pour tout
k ∈ {0 ; · · · ; n}, P (k) est vraie (récurrence forte).
Raisonnement par contraposée
La contraposée de la propriété P ⇒ Q est la propriété non Q ⇒ non P.
Elles sont logiquement équivalentes, et pour établir une implication, il
peut être plus commode d’établir sa contraposée.
Pour montrer qu’un polynôme de degré n 1 admet au plus n racines,
on démontre la contraposée : un polynôme admettant plus de n racines
n’est pas de degré n. Voir le § 6 de cette introduction.
Ne pas confondre contraposée et réciproque : la réciproque de la propriété P ⇒ Q est la propriété Q ⇒ P : la réciproque d’une implication
vraie peut être fausse.
8
Le raisonnement par récurrence doit être considéré comme un véritable guide de rédaction. Celui-ci doit être suivi scrupuleusement
et rédigé soigneusement. Cela n’empêche pas que le cas échéant la
rédaction puisse être rapide et synthétique.
Voici quelques situations typiques où on fait un raisonnement par
récurrence qui ne présente aucune difficulté :
• (§ 4.2.4) Soit A ∈ M 3 (R), X n ∈ M 3,1 (R) telles que
∀n ∈ N, X n+1 = AX n . On montre alors par récurrence :
∀n ∈ N, X n = A
n X n
• (§ 2.3) Soit (u n ) n∈N une suite telle que ∀n ∈ N, u n+1 = f (u n ), et
u 0 = a, avec a tel que f (a) = a. On montre alors par récurrence :
∀n ∈ N u n = a
• Pour établir l’hérédité, il faut souvent utiliser une idée ou une propriété
mise en évidence dans une question précédente. C’est le cas pour le
premier exemple ci-dessus (la propriété qui permet d’établir l’hérédité
est X n+1 = AX n ), et d’une manière tout à fait typique pour l’étude de
suites récurrentes grâce à la formule des accroissements finis (cf § 2.3.3 ).
• Le raisonnement par récurrence est susceptible de nombreuses variations : l’initialisation peut être faite avec n = 1. L’hérédité permet de
passer de n − 1 à n (n ∈ N
∗ ). . .
Parfois l’initialisation devra porter sur les propriétés P (0) , P (1) , P (2),
par exemple, et pour obtenir l’hérédité on supposera qu’il existe n ∈ N
tel que P (n) , P (n + 1) , P (n + 2) sont vraies (récurrence sur plusieurs
générations). Ou bien on supposera qu’il existe n ∈ N tel que, pour tout
k ∈ {0 ; · · · ; n}, P (k) est vraie (récurrence forte).
Raisonnement par contraposée
La contraposée de la propriété P ⇒ Q est la propriété non Q ⇒ non P.
Elles sont logiquement équivalentes, et pour établir une implication, il
peut être plus commode d’établir sa contraposée.
Pour montrer qu’un polynôme de degré n 1 admet au plus n racines,
on démontre la contraposée : un polynôme admettant plus de n racines
n’est pas de degré n. Voir le § 6 de cette introduction.
Ne pas confondre contraposée et réciproque : la réciproque de la propriété P ⇒ Q est la propriété Q ⇒ P : la réciproque d’une implication
vraie peut être fausse.
8