Resumes 
Flashcards 
StudySmarter IA 
Notes de cours 
Planning de révision 
Dossiers 
Examens 
Magazine 
Faire carrière 
App mobile 
Sauter à un chapitre clé
Qu'est-ce que la récurrence en maths ?
Nous appliquons le concept de la récurrence en maths lorsque nous utilisons un composant d'une séquence pour définir ou générer le suivant. Tu as peut-être déjà utilisé la récurrence pour définir des suites numériques. Ce concept peut s'étendre à d'autres objets mathématiques, tels que les matrices ou des opérations, comme la dérivation.
Nous pouvons définir les termes d'une suite par récurrence. Considère la suite numérique \(1, 5, 9, ...\). Si nous notons le n-ième terme de cette suite \(u_{n-1}\), alors nous pouvons définir cette suite par récurrence avec \(u_0 = 1\) et \(u_n = u_{n-1} + 4\). Observe que cette dernière équation est équivalente à \(u_{n+1} = u_n + 4\).
Nous pouvons également définir la n-ième dérivée de la façon suivante. Considère une fonction \(f\) qui est dérivable \(n\) fois. Nous notons alors \(f^{(n)} = (f^{(n-1)})'\).
Le principe de récurrence s'avère un outil puissant pour faire des démonstrations. Alors, quand faut-il privilégier une démonstration par récurrence ?
Quand utiliser la démonstration par récurrence ?
Nous avons plusieurs méthodes de démonstration, mais savais-tu que nous devons privilégier certaines méthodes selon le cas ? En effet, certaines méthodes mènent à des démonstrations plus courtes ou plus simples — et la démonstration par récurrence n'en est pas une exception. Imagine que tu dois démontrer une propriété pour tout entier naturel. Il serait impossible de vérifier cette propriété pour chaque nombre un par un. C'est dans ces cas-là qu'il faut utiliser la démonstration par récurrence.
Sais-tu cerner dans quels cas une démonstration par récurrence serait utile ?
- Démontre que \(4^{3n} + 5\) est divisible par \(3\) pour tout entier naturel \(n\).
- Démontre que \(1^2 + ... + n^2 = \frac{n(n+1)(2n + 1)}{6}\) pour tout entier naturel \(n\).
- Démontre que \(n! > 2^n\) pour tout entier supérieur à \(4\).
En fait, nous pouvons appliquer une démonstration par récurrence à toutes ces propositions !
En règle générale, lorsqu'il y a « pour tout » dans l'énoncé d'un exercice de démonstration, nous pouvons appliquer un raisonnement par récurrence.
Voyons maintenant quel est le principe qui fait fonctionner la démonstration par récurrence.
Le principe de récurrence
Le raisonnement par récurrence est une méthode utile pour démontrer certaines propositions mathématiques. Or, pour appliquer ce type de raisonnement, il faut comprendre le principe de récurrence. Dans un raisonnement par récurrence, nous avons trois grandes étapes :
initialisation ;
hérédité ;
et une conclusion.
Dans l'initialisation, nous montrons que la propriété que nous souhaitons démontrer est vraie pour le cas initial. Quant à l'hérédité, nous devons démontrer que cette propriété est passée d'un cas au suivant. C'est souvent l'étape la plus délicate. À la fin de notre démonstration par récurrence, nous devons également conclure avec une phrase appropriée. C'est un peu comme des formules de politesse à la fin d'une lettre formelle.
Nous pouvons traduire ces étapes avec des symboles mathématiques. Soient \(n_0\) et \(k\) deux entiers naturels. Considérons une proposition \(P(n)\) qui vérifie les propositions suivantes :
\(P(n_0)\) est vraie ;
Si \(P(k)\) est vrai, alors \(P(k+1)\) est vrai.
Dans ce cas, le principe de récurrence affirme que la proposition \(P(n)\) est vraie pour tout entier naturel \(n \geq n_0\)
Attention : ces deux propositions doivent être vérifiées. Sinon, la proposition peut être fausse.
Pour mieux comprendre, il est essentiel de regarder un exemple de comment démontrer par récurrence.
Démonstration par récurrence
Dans cette section, nous t'expliquons comment démontrer par récurrence, étape par étape. Nous nous servirons de deux exemples d'exercices auxquels tu peux appliquer un raisonnement par récurrence.
Démontre la proposition \(P(n) : 1 + ... + n = \frac{n(n+1)}{2}\), pour tout entier naturel \(n \geq 1\).
Démontre la proposition \(Q(n) : n! > 2^n\), pour tout nombre entier \(n \geq 4\).
Pour démontrer par récurrence, il y a trois étapes : initialisation, hérédité et une conclusion.
Initialisation
Dans l'étape d'initialisation, nous devons démontrer que le cas initial est vrai. Voyons comment faire cela pour nos deux exercices types.
Sais-tu à quoi correspondent les cas initiaux pour \(P(n)\) et \(Q(n)\) ?
Le cas initial de la proposition \(P(n)\) est \(P(1) : 1 = \frac{(1)((1)+1)}{2}\). Comme cette égalité est vraie, la proposition \(P (1)\) est vraie et le cas initial est vérifié.
Le cas initial de la proposition \(Q(n)\) est \(Q(4) : 4! > 2^4\). Cette inégalité, est-elle vraie ? D'une part, \(4! = 24\). D'autre part, \(2^4 = 16\). La proposition \(P(4)\) est donc vraie et le cas initial est vérifié.
Nous pouvons dire que l'initialisation est vérifiée pour les deux propositions ou que les propositions sont initialisées. Maintenant, il faut démontrer que l'hérédité est vérifiée. Pour cela, nous devons formuler l'hypothèse de récurrence.
Hypothèse de récurrence
Dans un raisonnement par récurrence, démontrer l'hérédité de la proposition \(P(n)\) revient à démontrer que la véracité de \(P(k)\) implique la véracité de \(P(k+1)\). Le fait de supposer que \(P(k)\) est vraie s'appelle l'hypothèse de récurrence. Nous devons nous appuyer sur l'hypothèse de récurrence pour démontrer \(P(k+1)\).
Hérédité
Démontrer l'hérédité nécessite des approches différentes selon la proposition que nous souhaitons démontrer. Dans tous les cas, il convient d'énoncer clairement l’hypothèse de récurrence. Si cette hypothèse est \(P(k)\), il faut également réfléchir à l'expression de \(P(k+1)\). Cela nous donnera une idée de comment manipuler \(P(k)\) pour en déduire \(P(k+1)\).
Es-tu capable de démontrer l'hérédité de la proposition \(P(n)\) ?
Pour l'hérédité, supposons \(P(k)\) vrai. Nous avons alors que \(1 + ... + k = \frac{k(k+1)}{2}\). Il faut utiliser cette égalité pour démontrer que \(P(k+1) : 1 + ... + k + k+1 = \frac{(k+1)(k+2)}{2}\) est vrai.
\(1 + ... + k = \frac{k(k+1)}{2}\)
\(1 + ... + k + k+1 = \frac{k(k+1)}{2} + k+1\)
\(1 + ... + k + k+1 = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}\)
\(1 + ... + k + k+1 = \frac{k(k+1) + 2(k+1)}{2} \)
\(1 + ... + k + k+1 = \frac{(k+1)(k+2)}{2} \)
Nous avons donc que démontré \(P(n+1)\) est vraie.
La proposition \(P(n)\) est donc héréditaire.
Les étapes pour démontrer une égalité sont différentes à celles nécessaires pour démontrer une inégalité.
Peux-tu démontrer l'hérédité de la proposition \(Q(n)\) ?
Pour l'hérédité, supposons \(Q(k)\) vrai. Nous savons alors que \(k! > 2^k\). Nous devons utiliser cette inégalité pour démontrer que \(Q(k+1) : (k+1)! > 2^{k+1}\) est vrai.
\(k! > 2^k\)
\((k+1) \times k! > (k+1) \times 2^k\)
\((k+1)! > (k+1) \times 2^k\)
Or, comme \(k \geq 4\), \(k + 1 \geq 5 > 2\) et donc \((k+1) \times 2^k > 2 \times 2^k = 2^{k+1}\).
Nous en déduisons que \((k+1)! > 2^{k+1}\) et ainsi, \(Q(k+1)\) est vraie.
La proposition \(Q(n)\) est donc héréditaire.
Après avoir démontré l'initialisation et l'hérédité d'une proposition, il reste à écrire une conclusion.
Conclusion
Un raisonnement par récurrence est incomplet sans rédiger une conclusion. Heureusement, la conclusion d'une démonstration par récurrence suit un modèle simple. Il faut souligner que l'initialisation et l'hérédité sont vérifiées, et inférer que la proposition est vraie par le principe de récurrence. Voici quelques façons de formuler cette conclusion.
Comme \(P(1)\) est vraie et \(P(k) \implies P(k+1)\), par le principe de récurrence, \(P(n)\) est vraie pour tout entier naturel \(n \geq 1\).
Pour \(Q(n)\), il y a l'initialisation et l'hérédité. Par récurrence, \(n! > 2^n\), pour tout entier \(n \geq 4\).
Le symbole \(\implies\) signifie « implique ».
Le type de récurrence que nous avons utilisé jusqu'à présent s'appelle la récurrence faible. S'il y a une récurrence faible, il doit logiquement avoir une récurrence forte.
Qu'est-ce que la récurrence forte ?
La récurrence forte et la récurrence faible sont presque identiques. La petite différence entre les deux est que la récurrence forte suppose la proposition vraie pour tous les rangs précédents. Par exemple, imagine que nous avons à démontrer la proposition \(P(n)\) pour tout entier naturel \(n\). Au lieu de démontrer que \(P(k)\) implique \(P(k+1)\), avec la récurrence forte, nous allons supposer que \(P(k), P(k-1), ..., P(0)\) sont vrais pour démontrer \(P(k+1)\).
Dans la plupart des cas, la récurrence faible suffit pour un raisonnement par récurrence.
Raisonnement par récurrence - Points clés
- Une démonstration par récurrence est plus souvent utilisée lorsqu'il faut démontrer une proposition pour tous les nombres entiers.
- Il y a trois étapes d'un raisonnement par récurrence :
- initialisation ;
- hérédité ;
- et une conclusion.
- Si nous devons démontrer la proposition \(P(n)\), l'étape d'initialisation consiste à démontrer que la proposition est vraie pour le cas initial, souvent \(P(0)\).
- Similairement, l'étape d'hérédité consiste à démontrer que \(P(k) \implies P(k+1)\).
- Pour la récurrence forte au lieu de supposer la véracité de \(P(k)\), nous supposons que \(P(k), P(k-1), ...\) sont vrais pour démontrer \(P(k+1)\).
Apprends avec 5 fiches de Raisonnement par récurrence dans l'application gratuite StudySmarter
Tu as déjà un compte ? Connecte-toi
Questions fréquemment posées en Raisonnement par récurrence
Comment faire un raisonnement par récurrence ?
Pour faire un raisonnement par récurrence, il faut d'abord vérifier que la proposition à démontrer est vraie pour le cas initial. Ensuite, il faut démontrer que si la proposition est vraie pour un certain rang, alors elle est vraie pour le rang suivant.
Qu'est-ce qu'une formule de récurrence ?
Une formule de récurrence établit un lien entre une valeur ou égalité d'une liste infinie, avec le précédent ou le prochain élément de la liste.
Comment comprendre le raisonnement par récurrence ?
Nous faisons souvent une analogie entre le raisonnement par récurrence et les dominos. En règle générale, si un domino tombe, alors le suivant tombera. Cela signifie que si tu fais tomber le premier domino, alors tous les dominos vont tomber. Le principe du raisonnement par récurrence est le même, sauf qu'il s'agit d'une relation mathématique.
C'est quoi la récurrence forte ?
La récurrence forte consiste à supposer que la proposition à démontrer est vraie pour tous les rangs inférieurs à un certain rang, afin de démontrer que la proposition est vraie pour le rang suivant.
C'est quoi l'hypothèse de récurrence ?
Lors d'un raisonnement par récurrence, nous faisons l'hypothèse que la proposition est vraie pour un certain rang, afin de le démontrer pour le rang suivant. Cette hypothèse est appelée hypothèse de récurrence.
Teste tes connaissances avec des questions à choix multiples
TON SCORE
Ton score
Rejoins l'application StudySmarter et apprends efficacement avec des millions de flashcards, et plus encore.
Apprends avec 5 fiches de Raisonnement par récurrence dans l'application gratuite StudySmarter
Tu as déjà un compte ? Connecte-toi
À propos de StudySmarter
StudySmarter est une entreprise de technologie éducative mondialement reconnue, offrant une plateforme d'apprentissage holistique conçue pour les étudiants de tous âges et de tous niveaux éducatifs. Notre plateforme fournit un soutien à l'apprentissage pour une large gamme de sujets, y compris les STEM, les sciences sociales et les langues, et aide également les étudiants à réussir divers tests et examens dans le monde entier, tels que le GCSE, le A Level, le SAT, l'ACT, l'Abitur, et plus encore. Nous proposons une bibliothèque étendue de matériels d'apprentissage, y compris des flashcards interactives, des solutions de manuels scolaires complètes et des explications détaillées. La technologie de pointe et les outils que nous fournissons aident les étudiants à créer leurs propres matériels d'apprentissage. Le contenu de StudySmarter est non seulement vérifié par des experts, mais également régulièrement mis à jour pour garantir l'exactitude et la pertinence.
En savoir plus