Méthodologie du Raisonnement par Récurrence

Principe et Axiome

Le raisonnement par récurrence est un pilier de l'arithmétique. Fondé sur les axiomes de Peano, il stipule que si une propriété se transmet d'un rang au suivant et est vérifiée initialement, elle appartient à tout l'ensemble $\mathbb{N}$.

Analogie des dominos : faire tomber le premier ($n_0$) garantit la chute de tous les suivants si chaque domino fait tomber son successeur.

Étapes de la démonstration

1. Initialisation : Vérifier que $P_{n_0}$ est vraie.
2. Hérédité : Supposer $P_k$ vraie pour un entier $k \ge n_0$. Démontrer alors que $P_{k+1}$ est vraie.

Exemple : Somme des cubes

Montrons que $\forall n \in \mathbb{N}^*$ :

$$1^3 + 2^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$

Initialisation : Pour $$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$0 : $$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$1 et $$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$2. ✓

Hérédité : Supposons $$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$3 vraie. Alors :

$$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$

$$= (k+1)^2 \cdot \frac{k^2 + 4k + 4}{4} = \frac{(k+1)^2(k+2)^2}{4} = \left(\frac{(k+1)(k+2)}{2}\right)^2$$

L'expression obtenue est bien $$\sum_{i=1}^{k+1} i^3 = \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = (k+1)^2\left(\frac{k^2}{4} + (k+1)\right)$$4. La propriété est héréditaire. ✓