Maths · Tle · Gratuit, sans inscription
Le raisonnement par récurrence
L'essentiel
Pour démontrer qu'une propriété P(n) est vraie pour tout entier n⩾n0 :
1. Initialisation : on vérifie que P(n0) est vraie.
2. Hérédité : on suppose P(n) vraie pour un entier n⩾n0 fixé et on démontre que P(n+1) est vraie.
3. Conclusion : par récurrence, P(n) est vraie pour tout n⩾n0.
Exemple : u0=5, un+1=un+2 et P(n) : « un=5+2n ». u0=5=5+2×0, donc P(0) est vraie ; si un=5+2n, alors un+1=5+2n+2=5+2(n+1) : P(n+1) est vraie.
À la fin de ce cours (25 min), tu sauras :
- Rédiger les trois étapes d'une récurrence : initialisation, hérédité, conclusion
- Démontrer par récurrence une formule de somme ou une divisibilité
- Encadrer une suite définie par un+1=f(un)
1Comprendre
La leçon en vidéo
L'effet domino. Clique sur « Lire », avec le son.
Le principe · Scène 1 / 4 · environ 3 min
Transcription
- Comment démontrer qu'une propriété est vraie pour tous les entiers, alors qu'il y en a une infinité ? Pensez à une file de dominos. Deux conditions suffisent pour qu'ils tombent tous. Un : le premier tombe. Deux : chaque domino qui tombe fait tomber le suivant. Alors, de proche en proche, ils tombent tous, même s'il y en a une infinité. C'est le raisonnement par récurrence. L'initialisation : la propriété est vraie au premier rang. L'hérédité : si elle est vraie à un rang n, elle est vraie au rang n plus un. Conclusion : elle est vraie pour tout n.
- Démontrons que la somme des n premiers nombres impairs, un plus trois plus etc. plus deux n moins un, vaut n carré. Initialisation : pour n égale un, la somme vaut un, et un carré aussi. Hérédité : supposons que la formule est vraie au rang n ; c'est l'hypothèse de récurrence. Au rang n plus un, on ajoute le terme suivant, deux n plus un. La somme devient n carré plus deux n plus un, c'est-à-dire n plus un au carré. C'est exactement la formule au rang n plus un. Conclusion : pour tout n supérieur ou égal à un, la somme vaut n carré.
- La récurrence est l'outil roi pour les suites définies par récurrence. Soit u zéro égale un et u n plus un égale racine de deux plus u n. Montrons que, pour tout n, zéro inférieur ou égal à u n inférieur à deux. Initialisation : u zéro égale un, c'est bien entre zéro et deux. Hérédité : si zéro inférieur ou égal à u n inférieur à deux, alors deux inférieur ou égal à deux plus u n inférieur à quatre. La racine carrée étant croissante, racine de deux inférieur ou égal à u n plus un inférieur à deux. Donc u n plus un est bien entre zéro et deux. Attention à l'erreur fréquente : supposer ce qu'on veut démontrer pour tout n, au lieu de le supposer pour un n fixé.
- Retenons l'essentiel. Initialisation : on vérifie que la propriété est vraie au premier rang. Hérédité : si elle est vraie à un rang, on montre qu'elle l'est au rang suivant. Alors elle est vraie pour tous les entiers : c'est l'effet domino.
Le raisonnement par récurrence : principe et rédaction en 3 étapes
Propriété · Principe de récurrence
Soit P(n) une propriété dépendant d'un entier n et n_0 un entier. Si P(n_0) est vraie (initialisation) et si, pour tout entier n≥ n_0, P(n) vraie entraîne P(n+1) vraie (hérédité), alors P(n) est vraie pour tout n≥ n_0 (conclusion).
Méthode · Rédiger une récurrence
- Énoncer clairement P(n).
- Initialisation : vérifier P(n_0) par le calcul.
- Hérédité : « Soit n≥ n_0 tel que P(n) est vraie » (hypothèse de récurrence, HR). Montrer P(n+1) en utilisant l'HR.
- Conclusion : « Par récurrence, P(n) est vraie pour tout n≥ n_0. »
Méthode · Pour une suite uₙ₊₁ = f(uₙ)
- Encadrement a≤ u_n≤ b : on applique des opérations ou une fonction croissante à l'encadrement.
- Sens de variation : on démontre u_n≤ u_n+1 par récurrence, en appliquant f croissante : f(u_n)≤ f(u_n+1), c'est-à-dire u_n+1≤ u_n+2.
Attention
Vérifier une propriété pour n=1, 2, 3, , 100 ne la prouve pas pour tout n. Et une hérédité sans initialisation ne prouve rien : « 10^n+1 est divisible par 9 » est héréditaire mais fausse pour tout n.
2Exemple
Exemple résolu : l'inégalité de Bernoulli
Énoncé
Soit a>0. Démontrer que pour tout entier n0, (1+a)^n1+na.
Étape 1
P(n) : (1+a)^n1+na. Initialisation : (1+a)^0=11+0 ✓.
Étape 2
Hérédité : soit n0 tel que (1+a)^n1+na. Comme 1+a>0, on multiplie : .
Pourquoi ? Multiplier par un nombre positif conserve l'inégalité.
Étape 3
car na^20. Donc P(n+1) est vraie.
Conclusion
Par récurrence, (1+a)^n1+na pour tout n0 — d'où l'on déduira que q^n+∞ si q>1.
3Rédiger
Rédiger comme au contrôle et au bac
Le bon résultat ne suffit pas : les points se gagnent sur ce qui est écrit. Voici les rédactions attendues, ligne par ligne.
Démontrer une formule de somme : 1^2+2^2+·s+n^2
- Pour tout entier n1, on note P(n) : « ».J'énonce la propriété à démontrer.
- Initialisation. Pour n=1 : 1^2=1 et (1×2×3)/(6)=1, donc P(1) est vraie.Je calcule les deux membres séparément au premier rang.
- Hérédité. Supposons que P(n) est vraie pour un entier n1 : .J'écris l'hypothèse de récurrence, pour un n fixé.
- Alors J'ajoute le terme suivant et j'utilise l'hypothèse de récurrence.
- =((n+1) [n(2n+1)+6(n+1) ])/(6)Je factorise par (n+1).
- =((n+1)(2n^2+7n+6))/(6)Je développe le crochet.
- Or (n+2)(2n+3)=2n^2+7n+6, donc la somme vaut ((n+1)(n+2)(2n+3))/(6) : P(n+1) est vraie.Je reconnais la formule au rang n+1.
- Conclusion. P(1) est vraie et la propriété est héréditaire, donc par récurrence P(n) est vraie pour tout entier n1.Je conclus en citant le principe de récurrence.
Encadrer une suite définie par u_n+1=f(u_n)
- Soit (u_n) définie par u_0=2 et u_n+1=12u_n+3. Pour tout n0, on note P(n) : « 0≤ u_n6 ».J'énonce la propriété.
- Initialisation. u_0=2 et 026, donc P(0) est vraie.Je vérifie au premier rang.
- Hérédité. Supposons que P(n) est vraie pour un entier n0 : 0≤ u_n6.Hypothèse de récurrence, pour un n fixé.
- En multipliant par 12>0 : .Multiplier par un nombre positif conserve le sens des inégalités.
- En ajoutant 3 : , soit . Donc : P(n+1) est vraie.Je fais apparaître u_n+1 ; comme 03, j'ai l'encadrement voulu.
- Conclusion. Par récurrence, 0≤ u_n6 pour tout entier n0.Je conclus : la suite est bornée.
Démontrer une divisibilité : 7^n-1 est divisible par 6
- Pour tout entier n0, on note P(n) : « 7^n-1 est divisible par 6 ».J'énonce la propriété.
- Initialisation. 7^0-1=0=6×0, donc P(0) est vraie.0 est divisible par 6.
- Hérédité. Supposons que P(n) est vraie pour un entier n0 : il existe un entier k tel que 7^n-1=6k, c'est-à-dire 7^n=6k+1.Je traduis « divisible par 6 » par une égalité avec un entier k.
- Alors .Je fais apparaître 7^n pour utiliser l'hypothèse.
- Comme 7k+1 est un entier, 7^n+1-1 est divisible par 6 : P(n+1) est vraie.Je justifie que le facteur est entier.
- Conclusion. Par récurrence, 7^n-1 est divisible par 6 pour tout entier n0.Je conclus.
À toi de rédiger
Démontre par récurrence que 5^n+3 est divisible par 4 pour tout entier n0. On note P(n) : « 5^n+3 est divisible par 4 ». Complète la rédaction.
- Initialisation. Pour n=0 : 5^0+3=, qui est divisible par 4.
- Hérédité. Supposons que : il existe un entier k tel que 5^n+3=4k, donc 5^n=4k-3.
- Alors 5^n+1+3=5×5^n+3=
- =20k-12= avec 5k-3 entier : P(n+1) est vraie.
- Conclusion. P(0) est vraie et la propriété est héréditaire, donc.
4S'entraîner
5 exercices corrigés
Du plus guidé au plus difficile. Réponds, puis vérifie : un indice se débloque après ton premier essai, la correction détaillée après le deuxième.
Exercice 1 / 5
Préparation de l'exercice…
Exercice 2 / 5
Préparation de l'exercice…
Exercice 3 / 5
Préparation de l'exercice…
Exercice 4 / 5
Préparation de l'exercice…
Exercice 5 / 5
Préparation de l'exercice…
5Retenir
À retenir : réponds de mémoire
Relire ne suffit pas à retenir. Chercher la réponse dans sa tête, si. Réponds d'abord, puis vérifie.
1. Quelles sont les trois étapes d'un raisonnement par récurrence ?
2. Dans l'hérédité, que suppose-t-on exactement ?
3. On veut montrer 2^n>n^2 pour tout n5. Vérifie l'initialisation.
4. Une propriété héréditaire est-elle forcément vraie ?
Dans 3 jours
La fiche de révision à imprimer
L'essentiel, la méthode, l'exemple type et les erreurs à éviter, sur une page A4.
Questions fréquentes
Comment faire un raisonnement par récurrence ?
On énonce P(n), on vérifie le premier rang, puis on montre que P(n) entraîne P(n+1). Pour « n^3-n est divisible par 3 » : au rang 0, 0 l'est ; et est divisible par 3 si n^3-n l'est.
Comment rédiger l'hérédité d'une récurrence ?
Écris « Supposons que P(n) est vraie pour un entier n≥ n_0 », puis pars de l'expression au rang n+1 pour y faire apparaître l'hypothèse. Pour 2+4+·s+2n=n(n+1) : on ajoute 2(n+1) et n(n+1)+2(n+1)=(n+1)(n+2).
Le raisonnement par récurrence, c'est en quelle classe ?
En terminale, en spécialité mathématiques, en général dès le chapitre sur les suites. Il resservira en mathématiques expertes (divisibilité) et dans le supérieur.
Quelle différence entre une suite définie par récurrence et un raisonnement par récurrence ?
Une suite définie par récurrence est donnée par son premier terme et une relation comme u_n+1=2u_n ; le raisonnement par récurrence est une méthode de démonstration. Avec u_0=3 et u_n+1=2u_n, on démontre par récurrence que u_n=3×2^n.