Raisonnement par récurrence et démonstrations de Terminale

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• **Schéma logique** : Initialisation Hérédité (P(k) P(k+1)) Validité universelle pour tout n n_0. • En arithmétique, la récurrence est fréquemment employée pour établir des formules de divisibilité : par exemple, prouver que 3^2n - 1 est divisible par 8.

Le cours

1. Principe de récurrence Pour démontrer qu'une propriété P(n) est vraie pour tout entier n n_0, il suffit d'établir deux points : Initialisation : P(n_0) est vraie ; Hérédité : pour un entier k n_0 fixé quelconque, si P(k) est vraie (hypothèse de récurrence), alors P(k + 1) est vraie. On conclut alors : par récurrence, P(n) est vraie pour tout n n_0. C'est l'effet « dominos » : le premier tombe, et chacun fait tomber le suivant. 2. Méthode en arithmétique : divisibilité 1. Traduire l'hypothèse avec la définition : A_k = d m avec m Z. 2. Écrire A_k+1 en fonction de A_k, par exemple A_k+1 = a A_k + c. 3. Remplacer A_k par dm et factoriser par d. Mini-exemple : avec A_n = 5^n - 1, on a A_k+1 = 5 5^k - 1 = 5(5^k - 1) + 4 = 5A_k + 4. Si A_k = 4m, alors A_k+1 = 20m + 4 = 4(5m + 1) : la divisibilité par 4 se transmet. 3. Attention : l'initialisation est indispensable La propriété « 4^n + 1 est un multiple de 3 » est héréditaire, car 4^k+1 + 1 = 4(4^k + 1) - 3. Pourtant elle est fausse pour tout n : 4^0 + 1 = 2, 4^1 + 1 = 5. Sans initialisation, l'hérédité ne prouve rien.

Dans ce chapitre