L'appli tout-en-un pour réviser
4.8 • +11k évaluations
Plus de 3 millions de téléchargements
Télécharger
Tu sais sûrement ce qu'est un effet domino. Le raisonnement par récurrence est presque la même chose. En effet, la récurrence repose sur le fait que certaines propriétés mathématiques se transfèrent d'un objet à un autre. Dans ce résumé de cours, nous présenterons tout d'abord la définition de la récurrence mathématique. Ensuite, nous expliciterons les cas dans lesquels la démonstration…
Explore our app and discover over 50 million learning materials for free.
Sauvegarde ce cours maintenant et relis-le quand tu auras le temps.
SauvegarderLerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenTu sais sûrement ce qu'est un effet domino. Le raisonnement par récurrence est presque la même chose. En effet, la récurrence repose sur le fait que certaines propriétés mathématiques se transfèrent d'un objet à un autre. Dans ce résumé de cours, nous présenterons tout d'abord la définition de la récurrence mathématique. Ensuite, nous expliciterons les cas dans lesquels la démonstration par récurrence devrait être privilégiée. Nous détaillerons ensuite le principe de récurrence utilisé pour les démonstrations et comment démontrer par récurrence. Pour terminer, nous expliquerons ce qu'est la récurrence forte.
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 ?
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 ?
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 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.
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.
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.
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)\).
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.
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.
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.
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.
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.
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.
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.
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.
des utilisateurs ne réussissent pas le test de Raisonnement par récurrence ! Réussirez-vous le test ?
lancer le quizHow would you like to learn this content?
How would you like to learn this content?
Free mathematiques cheat sheet!
Everything you need to know on . A perfect summary so you can easily remember everything.
Inscris-toi gratuitement et commence à réviser !
Sauvegarde des cours dans ton espace personnalisé pour y accéder à tout moment, n'importe où !
S'inscrire avec un e-mail S'inscrire avec AppleEn t'inscrivant, tu acceptes les Conditions générales et la Politique de confidentialité de StudySmarter.
As-tu déjà un compte ? Se connecter