Démonstration par récurrence

icône de pdf
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 nn0, la vérité de Pn entraîne celle de Pn+1, alors on peut conclure que pour tout entier naturel n tel que nn0, 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 nn0, 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 nn0, 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 nn0, 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×2k1=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×2k1=k=11k+1×2k1=2×20=2.

Et, n×2n=2.

Hérédité : Supposons que pour un entier naturel non nul n :

k=1nk+1×2k1=n×2n.

(C’est l’hypothèse de récurrence : HR.)

k=1n+1k+1×2k1=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 :

k=1n+1(k+1)×2k1∑^{n+1}_{k=1}(k+1)\times 2^{k-1}

=k=1n(k+1)×2k1+(n+2)2n= ∑^{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×2k1=n×2n.