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 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.
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)\).
Cours 
Magazine 
