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+⋯+n=2n(n+1)
Vérification de la formule pour certaines valeurs de n :
-
Pour n=5 ∶
1+2+3+4+5=15=25⋅6
-
Pour n=10 :
1+2+3+⋯+10=55=210⋅11
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+⋯+n=2n(n+1) est valable pour toutes les valeurs entières naturelles de n.
Vérifie la formule pour n=1 :
1=21⋅2
Pars du principe que la formule 1+2+⋯+n=2n(n+1) est vraie pour et prouve-la pour n+1 :
1+2+⋯+n+(n+1)=2(n+1)(n+2)
Retrouve la forme utilisée pour n et sers-toi de la formule :
1+2+⋯+n+(n+1)=(1+2+⋯+n)+(n+1)= 2n(n+1)+(n+1)
Rassemble les termes pour obtenir la forme désirée :
2n(n+1)+(n+1)=2n(n+1)+2(n+1)=2(n+2)(n+1).