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 : $10^n - 1$ est divisible par 9

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

Initialisation ($n = 0$) : $10^0 - 1 = 0 = 9 \times 0$ ✓

Hérédité : supposons $P(k)$ vraie, i.e. $\exists m \in \mathbb{Z},\; 10^k - 1 = 9m$.

Alors :

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

Donc $10^{k+1} - 1$ est un multiple de 9 : $P(k+1)$ est vraie.

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

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 : $\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$

Variantes

• Récurrence forte : on suppose $P(j)$ vraie pour tout $j \leq k$, puis on démontre $P(k+1)$
• Récurrence double : on initialise à $n_0$ et $n_0 + 1$, et l'hérédité utilise $P(k)$ et $P(k+1)$ pour prouver $P(k+2)$