Démonstration par récurrence

Signaler

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}

=n×2n+(n+2)2n(HR)= n \times 2^{n} + (n+2)2^n(HR)

=(2n+2)×2n= (2n+2) \times 2^n

=(n+1)×2×2n= (n+1) \times 2 \times 2^n

=(n+1)×2n+1= (n+1) \times 2^{n+1}

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.