Le raisonnement par récurrence est une méthode pour démontrer une propriété. Il sert à démontrer qu’un énoncé est vrai pour tout nombre naturel.
Exemple
La somme des nombres entiers de 1 à n 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. Le raisonnement par récurrence garantit que la formule est toujours valable, pour n’importe quel nombre 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). Note : 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 n, et sers-toi de cette information pour prouver qu’il est vrai pour n+1. Conseil : Dans la formule pour n+1, tu as le droit d’utiliser la formule que tu supposes vraie jusqu’à 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 n 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 :
Comment je peux utiliser le raisonnement par récurrence ?
Commence par vérifier que l’énoncé/la formule est vraie pour la plus petite valeur entière (généralement 0 ou 1). Ensuite, pars du principe que l’énoncé est vrai pour n, et sers-toi de cette information pour prouver qu’il est vrai pour n + 1.
À quoi sert le raisonnement par récurrence ?
Il sert à démontrer qu’un énoncé est vrai pour tout nombre naturel.
Qu'est-ce que le raisonnement par récurrence d'une suite ?
Le raisonnement par récurrence est une méthode pour démontrer une propriété.
Beta
Je suis Vulpy, ton compagnon de révision IA ! Apprenons ensemble.