Le raisonnement par récurrence
Principe du raisonnement par récurrence
On peut se représenter le principe de raisonnement utilisé dans l'activité précédente comme une chaîne de dominos.
Si on veut faire tomber toute la chaîne, il faut s'assurer :
que le premier domino tombe. C'est ce qu'on appellera la phase d'initialisation.
que les dominos sont placés de telle façon que lorsqu'un domino tombe, le suivant tombe aussi. C'est ce qu'on appellera la propriété d'hérédité.
Si ces deux conditions sont réunies, alors on est assuré que tous les dominos tomberont, aussi longue soit la chaîne.
On peut se donner d'autres représentations de ce principe comme monter à une échelle ou un escalier. Les bébés apprennent très vite à grimper d'une marche à une autre et se retrouvent souvent en haut d'un escalier sans savoir redescendre... Pour les empêcher de se retrouver dans une situation dangereuse, on place une barrière au niveau de la première marche, ce qui revient à les priver de la phase d'initialisation. Il sont ainsi dans l'incapacité de monter à l'escalier même s'ils maîtrise la propriété d'hérédité consistant à passer d'une marche à l'autre !
Fondamental : Le principe de récurrence
Soit \(n_0\in \mathbb{N}\) un entier.
On veut démontrer que pour tout rang \(n\geq n_0\), une propriété \(\mathcal{P}_n\) (propriété au rang \(n\)) est vraie.
Pour cela on utilise la méthode suivante :
Initialisation: Vérifier que la propriété est vraie au rang \(n_0\) (\(\mathcal P_{n_0}\) est vraie).Hérédité:On suppose que la propriété est vraie à un certain rang \(k\) (on suppose donc que \(\mathcal P_k\) est vraie).
On démontre alors que la propriété est vraie au rang suivant \(k+1\) (on doit démontrer que \(\mathcal P_{k+1}\) est vraie).
Conclusion: On conclut alors que la propriété est vraie« à partir »
du rang \(n_0\). (Pour tout \(n\geq n_0\), \(\mathcal P_n\) est vraie).\(\text{}\)
Attention !
Toutes les propriétés ne sont pas initialisées et toutes ne sont pas héréditaires !
Exemple :
On définit la suite \((u_n)\) par :
\(u_0=0\)
\(u_{n+1}=u_n+2n-11\) pour tout \(n\in \mathbb N\).
Montrer que la suite \((u_n)\) a pour forme explicite :
pour tout \(n\) : \(u_n=n^2-12n\).
Utilisons un raisonnement par récurrence :
Soit \(\mathcal P_n\) la propriété \(u_n=n^2-12n\).
InitialisationSi \(n=0, u_0=0\) est donnée par la définition de la suite, mais aussi \(u_0=0^2-12\times 0\).
Donc \(\mathcal P_0\) est vraie au rang \(n=0\). L'initialisation est réalisée.
HéréditéSupposons qu'à un certain rang \(k\), la propriété \(\mathcal P_k\) soit vraie. Nous devons la démontrer au rang \(k+1\) :
Or, \(u_{k+1}=u_k+2k-11\) d'après la définition de la suite \((u_n)\).
Mais alors \(u_{k+1}=k^2-12k+2k-11\) en utilisant la propriété \(\mathcal P_k\) (on l'appelle l'hypothèse de récurrence).
En simplifiant on a \(u_{k+1}=k^2-10k-11\).
Pour vérifier la formule au rang \(k+1\), nous allons développer et réduire l'expression recherchée au rang \(k+1\):
\((k+1)^2-12(k+1)=k^2+2k+1-12k-12=k^2-10k-11\). On reconnaît l'expression simplifiée de \(u_{k+1}\).
Donc on a bien \(u_{k+1}=(k+1)^2-12(k+1)\). La propriété \(\mathcal P_{k+1}\) est vraie au rang \(k+1\). Elle est donc héréditaire.
ConclusionPar un raisonnement par récurrence, on a prouvé que pour tout \(n\geq 0\), la propriété \(\mathcal P_n\) est vraie.
Donc :
Pour tout \(n\in \mathbb N, u_n=n^2-12n.\)