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

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}.$$​​