Induction ou raisonnement par récurrence

Définition

L’induction, aussi appelée raisonnement par récurrence, est une méthode de preuve. Elle sert à démontrer qu’un énoncé est vrai peu importe le nombre entier naturel utilisé.

Exemple

La somme des nombres entiers de 1 à pour n’importe quel nombre naturel $n$  est donnée par la formule :

$1+2+\cdots+n=\frac{n(n+1)}{2}$ 

Vérification de la formule pour certaines valeurs de $n$  :

Pour $n=5\ ∶\$

$1+2+3+4+5=15=\frac{5\cdot6}{2}$

Pour $n=10\ :$

$1+2+3+\cdots+10=55=\frac{10\cdot11}{2}$

Il n’est pas possible de vérifier la formule pour toutes les valeurs de $n$ . L’induction garantit que la formule est toujours valable, pour n’importe quel nombre entier naturel $n.$ 

Idée

L’idée est de vérifier que l’énoncé en question est vrai pour la ou les premières valeurs entières concernées (généralement $0$ ou $1$ ). Puis, on montre que si l’énoncé est vrai pour un certain $n$ , alors il est nécessairement vrai pour $n+1$ .

MÉTHODE

1.

Vérifie que l’énoncé/la formule est vraie pour la plus petite valeur entière (généralement $0$ ou $1$ ).

Remarque : Cette étape est courte et souvent facile mais elle est très importante, ne l’oublie pas.

2.

Pars du principe que l’énoncé est vrai pour , et sers-toi de cette information pour prouver qu’il est vrai pour $n+1$ .

Conseil : Dans la formule pour essais de retrouver la forme utilisée pour $n.$ 

Grâce à cette méthode, on sait que la formule est vraie pour une première valeur, par exemple $1$ .

Puis, on sait que si la formule est vraie pour $n=1$ , alors elle est aussi vraie pour $n+1=2$ .

Puis, on sait que si la formule est vraie pour $n=2$ , alors elle est aussi vraie pour $n+1=3$ , etc.

Ainsi, la formule est vraie pour l’ensemble des nombres entiers naturels.

Exemple

Prouve que la formule $1+2+\cdots+n=\frac{n(n+1)}{2}$ est valable pour toutes les valeurs entières naturelles de $n.$

Vérifie la formule pour $n=1$ :

$1=\frac{1\cdot2}{2}$

Pars du principe que la formule $1+2+\cdots+n=\frac{n(n+1)}{2}$ est vraie pour et prouve-la pour $n+1$ :

$1+2+\cdots+n+(n+1)=\frac{(n+1)(n+2)}{2}$

Retrouve la forme utilisée pour $n$ et sers-toi de la formule :

$1+2+\cdots+n+(n+1)=(1+2+\cdots+n)+(n+1)=\ \frac{n(n+1)}{2}+(n+1)$

Rassemble les termes pour obtenir la forme désirée :

$\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+2)(n+1)}{2}.$