Introduction à la récurrence
La preuve de correction partielle à l'aide de l'invariant de boucle est appelé un raisonnement inductif, ou récurrent. C'est simple mais ça peut paraître abscons parce que c'est un peu plus long que ce dont vous avez l'habitude. Donc ça peut prendre un temps à assimiler, c'est normal.
Ce raisonnement en 3 étapes sert à montrer qu'une proposition dépendant d'un entier naturel est vraie tout le temps à partir d'un entier de départ.
Prenons un exemple concret qui ne nécessite que de savoir manipuler des expressions élémentaires.
On veut montrer que la proposition \(P_n\): "La somme \(S_n\) des \(n\) premiers entiers impairs est égale à \(n^2\)" est toujours vraie pour \(n \ge 1\)
1. INITIALISATION
On veut montrer que c'est vrai au début
Pour \(n=1\), \(S_1 = 1 = 1^2\) donc \(P_1\) est vraie
Pour \(n=2\), \(S_2 = 1 + 3 = 4 = 2^2\) donc \(P_2\) est vraie
Pour \(n=3\), \(S_3 = 1 + 3 + 5 = 9 = 3^2\) donc \(P_3\) est vraie
C'est donc vrai au début. (en réalité, il ne suffit que de le montrer pour \(n=1\), mais le faire plusieurs fois permet de s'approprier un peu les propositions qu'on manipule)
Mais ça ne veut pas dire que ça sera toujorus vrai, et c'est justement ça qui nous occupe.
2. CONSERVATION / Hérédité
On veut montrer que si jamais \(P_n\) est vraie pour un \(n\) quelconque, alors ça implique automatiquement que \(P_{n+1}\) est vraie.
On va donc supposer que \(P_n\) est vraie pour un \(n\) quelconque.
Donc que \(S_n=1+3+....+(2n-1) = n^2\)
Ce qu'on veut démontrer, c'est donc que sous cette hypothèse on aura automatiquement \(P_{n+1}\) vraie. Donc que \(S_{n+1} = (n+1)^2\)
Calculons donc \(S_{n+1}\), en se disant qu'on veut faire apparaître \(S_n\) pour pouvoir utiliser notre hypothèse (sinon elle sert à rien, c'est ridicule).
\(S_{n+1} = 1+...+(2n+1)\)
\(S_{n+1} = 1+...+(2n-1)+(2n+1)\)
\(S_{n+1} = S_n +(2n+1)\)
Or, \(P_n\) est Vraie par hypothèse. Donc \(S_n= n^2\)
\(S_{n+1} = n^2 + 2n + 1\)
A partir du moment où on a réussi à utiliser notre hypothèse, on cherche à retrouver l'écriture de ce qu'on veut démontrer en bidouillant.
En l'occurence, ici on reconnaît une identité remarquable, donc:
\(S_{n+1} = (n+1)^2\)
C'est justement ce qu'on voulait démontrer!
On vient donc de prouver que si jamais \(P_n\) est vraie un jour, alors \(P_{n+1}\) elle nécessairement vraie aussi
3. CONCLUSION
\(P_1\) est vraie. Donc nécessairement, \(P_2\) est vraie. Donc nécessairement, \(P_3\) est vraie. Donc nécessairement, \(P_4\) est vraie, etc...
Il est important d'initialiser, car il faut que ça soit vrai au moins une fois pour que ça soit "infiniment vrai" par conservation/hérédité.
Si \(P_1\) est vraie et que \(P_n \implies P_{n+1}\), alors \(P_n\) est vraie pour tout \(n \ge 1\)
Cette proposition (qui se démontre elle-même grâce aux axiômes fondamentaux des mathématiques) est au coeur du raisonnement.
On peut donc affirmer le coeur léger que "La somme \(S_n\) des \(n\) premiers entiers impairs est égale à \(n^2\) pour tout \(n \ge 1\)"
Premiers pas - La récurrence avec des petites roulettes
Démontrer que \(P_n\) = "La somme \(S_n\) des n premiers entiers est égale à \(\displaystyle \frac{n(n+1)}{2}\)" est vraie pour \(n \ge 1\)"
Pour ce faire, complétez la démonstration suivante:
1. INITIALISATION
Pour \(n=1\), \(S_1 = \dots\)
C'est donc vrai au début
2. CONSERVATION
On veut montrer que si jamais \(P_n\) est vraie pour un \(n\) quelconque, alors ça implique automatiquement que \(P_{n+1}\) est vraie.
On va donc supposer que \(P_n\) est vraie pour un \(n\) quelconque.
Donc que \(S_n= \dots\dots\dots\dots\dots\dots\)
Ce qu'on veut démontrer, c'est que sous cette hypothèse, \(P_{n+1}\) est vraie. Donc que \(S_{n+1} = \dots\dots\dots\dots\dots\)
Calculons donc \(S_{n+1}\) en faisant apparâitre \(S_n\)
\(S_{n+1} = \dots\dots\dots\dots\dots\dots\)
Or, \(P_n\) est Vraie par hypothèse. Donc \(\displaystyle S_n= \frac{n(n+1)}{2}\)
\(S_{n+1} = \dots\dots\dots\dots\dots\)
C'est justement ce qu'on voulait démontrer!
On vient donc de prouver que si jamais \(P_n\) est vraie un jour, alors \(P_{n+1}\) est nécessairement vraie aussi
3. CONCLUSION
\(P_1\) est vraie et pour tout \(n\), \(P_n \implies P_{n+1}\)
La somme \(S_n\) des \(n\) premiers entiers est donc égale à \(\displaystyle \frac{n(n+1)}{2}\) pour tout \(n>1\).