Une démonstration par récurrence consiste à démontrer qu’une infinité de propositions dépendantes d’un entier naturel n sont vraies.
I. Le principe de récurrence
Soit n0 un entier naturel et soit Pn0, Pn0+1, Pn0+2, …, Pn, … une suite de propositions.
Si la Pn0 est vraie et si, pour n’importe quel entier naturel n tel que n≥n0, la vérité de Pn entraîne celle de Pn+1, alors on peut conclure que pour tout entier naturel n tel que n≥n0, Pn est vraie.
À noter
Dans la grande majorité des cas, n0 vaut 0 ou 1.
II. La démonstration par récurrence
1) Mise en œuvre
Soit n0 un entier naturel. Pour démontrer par récurrence qu’une proposition Pn est vraie pour tout entier n≥n0, on procède en deux étapes qui permettront de conclure :
l’initialisation pour vérifier que la proposition Pn0 est vraie ;
l’hérédité montrant que si la proposition Pn est vraie pour un entier naturel nquelconque tel que n≥n0, alors la proposition Pn+1 doit être également vraie.
Le principe de récurrence permettra alors de conclure que pour tout entier naturel n tel que n≥n0, la proposition Pn est vraie.
À noter
Lors de la seconde étape, on suppose la proposition Pn vraie pour un certain rang n : c’est l’hypothèse de récurrence, souvent notée HR.
2) Quelques pièges à éviter
Oublier l’initialisation : par exemple la proposition « 10n+(−1)n est un multiple de 11 » est héréditaire, puisque 10n+1+(−1)n+1=10(10n+(−1)n)−11(−1)n, mais elle est fausse pour tout entier n.
Supposer, pour montrer l’hérédité, que la proposition est vraie pour tout entier naturel n, puisque c’est ce que l’on veut justement démontrer !
On supposera donc la proposition vraie pour un entier naturel.
Méthode
Démontrer une égalité
Démontrer par récurrence que pour tout entier n strictement positif :
∑k=1nk+1×2k−1=n×2n.
Conseils
Lorsque l’on exprime la propriété au rang n+1, il faut penser à remplacer « tous les n » par des « n+1 ». Pour la notation Σ, se référer au mémo visuel.
Solution
Initialisation : Pour n=1,
∑k=1nk+1×2k−1=∑k=11k+1×2k−1=2×20=2.
Et, n×2n=2.
Hérédité : Supposons que pour un entier naturel non nul n :
∑k=1nk+1×2k−1=n×2n.
(C’est l’hypothèse de récurrence : HR.)
∑k=1n+1k+1×2k−1=n+1×2n+1.
Conseils
Lors de cette étape, tout d’abord, établissez un lien entre les propositions aux rangs n et n+1, puis utilisez l’hypothèse de récurrence.
On a :
∑^{n+1}_{k=1}(k+1)\times 2^{k-1}
= ∑^{n}_{k=1}(k+1)\times2^{k-1}+(n+2)2^{n}
La propriété est donc héréditaire.
Conclusion : Le principe de récurrence permet de conclure que :
∀n∈ℕ*, ∑k=1nk+1×2k−1=n×2n.