Module 1 : Introduction au raisonnement par récurrence

par


Si vous connaissez déjà le raisonnement par récurrence (ce qui est probablement le cas si vous avez passé le début d’année de Terminale S) vous pouvez passer l’Introduction et l’Exercice 1, et vous rendre directement à l’Exercice 2.

L’Exercice 3 devrait vous plaire si vous prenez la peine de bien y réfléchir !

Les exercices de chaque module sont généralement classés par ordre croissant de difficulté, je vous conseille donc de les suivre dans l’ordre.

Bon courage !

Introduction :

 

Le raisonnement par récurrence est un outil très puissant pour démontrer des propriétés sur des suites numériques, qui vous servira tout au long de vos études supérieures. Il ne peut en revanche pas s’appliquer sur des fonctions définies sur des ensembles réels ; vous allez comprendre pourquoi.

Supposons qu’on souhaite étudier une propriété à propos d’une certaine suite (par exemple : « cette suite est toujours positive » ou « cette suite est croissante »). Notons P(n) cette propriété pour un certain rang n de la suite, par exemple P(n) = « cette suite est positive au rang n » : montrer P revient alors à montrer que la propriété P(n) est vraie pour tout entier naturel n
Si la suite n’est pas définie explicitement, faire une démonstration rigoureuse de la propriété peut s’avérer compliqué. C’est là qu’intervient la démonstration par récurrence ; elle se décompose en deux étapes fondamentales : l’initialisation et l’hérédité.

L’initialisation consiste à montrer que la propriété P(n) est vraie pour un des premiers rangs de la suite.

L’hérédité consiste à montrer que si P(n) est vérifiée à un certain rang n (quelque soit ce rang), alors elle l’est également au rang n+1. Il est important de faire la démonstration dans le cas général, en prenant un n quelconque.

Combinée à l’initialisation, l’hérédité nous permet alors de généraliser à toute la suite : si la propriété est vraie au rang 1 (initialisation) alors elle est vraie au rang 2 (hérédité). Si elle est vraie au rang 2, alors elle est vraie au rang 3 (hérédité). Si elle est vraie au rang 3, alors…etc… On peut ainsi conclure que la propriété P(n) est vraie pour tous les rangs de la suite supérieurs ou égaux au rang de l’initialisation, autrement dit qu’elle est vraie pour toute la suite après ce rang.

 

Pour bien comprendre ce qu’est le principe de récurrence, il convient de visualiser une suite infinie de dominos, disposés debout les uns derrière les autres. Il est bien évident que faire tomber le premier domino conduira inexorablement à la chute de tous les dominos, l’un après l’autre (en supposant qu’ils aient été convenablement disposés). Pour démontrer cela rigoureusement, il faut que deux conditions soient vérifiées :

1/ Le premier domino est tombé.   (initialisation)

2/ Si un domino tombe, alors le suivant tombe aussi.   (hérédité)

L’initialisation va en fait définir le rang à partir duquel la propriété est vraie. Par exemple, si on sait que le 3ème domino est tombé, alors nécessairement tous les dominos de rang supérieur ou égal à 3 sont également tombés, mais cela ne nous donne aucune indication sur l’état des dominos 1 et 2…
En règle générale, il faut bien veiller à toujours faire attention à la cohérence et à la rigueur du raisonnement, et ne pas se contenter « d’appliquer un schéma » ; sous peine d’arriver à des conclusions erronées voire absurdes (vous en aurez une illustration parfaite dans l’exercice 3).

 

Exemple concret :

Soit (u_n) la suite définie sur \mathbb{N} par : \begin{cases} u_{0} = 0 \\ u_{n+1} = 3 u_{n} + 1 \end{cases}

Il est évident que la suite est positive. Mais vous savez bien qu’en mathématiques, une démonstration basée sur des « c’est évident que […] » , « on sent bien que […] », « on voit que […] » etc… ne vaut strictement rien.

La question que je vous pose maintenant est : comment démontrer rigoureusement que la suite est effectivement positive pour tout entier naturel n ? La réponse est bien évidemment : par récurrence (on s’en serait douté). Voici un exemple de rédaction possible.

 

Montrons par récurrence que, pour tout entier naturel n, on a   u_{n} \geq 0    (propriété P(n) à démontrer)

Initialisation :    u_{0}=0 \geq 0        donc P(0) est vraie.   (c.à.d la propriété « u_{n} \geq 0 »  est vraie au rang 0)

Hérédité :  On suppose avoir trouvé un entier naturel n pour lequel la propriété P(n) est vérifiée (hypothèse de récurrence). Montrons qu’alors P(n+1) est également vraie.

 u_{n+1}=3u_{n}+1      or d’après notre hypothèse de récurrence,   u_{n} \geq 0

D’où :

u_{n+1}=3u_{n}+1\geq  3\times0+1

  u_{n+1}\geq1\geq 0

 

 P(n+1) est vraie, la propriété est donc héréditaire. Par le principe de récurrence on a par conséquent montré que la suite  (u_n) est toujours positive.

 

 Ne vous formalisez pas trop sur les mots employés pour rédiger la démonstration par récurrence. Il existe de nombreuses façons de la formuler : l’important est que vous ayez compris le principe et que vous soyez capables de l’exprimer de manière claire et précise. Plus vous avancerez dans vos études, moins vous détaillerez votre rédaction, mais au lycée les professeurs / correcteurs sont parfois à cheval sur certaines formulations, le plus simple sera donc de calquer votre rédaction sur celle que votre professeur vous présente.

Vous comprenez maintenant pourquoi le raisonnement par récurrence est inopérant sur des fonctions définies sur les réels (supposons qu’une certaine propriété est vraie pour un certain rang réel x, quel est le réel venant juste après ?…)

L’exemple pris ici était d’une simplicité enfantine (la propriété à démontrer était donnée et l’hérédité ne présentait aucune difficulté). Parfois, le plus dur sera de trouver la propriété à démontrer. N’hésitez pas à relire cette introduction si vous en sentez le besoin ; si vous vous sentez prêt à passer à la suite, les exercices vous attendent !

Exercice 1 : Somme des impairs

Le but de cet exercice est de trouver une formule explicite à la somme des n premiers entiers impairs. Étant dans le module « raisonnement par récurrence », vous vous doutez bien qu’il faudra utiliser une récurrence. Dans le prochain module, nous verrons comment retrouver ce résultat directement avec le calcul de sommes.

 

On s’intéresse à la suite  (u_n)  définie sur  \mathbb{N}  par :

  \begin{aligned} u_{n}  &=  \sum_{k=0}^{n-1} (2k+1)& \\   &= 1+3+5+...+(2n-1) \end{aligned}&

(Ignorez la première notation si vous n’êtes pas à l’aise avec pour le moment)

Expliciter la valeur de  u_n  pour tout entier naturel n non nul.

 

Voir la correction

Indice

Le plus dur ici est de trouver la relation à démontrer par récurrence. En règle générale, quand on ne sait pas ce que l’on cherche, il est avisé de regarder comment se comporte la suite sur les premiers termes. Voici ce que je vous propose :

1) Calculer u_1,u_2,u_3,u_4

2) Émettre une conjecture sur la valeur de u_n  en fonction de n, puis la démontrer par récurrence.

Exercice 2 : Produit des impairs

 

On cherche cette fois-ci à calculer le produit des entiers impairs. Pour des raisons de commodité dans la notation, nous nous intéresserons au produit des n+1 premiers impairs au lieu des n premiers.

Montrer par récurrence que, pour tout n\in\mathbb{R} ,

\displaystyle 1\times3\times5\times...\times(2n+1)=\frac{(2n+1)!}{2^n\times(n!)}

Pour ceux qui ne savent pas ce que ces «  !  » signifient : il s’agit de factorielles. Une factorielle est le produit de tous les entiers partant de 1, jusqu’à l’entier considéré. Ainsi la factorielle de 4 (notée 4! ) est égale à 1x2x3x4 = 24 .
De même,  3 ! = 1x2x3 = 6  ,  2 ! = 1×2 = 2  ,  1 ! = 1
Plus généralement on note  :   n!=1\times2\times3\times...\times(n-1)\times n
Par exemple, on a également   (n+1)\times (n!)=(n+1)!

 

Attention : Par convention, 0!=1  et  a^0=1  pour tout  a\in\mathbb{R} .

 

En langage mathématique plus formel, on écrira :

\displaystyle 1\times3\times5\times...\times(2n+1)=\prod_{k=0}^{n}(2k+1)
\displaystyle n!=\prod_{k=1}^{n}(k)

Mais je ne veux pas vous déstabiliser avec ces notations pour l’instant si vous ne les connaissez pas bien, nous les verrons en détail dans le module suivant, sur les sommes (il s’agit ici d’un produit mais le comportement de cette notation est assez similaire à celui de la somme).

 

 

Voir la correction

Indice

 

Multiplier par ne change rien à un produit.
Entre autres :

    \[1=\frac{2n+2}{2n+2}\]

Exercice 3 (Bonus) : Un paradoxe de logique

  

Voici un petit problème de logique qui m’a été posé lors de ma première khôlle de maths en prépa, faisant intervenir une démonstration par récurrence. Je me souviens que celui-ci m’avait particulièrement marqué à l’époque ; il est un parfait exemple qu’un manque de rigueur peut conduire à des erreurs subtiles et difficiles à détecter, qui amènent à un résultat entièrement faux

Attention : Il s’agit ici d’un réel problème de logique, non pas d’un jeu sur les mots, d’un problème de formulation ou de quelque chose qui dépendrait d’une interprétation subjective. Si vous avez l’impression que le raisonnement du problème est étrange (voire stupide), c’est très probablement que vous ne l’avez pas entièrement compris !

 


 

On cherche à démontrer que quels que soient les crayons de couleur que je choisisse, tous ces crayons seront nécessairement de la même couleur (autrement dit, qu’il n’existe qu’une seule couleur de crayon sur la planète).

Supposons que je prenne un seul crayon de couleur. Quel que soit le crayon choisi, il sera nécessairement de la même couleur que lui-même, n’est-ce pas ? Si vous préférez, nous pouvons dire que quel que soit l’ensemble des « 1 » crayons choisi, ces crayons sont tous de la même couleur. Cela peut sembler stupide, mais nous en avons besoin pour la suite : c’est l’étape d’initialisation.

 


Hérédité :
Supposons maintenant avoir trouvé un nombre entier naturel n quelconque pour lequel la propriété P= « Quels que soient les n crayons choisis, ils sont tous de la même couleur » est vérifiée. Montrons qu’elle est vraie au rang n+1.

Prenons n+1 crayons :

D’après notre hypothèse de récurrence, les n premiers crayons sont tous de la même couleur :

Or d’après cette même hypothèse de récurrence, les n derniers crayons sont eux aussi tous de la même couleur (car notre hypothèse est vraie quels que soient les n crayons choisis) : 

Nous pouvons donc en conclure que tous ces n+1 crayons sont de la même couleur. La propriété est donc vraie au rang n+1 : elle est héréditaire. De plus, d’après l’initialisation, P(1) est vérifiée.
Par le principe de récurrence nous venons de démontrer que quelque soient les crayons que nous choisissons et peu importe leur nombre, ils seront tous de la même couleur.

Bien entendu cette conclusion est complètement fausse ! Il est parfaitement possible de choisir quatre crayons dont un bleu, deux verts et un rouge par exemple. Et qui dit conclusion fausse, dit nécessairement erreur de raisonnement (ou théorie axiomatique inconsistante, mais ce n’est pas le cas ni le sujet ici). Alors, où se trouve l’erreur ?

P.S : Essayez de réellement comprendre le raisonnement utilisé ici, qui est très loin d’être stupide. L’erreur réside dans quelque chose de très précis et très clair. Si vous pensez avoir trouvé l’erreur sans en être totalement sûr, c’est que vous vous trompez !

Voir la correction

Indice

 

L’erreur se trouve dans le raisonnement utilisé dans l’hérédité. Celui-ci n’est vrai qu’à une seule condition, qui n’est pas vérifiée ici…