....
..c
Ol
·;::
>0..
0
u
La propriété est donc vraie au rang n + 1 .
Comme elle est vraie au rang 0, elle est donc vraie pour tout entier naturel n.
Le raisonnement par récurrence permet de démontrer une propriété vérifiée, suivant les cas,
pour tous les entiers naturels, dans d'autres, pour une infinité d 'entiers naturels, à partir d'un
certain rang.
2. Récurrence forte
Considérons une suite (un)n.eN· On cherche toujours à démontrer une propriété P pour
une suite (un)neN·
Comme pour la récurrence simple, on commence par regarder si la propriété P est
vérifiée à un rang initial no E N donné (no peut, bien sûr, être égal à zéro); si c' est le
cas, on suppose ensuite qu'elle est vraie jusqu' à un r ang n ~ no quelconque, et on
cherche à déterminer si elle est encore vraie au rang n+ 1 : si oui, le fait qu'elle soit vraie
au rang no permettra d'en déduire qu'elle est vérifiée pour tout entier n ~ no .
Cette récurrence qui semble, en apparence, plus forte que la récurrence simple, lui est
en fait équivalente, dans la mesure où elle revient à démontrer par récurrence simpJe la
propriété à tout rang k ~ n.
3. Récurrence double
Il s'agit, cette fo is-ci, d' un autre type de démonstration par récurrence : on cherche
toujours à démontrer une propriété P pour une suite (un.)nel' >l> mais, pour commencer, au
lieu de regarder si P est vérifiée à un rang initial no E N donné, on regarde si elle est
vraie aux rangs no et no + 1 (no peut toujours être égal à zéro); s. i c'est Je cas, on suppose
ensuite que Pest vraie aux rangs n ~ no et n + 1, pour n quelconque, et on cherche à
déterminer si elle est encore vraie aux rangs n + 1 et n + 2: si oui , le fait qu 'elle soit vraie
aux rangs no et n 0 +1 permettra d'en déduire qu'elle est véri fiée pour tout entier n ~ n 0 .
Exemple
Soit () un réel.
Démontrons par récurrence que, pour tout entier naturel non nul n, cos(n B) est un polynôme,
noté T 11 , de degré n en cos e, de coefficient dominant 2
11
-
1 •
• La propriété est vraie au rang 1 :
cos e est bien un polynôme de degré 1 en cos (), de coefficient dominant 2 1 - 1 = 1.
• La propriété est vraie au rang 2 :
cos(2 0) = 2 cos
2
e - 1 est bien un polynôme de degré 2 en cos e, de coefficient dominant
22-1 = 2.
• Supposons la vraie jusqu' à un rang n > 1.
Les formules d'addition permettent alors d'écrire :
cos ((n + 1) ()) = cos (n ()) cos() - sin (n ()) sin e
et:
cos ((n - 1) B) = cos (n ()) cos() + sin (n B) sin()
378
..c
Ol
·;::
>0..
0
u
La propriété est donc vraie au rang n + 1 .
Comme elle est vraie au rang 0, elle est donc vraie pour tout entier naturel n.
Le raisonnement par récurrence permet de démontrer une propriété vérifiée, suivant les cas,
pour tous les entiers naturels, dans d'autres, pour une infinité d 'entiers naturels, à partir d'un
certain rang.
2. Récurrence forte
Considérons une suite (un)n.eN· On cherche toujours à démontrer une propriété P pour
une suite (un)neN·
Comme pour la récurrence simple, on commence par regarder si la propriété P est
vérifiée à un rang initial no E N donné (no peut, bien sûr, être égal à zéro); si c' est le
cas, on suppose ensuite qu'elle est vraie jusqu' à un r ang n ~ no quelconque, et on
cherche à déterminer si elle est encore vraie au rang n+ 1 : si oui, le fait qu'elle soit vraie
au rang no permettra d'en déduire qu'elle est vérifiée pour tout entier n ~ no .
Cette récurrence qui semble, en apparence, plus forte que la récurrence simple, lui est
en fait équivalente, dans la mesure où elle revient à démontrer par récurrence simpJe la
propriété à tout rang k ~ n.
3. Récurrence double
Il s'agit, cette fo is-ci, d' un autre type de démonstration par récurrence : on cherche
toujours à démontrer une propriété P pour une suite (un.)nel' >l> mais, pour commencer, au
lieu de regarder si P est vérifiée à un rang initial no E N donné, on regarde si elle est
vraie aux rangs no et no + 1 (no peut toujours être égal à zéro); s. i c'est Je cas, on suppose
ensuite que Pest vraie aux rangs n ~ no et n + 1, pour n quelconque, et on cherche à
déterminer si elle est encore vraie aux rangs n + 1 et n + 2: si oui , le fait qu 'elle soit vraie
aux rangs no et n 0 +1 permettra d'en déduire qu'elle est véri fiée pour tout entier n ~ n 0 .
Exemple
Soit () un réel.
Démontrons par récurrence que, pour tout entier naturel non nul n, cos(n B) est un polynôme,
noté T 11 , de degré n en cos e, de coefficient dominant 2
11
-
1 •
• La propriété est vraie au rang 1 :
cos e est bien un polynôme de degré 1 en cos (), de coefficient dominant 2 1 - 1 = 1.
• La propriété est vraie au rang 2 :
cos(2 0) = 2 cos
2
e - 1 est bien un polynôme de degré 2 en cos e, de coefficient dominant
22-1 = 2.
• Supposons la vraie jusqu' à un rang n > 1.
Les formules d'addition permettent alors d'écrire :
cos ((n + 1) ()) = cos (n ()) cos() - sin (n ()) sin e
et:
cos ((n - 1) B) = cos (n ()) cos() + sin (n B) sin()
378