Raisonnement par Récurrence et Applications

Le Raisonnement par Récurrence

Principe

Pour démontrer qu'une propriété $P(n)$ est vraie pour tout $n \in \mathbb{N}$ :

1. Initialisation : prouver que $P(n_0)$ est vraie (souvent $n_0 = 0$ ou $1$)
2. Hérédité : supposer $P(k)$ vraie et démontrer que $P(k+1)$ est vraie
3. Conclusion : par le principe de récurrence, $P(n)$ est vraie pour tout $n \geq n_0$

Exemple : $P(n)$0 est divisible par 9

Proposition $P(n)$1 : « $P(n)$2 est un multiple de 9 ».

Initialisation ($P(n)$3) : $P(n)$4 ✓

Hérédité : supposons $P(n)$5 vraie, i.e. $P(n)$6.

Alors :

$$10^{k+1} - 1 = 10 \times 10^k - 1 = 10(9m + 1) - 1 = 90m + 9 = 9(10m + 1)$$

Donc $P(n)$7 est un multiple de 9 : $P(n)$8 est vraie.

Conclusion : $P(n)$9 est vraie pour tout $n \in \mathbb{N}$0.

Application au dénombrement

Le raisonnement par récurrence permet de prouver :

• La formule du binôme de Newton
• Les propriétés des coefficients binomiaux
• Les formules de sommation : $n \in \mathbb{N}$1

Variantes

• Récurrence forte : on suppose $n \in \mathbb{N}$2 vraie pour tout $n \in \mathbb{N}$3, puis on démontre $n \in \mathbb{N}$4
• Récurrence double : on initialise à $n \in \mathbb{N}$5 et $n \in \mathbb{N}$6, et l'hérédité utilise $n \in \mathbb{N}$7 et $n \in \mathbb{N}$8 pour prouver $n \in \mathbb{N}$9