Tu veux savoir comment rédiger tes récurrences proprement et efficacement ? Que tu sois bizuth, carré ou même cube, cet article est fait pour toi. Dedans, tu y trouveras la méthode qu’il te faut pour soigner la rédaction d’une récurrence, raisonnement incontournable en prépa ECG.
L’utilité du raisonnement par récurrence
Soit \(n_0 \in \mathbb N\)
Le raisonnement par récurrence est très utile en mathématiques. Il sert à démontrer une propriété portant sur tous les entiers naturels, en prouvant les points suivants :
- l’initialisation : la propriété est vraie pour un entier \( n_0 \) (souvent pour \( 0 \) ou \( 1\) ) ;
- l’hérédité : chaque fois que cette propriété est vérifiée par un entier naturel \( n \ge {n_0} \), elle l’est également par son successeur, soit par l’entier \( n+1 \).
Si ces deux conditions sont établies, alors la propriété est vraie pour tous les nombres entiers naturels \( n \ge {n_0} \).
Repérer une question appelant un raisonnement par récurrence
Ceci est fondamental. En effet, dans chaque sujet de concours, tu peux repérer (facilement) les questions qui font penser à des raisonnements par récurrence.
Ce sont toujours des questions de la forme : \( “\ montrer\ que :\ \forall n \in \mathbb{N}, …” \).
Par ailleurs, voici quelques indices en plus pour dénicher un raisonnement par récurrence :
- la question porte sur des suites réelles. Exemple : trouver l’expression générale d’une suite définie par récurrence, prouver un résultat général (cf. \( \forall n \in \mathbb{N}, u_{n} \ge {0}\)), etc. ;
- le calcul d’une somme finie. Exemple : \( \forall n \in \mathbb{N}^*, \displaystyle \sum_{k=1}^{n} k = \frac {n(n+1)}{2} \) ;
- ou tout simplement, si tu ne vois pas comment résoudre une question sur des entiers naturels autrement que par récurrence.
Pour te montrer comment rédiger proprement, je vais détailler la rédaction pour montrer par récurrence que :
\[ \forall n \in \mathbb{N}^*, \displaystyle \sum_{k=1}^{n} k = \frac {n(n+1)}{2} \]
Étape 1 : énoncer la propriété que l’on démontrera par récurrence
Cette étape est importante, car c’est la première étape de ton raisonnement. Il faut poser la propriété, souvent notée \( \mathcal{H}_{n} \) ou \( \mathcal{P}_{n} \), pour tout entier naturel \( n \in \mathbb{N}\).
À écrire sur la copie
Pour tout entier \( n \in \mathbb{N}^*\), notons \( \mathcal{H}_{n} : \ \displaystyle \sum_{k=0}^{n} k = \frac {n(n+1)}{2} \)
Attention, tu as remarqué que le quantificateur \( \forall n \in \mathbb{N} ^*\) ne figure pas dans l’énoncé de la propriété \(\mathcal{H}_{n} \) : il faut le placer juste avant !
Étape 2 : l’initialisation et l’hérédité
Si l’initialisation est souvent facile à vérifier, l’hérédité peut être bien plus astucieuse ! Cependant, tu peux toujours baliser ta copie en écrivant les étapes du raisonnement (notamment l’initialisation !). Ce sera déjà quelques points de pris !
Ainsi, l’important ici est d’être clair et de rédiger proprement chaque étape, pour gagner la confiance du correcteur.
À écrire sur la copie (reprise de l’exemple précédent)
Initialisation : pour \( n=1\), on a : \( 1= \frac {1(1+1)}{2} \). Donc, la propriété \( \mathcal{H}_{1} \) est vraie.
Hérédité : soit \(n \in \mathbb{N}^* \) tel que \( \mathcal{H}_{n} \) est vraie.
Montrons que \( \mathcal{H}_{n+1} \) est vraie.
….
Donc, \( \mathcal{H}_{n+1} \) est vraie. Par principe de récurrence, \( \mathcal{H}_{n} \) est vraie pour tout \(n \in \mathbb{N} \).
Soit : \[ \forall n \in \mathbb{N}^*, \displaystyle \sum_{k=0}^{n} k = \frac {n(n+1)}{2} \]
Résumé de ce qu’il faut faire
Sur l’initialisation
- Montrer clairement que la propriété est vraie au rang \( n=1\) (cf. on peut laisser le \( 1+1\) dans le calcul).
- Terminer l’initialisation en énonçant que \( \mathcal{H}_{1} \) est vraie.
Sur l’hérédité
- Bien poser l’entier naturel \(n \) au début de l’hérédité.
- Écrire clairement ce que l’on veut démontrer, c’est-à-dire : si \( \mathcal{H}_{n} \) est vraie, alors \(\mathcal{H}_{n+1} \) est vraie. C’est un raisonnement par implication qui ne dit pas son nom ! (Pour en savoir plus, regarde cet article.)
- Conclure là aussi clairement en rappelant la propriété que tu as démontrée, et sans oublier d’énoncer le principe de récurrence !
Attention : n’oublie pas d’aérer ta copie entre chaque étape pour la rendre plus lisible !
Remarque supplémentaire : les différents types de récurrences
On distingue plusieurs types de raisonnements par récurrence, dont principalement :
– les récurrences simples (les plus courantes, cf. l’exemple ci-dessus) ;
– les récurrences doubles (ou triples, etc.) ;
– les récurrences finies ;
– les récurrences fortes ;
– les récurrences descendantes.
Récurrences doubles
On procède 2 par 2, c’est-à-dire que l’on prouve que \(\mathcal{H}_0\) et \(\mathcal{H}_1\) et on suppose que \(\mathcal{H}_n\) et \(\mathcal{H}_{n+1}\) sont vraies pour prouver que \(\mathcal{H}_{n+1}\) et \(\mathcal{H}_{n+2}\) sont vraies.
Attention : il ne faut pas oublier d’initialiser pour deux valeurs de \(n\).
Récurrences finies (aussi appelées « montées finies »)
On suit le même principe que pour des récurrences infinies (c’est-à-dire pour les propriétés sur \(n \in \mathbb{N} \)), mais avec \(i \in [\! [1,n]\!] \).
Attention : souvent, on fait alors des récurrences sur un autre entier que \(n\), par exemple en prenant \(i\). Il ne faut donc pas confondre les deux indices !
Il faut également faire attention au niveau de l’hérédité pour ce type de récurrence : au lieu de fixer un entier \(i \in [\! [1,n]\!] \), tu devras systématiquement baisser d’un rang la borne supérieure de l’ensemble. Donc, fixer un entier : \(i \in [\! [1,n-1]\!] \).
En conclusion, savoir rédiger une récurrence est nécessaire et même impératif pour tout préparationnaire, mais cela ne garantit pas de réussir la récurrence. Néanmoins, garde en tête qu’une récurrence bien rédigée et claire fera plaisir au correcteur, en t’assurant des points gratuits, dans le cas d’une initialisation bien faite par exemple.
N’hésite pas à consulter toutes nos autres ressources de maths !
