Terminale générale Mathématiques Combinatoire et dénombrement

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 $n_{0}$ un entier naturel et soit $P_{n_{0}}$ , $P_{n_{0} + 1}$ , $P_{n_{0} + 2}$ , …, $P_{n}$ , $\dots$ une suite de propositions.

Si la $P_{n_{0}}$ est vraie et si, pour n'importe quel entier naturel $n$ tel que $n \geq$ $n_{0}$ , la vérité de $P_{n}$ entraîne celle de $P_{n + 1}$ , alors on peut conclure que pour tout entier naturel $n$ tel que $n \geq n_{0}$ , $P_{n}$ est vraie.

À noter

Dans la grande majorité des cas, $n_{0}$ vaut $0$ ou $1$ .

II La démonstration par récurrence

1 Mise en œuvre

Soit $n_{0}$ un entier naturel. Pour démontrer par récurrence qu'une proposition $P_{n}$ est vraie pour tout entier $n \geq n_{0}$ , on procède en deux étapes qui permettront de conclure :

l'initialisation pour vérifier que la proposition $P_{n_{0}}$ est vraie ;

l'hérédité montrant que si la proposition $P_{n}$ est vraie pour un entier naturel $n$ quelconque tel que $n \geq n_{0}$ , alors la proposition $P_{n + 1}$ doit être également vraie.

Le principe de récurrence permettra alors de conclure que pour tout entier naturel $n$ tel que $n \geq n_{0}$ , la proposition $P_{n}$ est vraie.

À noter

Lors de la seconde étape, on suppose la proposition $P_{n}$ 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 « $10^{n} + {(- 1)}^{n}$ est un multiple de 11 » est héréditaire, puisque $10^{n + 1} + {(- 1)}^{n + 1} = 10 (10^{n} + {(- 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 :

$\sum_{k = 1}^{n} (k + 1) \times 2^{k - 1} = n \times 2^{n}$ .

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$ ,

$\begin{matrix} \sum_{k = 1}^{n} (k + 1) \times 2^{k - 1} = \sum_{k = 1}^{1} (k + 1) \times 2^{k - 1} \\ = 2 \times 2^{0} = 2 . \end{matrix}$

Et, $n \times 2^{n} = 2$ .

La proposition est donc vraie au rang 1.

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

$\sum_{k = 1}^{n} (k + 1) \times 2^{k - 1} = n \times 2^{n} .$

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

$On veut en déduire que \sum_{k = 1}^{n + 1} (k + 1) \times 2^{k - 1} = (n + 1) \times 2^{n + 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 :

$\begin{matrix} \sum_{k = 1}^{n + 1} (k + 1) \times 2^{k - 1} = \sum_{k = 1}^{n} (k + 1) \times 2^{k - 1} + (n + 2) 2^{n} \\ = n \times 2^{n} + (n + 2) 2^{n} (HR) \\ = (2 n + 2) \times 2^{n} \\ = (n + 1) \times 2 \times 2^{n} \\ = (n + 1) \times 2^{n + 1} . \end{matrix}$

La propriété est donc héréditaire.

Conclusion : Le principe de récurrence permet de conclure que :

$\forall n \in ℕ^{*}, \sum_{k = 1}^{n} (k + 1) \times 2^{k - 1} = n \times 2^{n} .$

Démonstration par récurrence

I Le principe de récurrence

À noter

II La démonstration par récurrence

1 Mise en œuvre

À noter

2 Quelques pièges à éviter

Méthode

Démontrer une égalité

Conseils

Solution

Conseils

Pour lire la suite