Comment bien mener et rédiger une récurrence en mathématiques ?

Partie I – Qu’est-ce qu’une récurrence ?

Le raisonnement par récurrence est une des grandes nouveautés pour les élèves qui arrivent en terminale S. Pour eux, cette notion est plutôt difficile à assimiler. Certes, le principe est simple à comprendre mais l’organisation des calculs peut énormément varier selon les contextes. Les élèves y perdent alors leurs repères. C’est surtout l’étape de « l’hérédité » qui est compliquée à gérer car cela revient à prouver une infinité d’implications, chose qui est assez inhabituelle pour un élève en terminale S.

Commençons par rappeler/préciser de quoi il s’agit. Le principe de raisonnement par récurrence repose sur une idée toute simple, à la portée d’un enfant de maternelle.  Imaginons que l’on dispose d’une série de dominos que l’on place debout :

Supposons que l’on ait les deux conditions suivantes qui soient satisfaites :

1°) les dominos sont suffisamment rapprochés de sorte que chaque domino qui tombe entraîne la chute du suivant (hérédité) ;

2°) on fait tomber le premier domino (ou le p-ième domino) (initialisation).

ALORS…

Alors, TOUS les dominos vont tomber (ou tous à partir du p-ième)

évident, n’est-ce pas ?

C’est ce principe simple et naturel que nous allons appliquer à des propriétés mathématiques afin de montrer qu’elles sont « toujours » vraies. Plus exactement, si on souhaite démontrer qu’une propriété mathématique dépendant d’un entier naturel n est vraie pour tout n, alors ce raisonnement par récurrence peut et doit être envisagé (si on n’a pas trouvé d’autre méthode de raisonnement direct).

Mais comment transposer ce principe simple à des propriétés mathématiques ?

C’est ce que nous allons voir et expliquer sur quelques exemples !
Mais pas si vite… D’abord, qu’est-ce qu’une propriété mathématique dépendant d’un entier naturel n ?

Lorsqu’on dit que les trois médianes d’un triangle sont concourantes, on exprime une propriété mathématique (qui, en l’occurrence, est vraie). Lorsqu’on dit que le carré d’un nombre est toujours positif, on exprime là encore une propriété mathématique (qui est vraie si le nombre en question est réel mais fausse si le nombre en question est complexe…). Ces propriétés mathématiques tiennent en une seule entité.
Mais si on affirme maintenant quelque chose du genre :

6^n-1 est un multiple de 5, quel que soit l’entier n

on décrit cette fois une propriété mathématique qui dépend d’un entier n. C’est totalement différent des propriétés mathématiques précédentes qui étaient non indexées. C’est pour des propriétés mathématiques de ce genre, qui sont indexées par un entier n, que le raisonnement par récurrence va pouvoir s’envisager.

D’ailleurs, qu’en pensez-vous de 6^n-1 ? Toujours un multiple de 5 ou non ?…
Voyons voir :

Valeur de n Valeur de 6^n-1 Résultat
0 0 multiple de 5
1 5 multiple de 5
2 35 multiple de 5
3 215 multiple de 5
4 1295 multiple de 5

C’est vite vu, il semble que 6^n-1 soit un multiple de 5 pour tout n. On a bien dit « il semble que… » ! En effet, rien ne nous assure, à ce stade, que ce processus va se poursuivre… Il y a peut-être un piège ? Ou non…

Comment faire ? Peut-on faire une infinité de vérifications manuelles ? Non, impossible…
Il va falloir donc raisonner autrement, plus généralement… Et c’est dans ce type de situation que le raisonnement par récurrence peut nous venir en secours ! Une vérification sur les premiers termes ou les premières étapes n’est pas suffisante pour affirmer qu’elle se généralise à tous les termes ou toutes les étapes ! Il existe de nombreuses situations mathématiques qui vont bien au début et puis qui tournent mal à partir d’un certain moment. On appelle cela des « fausses conjectures ».  Vous voulez en voir ? Pas de problèmes, en voici quelques unes…

Fausse conjecture n°1

n^5-10n^4+35n^3-50n^2+24n+2 est égal à 2

Toujours vrai ou non ?

 

Faisons un tableau comme précédemment :

Valeur de n n^5-10n^4+35n^3-50n^2+24n+2
0 2
1 2
2 2
3 2
4 2

Cela semble fonctionner comme précédemment…
Et pourtant, pour n=5, on obtient 122… Catastrophe !
La propriété P(n) : n^5-10n^4+35n^3-50n^2+24n+2=2 est donc vraie pour n=0, pour n=1, n=2, pour n=3, pour n=4 mais pas pour n=5… Elle n’est donc pas vraie pour tout n !

Encore plus fou, voici une autre conjecture fausse (due au mathématicien Euler) :

Fausse conjecture n°2

n^2 + n + 41 est un nombre premier.

Toujours vrai ou non ?

 

Là encore, faisons un tableau pour examiner comment les choses se passent au début :

Valeur de n n^2 + n + 41 Résultat
0 41 nombre premier
1 43 nombre premier
2 47 nombre premier
3 53 nombre premier
4 59 nombre premier
5 71 nombre premier

Et là, vous pouvez continuer longtemps, longtemps… vous allez longtemps trouver un nombre premier comme résultat. À tel point que vous allez finir par être convaincu que cette conjecture est vraie… Il faut aller jusqu’à l’étape n=40 pour avoir un contre-exemple. En effet, lorsque n=40, on a :

40^2 + 40 + 41 = 40(40 + 1) + 41 = 40 \times 41 + 41 = 41(40 + 1) = 41^2

Et 41^2 est évidemment un nombre composé (c’est-à-dire non premier).
La propriété P(n) : n^2 + n + 41 est un nombre premier est donc vraie pour n allant de 0 à 39 mais pas pour n=40… C’est flippant hein ?

Nous venons donc de constater que lorsqu’on considère une propriété mathématique  P(n), on peut rencontrer toutes sortes de scénarios : elle peut être vraie au début mais plus à partir d’un certain rang, elle peut être toujours fausse, elle peut être fausse au début et devenir toujours vraie à partir d’un certain rang, elle peut être toujours vraie etc.

Le principe de raisonnement par récurrence va nous servir uniquement pour démontrer que la propriété mathématique est vraie pour tous les entiers n (ou à la rigueur vraie à partir d’un certain entier n_0).

Nous avons assez parlé, il est temps de coucher noir sur blanc ce fameux principe de raisonnement :

Considérons une propriété P(n).

SI les deux conditions suivantes sont satisfaites :

1°) On a P(n_0) (autrement dit, la propriété est satisfaite à partir d’un certain rang n_0) (initialisation) ;

2°) P(n) \Longrightarrow P(n+1) pour tout n \geq n_0 (autrement dit, le fait que la propriété soit satisfaite au rang n implique le fait qu’elle soit satisfaite au rang n+1) (hérédité).

ALORS

On aura P(n) pour tout n \geq n_0. (autrement dit, la propriété sera satisfaite à tous les rangs à partir de n_0).

C’est exactement comme le principe des dominos exposé en début d’article.

Mais une difficulté demeure… Elle concerne la fameuse étape appelée hérédité
Comment prouver les implications P(n) \Longrightarrow P(n+1) ?
N’a-t-on pas juste déplacé le problème ?
Au départ, nous voulions prouver qu’une propriété est vraie pour tous les entiers et nous voilà à devoir prouver que l’on a l’implication P(n) \Longrightarrow P(n+1) pour tous les entiers… En quoi cela serait-il plus facile ?Eh bien, ce n’est pas forcément plus facile. En réalité, tous dépend des informations que l’on dispose ! Si on nous demande de prouver que :

3^n-1 est un nombre pair, quel que soit l’entier n

il n’y a point besoin de récurrence : on peut faire un raisonnement direct en disant que le produit de nombres impairs est toujours un nombre impair. Par conséquent, 3^n est un nombre impair, quel que soit n. On en déduit bien que 3^n-1 est un nombre pair, quel que soit l’entier n. Nous n’avons pas eu besoin de faire de récurrence. On a pu prouver directement que la propriété est vraie pour tous les entiers, en s’appuyant sur d’autres connaissances (le produit de nombres impairs).

Mais reprenons maintenant le cas de 6^n-1 évoqué plus haut. Peut-on adapter le raisonnement que nous venons de faire ? On pourrait dire que 6^n est un multiple de 6. Et puis ? Le fait de retrancher 1 à un multiple de 6 donne-t-il obligatoire un multiple de 5 ? Non bien sûr… Penser à 12 ou 18 par exemple. Dans ce cas là, le raisonnement direct semble plus difficile à élaborer (nous n’avons pas dit impossible…). Alors voyons si ce n’est pas plus simple de prouver l’hérédité, c’est-à-dire le caractère transmissible d’une propriété. Supposons, momentanément, que 6^n-1 soit effectivement un multiple de 5. Cela signifierait qu’il existe un entier k tel que :

6^n-1 = 5k

sous cette hypothèse, qu’en est-il de 6^{n+1}-1 ?
Effectuons un petit calcul mené stratégiquement pour faire le lien entre l’étape n et l’étape n+1 :

6^{n+1}-1 = 6 \times 6^n - 1 = 6 \times 6^n - 6 + 5 = 6(6^n - 1) + 5

Or, nous avons supposé que 6^n-1 = 5k. On peut donc poursuivre le calcul :

6^{n+1}-1 = 6 \times 5k + 5 = 30k + 5 = 5 \times (6k + 1)

Notons k' l’entier 6k + 1.

Ainsi, le calcul précédent montre que :

6^{n+1}-1 = 5k'

Cela signifie-t-il que 6^{n+1}-1 est assurément un multiple de 5 ?… Hum… on pourrait être tenté de le dire… Mais, pas si vite… Attendez… N’oublions pas que nous avions fait une hypothèse au départ, à savoir que 6^n-1 était un multiple de 5. Alors, que montre le calcul précédent ?

Il montre que SI 6^n-1 est un multiple de 5, ALORS à son tour,  6^{n+1}-1 est aussi un multiple de 5. Et cela, quel que soit l’entier n considéré. Mais, mais, mais… nous venons donc de démontrer le caractère héréditaire de la propriété ! Et comme, par ailleurs, la propriété est initialisée puisque pour n=0, on a 6^0-1= 1-1=0=0 (faut-il rappeler que 0 est un multiple de tous les entiers, donc en particulier de 5), le raisonnement par récurrence s’achève et nous permet d’affirmer, en conclusion, qu’effectivement, pour tous les entiers naturels n, 6^n-1 est bien un multiple de 5.

Finalement, quand est-ce qu’il faut privilégier un raisonnement par récurrence par rapport à un raisonnement direct ?

On privilégie le raisonnement par récurrence lorsqu’il est plus facile de prouver le caractère héréditaire que de prouver le caractère de vérité !
Autrement dit, lorsqu’il est plus facile de prouver que :

pour tout n, P(n) \Longrightarrow P(n+1)

que :

pour tout n, P(n)

Bien noter que le caractère héréditaire ne devient vrai que s’il initialisé. En l’absence d’initialisation, une propriété peut très bien être héréditaire sans être vraie ! (Voir les compléments en fin d’article)

Tout cela est très littéraire. Mais concrètement, comment rédiger la récurrence précédente de façon synthétique ? C’est la deuxième partie de cet article… La rédaction efficace et rigoureuse. Nous allons reprendre l’exemple précédent et donner d’autres exemples.

Partie II – Bien rédiger une récurrence

Exemple 1

Enoncé : démontrer que 6^n-1 est un multiple de 5, pour tout n.

 

Solution

• Considérons la propriété P(n) : il existe un entier k tel que 6^n-1=5k

• On a 6^0-1= 1 - 1 = 0 = 5 \times 0 d’où P(0).

• Soit n un entier naturel et supposons P(n) : il existe un entier k tel que 6^n-1=5k. Alors :

6^{n+1} - 1 = 6 \times 6^n - 1 = 6(5k + 1) - 1 = 30k + 5 = 5(6k + 1)

Il existe donc un entier k'=6k+1 tel que 6^{n+1} - 1 = 5k'.

On a donc montré que P(n) \Longrightarrow P(n+1) pour tout n \geq 0

• En conclusion, d’après le principe de raisonnement par récurrence, on a bien 6^n-1 est un multiple de 5, pour tout n.

 

On constate sur cet exemple que la rédaction d’une récurrence tient essentiellement en 4 points :

• on précise la propriété de travail P(n) ;

• on prouve que la propriété est initialisé (en 0 ou en n_0) ;

• on prouve que la propriété est héréditaire (à partir de 0 ou de n_0) ;

• on conclut.

Remarque sur l’exemple ci-dessus. Il y a très souvent plusieurs chemins pour parvenir à un résultat.

Une personne futée et expérimentée peut se passer de récurrence pour faire cette démonstration… Il suffit de considérer la somme suivante (qui est une somme de termes consécutifs d’une suite géométrique) :

\displaystyle \sum_{k=0}^{n-1} 6^k = \frac{6^n-1}{5}

Et on constate immédiatement que 6^n-1 est un multiple de 5 puisque :

\displaystyle 6^n-1 = 5 \left(\sum_{k=0}^{n-1} 6^k \right)

Mais cette ruse (classique) n’est pas à la portée d’un élève standard arrivant en terminale.

Exemple 2 (avec une suite définie par récurrence)

Enoncé

On considère la suite (u_n) définie par :

\left\{\begin{array}{rcl}u_0&=&0\\u_{n+1}&=&3u_n-2n+3\end{array}\right.

Démontrer que pour tout entier naturel n, on a u_n \geq n

 

Solution

• Considérons la propriété P(n) : u_n \geq n

• On a u_0 = 0 \geq 0 d’où P(0).

• Soit n un entier naturel et supposons P(n) : u_n \geq n.

Alors :

u_{n+1}= 3 u_n - 2n + 3 \geq 3n - 2n + 3 \geq n + 1

Ce qui est P(n+1).

On a donc montré que P(n) \Longrightarrow P(n+1) pour tout n \geq 0

• En conclusion, d’après le principe de raisonnement par récurrence, on a bien u_n \geq n pour tout n.

Remarque : on en déduit, par comparaison, que : \displaystyle \lim_{n \to {+\infty}} u_n = {+\infty}

Exemple 3 (où l’initialisation est fixée à n=1)

Enoncé

Démontrer que pour tout entier naturel n \geq 1, on a \displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}

 

Solution

• Considérons la propriété P(n) : \displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} pour n \ge 1

• On a \displaystyle \sum_{k=1}^1 k^2 = 1 = \frac{1 \times 2 \times 3}{6} d’où P(1).

• Soit n un entier naturel supérieur à 1 et supposons :

P(n) : \displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.

Alors :

\displaystyle \sum_{k=1}^{n+1} k^2 = \sum_{k=1}^{n} k^2 + (n+1)^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2

Réduisons au même dénominateur et factorisons par (n+1) :

\displaystyle \sum_{k=1}^{n+1} k^2 = \frac{(n+1)\bigl[n(2n+1)+6(n+1)\bigr]}{6}

\displaystyle \sum_{k=1}^{n+1} k^2 = \frac{(n+1)(2n^2+7n+6)}{6} = \frac{(n+1)(n+2)(2n+3)}{6}

Ce qui est P(n+1).

On a donc montré que P(n) \Longrightarrow P(n+1) pour tout n \geq 1

• En conclusion, d’après le principe de raisonnement par récurrence, on a bien \displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.

Remarque sur l’exemple ci-dessus : on peut se demander comment calculer la somme si on n’a pas conjecturé la formule ?… Et c’est là qu’on prend conscience d’une faiblesse du raisonnement par récurrence :

On ne peut envisager une récurrence que si l’on a conjecturé la propriété à démontrer !

Un élève standard peut-il deviner la formule pour calculer la somme des carrés des n premiers entiers naturels non nuls ?

\displaystyle \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

Pas vraiment non… Alors heureusement qu’elle est gentiment proposée dans l’énoncé !
Mais si cela intéresse le lecteur, on peut la retrouver par télescopage
Hein ? Quoi ? C’est quoi ce nouveau truc encore ?

Par linéarité de la somme :

\displaystyle \sum_{k=1}^n (k+1)^3 = \sum_{k=1}^n k^3 + 3\sum_{k=1}^n k^2 +3\sum_{k=1}^n k +\sum_{k=1}^n 1

\displaystyle \sum_{k=1}^n (k+1)^3 - \sum_{k=1}^n k^3 = 3\sum_{k=1}^n k^2 + 3\frac{n(n+1)}{2}+ n

Par télescopage, les deux sommes du membre de gauche se compensent sauf deux termes extrêmes :

\displaystyle (n+1)^3 - 1 = 3\sum_{k=1}^n k^2 + 3\frac{n(n+1)}{2}+ n

\displaystyle n^3 + 3n^2 + 3n = 3\sum_{k=1}^n k^2 + 3\frac{n(n+1)}{2}+ n

Multiplions par 2 :

\displaystyle 2n^3 + 6n^2 + 6n = 6\sum_{k=1}^n k^2 + 3n(n+1)+ 2n

Factorisons par n :

\displaystyle n \bigl[2n^2 + 6n + 6 - 3(n+1)-2\bigr] = 6\sum_{k=1}^n k^2

\displaystyle n(2n^2 + 3n + 1) = 6\sum_{k=1}^n k^2

Or, on constate facilement que 2n^2 + 3n + 1=(2n+1)(n+1) d’où :

\displaystyle 6\sum_{k=1}^n k^2 = n(n+1)(2n+1)

D’où le résultat… Mais tout ça, c’est une autre histoire !

Partie III – Compléments

Exemple de propriété héréditaire ET fausse

Considérons la suite (u_n) définie par

\left\{\begin{array}{rcl}u_0&=&2\\u_{n+1}&=&3u_n-2\end{array}\right.

Et considérons la propriété suivante :

P(n) : u_n = 1

Il est très facile de prouver que cette propriété est héréditaire pour n \geq 0. En effet, supposons que l’on ait P(n) : u_n = 1 pour un certain n \geq 0, alors :

u_{n+1} = 3 u_n - 2 = 3 \times 1 - 2 = 1

Et cela correspond à l’énoncé de P(n+1).

On a donc bien P(n) \Longrightarrow P(n+1) pour tout n \geq 0.

Cette propriété est héréditaire.

Mais soyons fou et formulons une autre propriété affirmant, pour chaque indice n, exactement le contraire de la propriété précédente :

Q(n) : u_n \neq 1

Il est très facile de prouver que cette nouvelle propriété est également héréditaire pour n \geq 0. En effet, supposons que pour un certain n \geq 0, on ait :

Q(n) : u_n \neq 1

Alors :

3 u_n \neq 3

3 u_n - 2 \neq 1

C’est-à-dire :

u_{n+1} \neq 1

Et cela correspond à l’énoncé de Q(n+1).

On a donc bien Q(n) \Longrightarrow Q(n+1) pour tout n \geq 0.

Cette propriété est aussi héréditaire.

On voit sur cet exemple que des propriété opposées, qui affirment une chose et son contraire peuvent toutes deux être héréditaires. Or, manifestement, elles ne peuvent pas toutes deux être vraies ! Alors, laquelle des deux est vraie ? Eh bien, celle qui est initialisée et c’est la propriété Q qui l’est puisque u_0 \neq 1. Du coup, la propriété P ne sera jamais initialisée (puisqu’aucun terme de la suite ne vaut 1). C’est donc une propriété tout le temps fausse… Alors qu’elle était héréditaire…

 

Exemple de propriété initialisée à un certain rang mais héréditaire à partir d’un autre rang

Pour que le principe de récurrence s’applique, il est nécessaire que la propriété soit initialisée à un certain rang ET qu’elle soit héréditaire à partir DU MÊME RANG ! Si l’hérédité commence à un rang strictement supérieur de celui de l’initialisation, alors on ne peut rien en déduire !

C’est ainsi qu’on peut élaborer subtilement de fausses démonstrations du genre :

« tous les points du plan sont alignés »

En effet, considérons la propriété suivante :

P(n) : n points du plan sont toujours alignés pour n \geq 1

Il est clair qu’un point seul est toujours aligné avec lui même, on a donc P(1).
On a aussi P(2) puisque deux points sont toujours alignés.

Cette propriété est donc initialisée pour n=1.

Voyons l’hérédité et supposons P(n) pour n \geq 1.
Considérons alors une famille de n+1 points que nous noterons :

A_1, A_2, ... , A_{n}, A_{n+1}

Alors, d’après notre hypothèse de récurrence, nous savons d’une part que dans la sous-famille de n points A_1, A_2, ... , A_{n}, ils sont tous alignés. Mais, par ailleurs, dans la sous-famille de n points A_2, ... , A_{n}, A_{n+1}, ils sont également tous alignés. Par conséquent, le point A_{n+1} est aligné avec les précédents. D’où P(n+1).

En conclusion : quelle que soit la famille de n points donnés, ils seront donc toujours alignés… ???

Où est la faille ?

La faille est dans le raisonnement que nous faisons pour l’hérédité. Ce raisonnement est correct à condition d’avoir au moins trois points au départ ! Si on n’en a que deux, on voit facilement en faisant un dessin qu’on ne peut pas en déduire qu’un troisième point sera aligné avec les deux premiers. En fait, la propriété est héréditaire pour n \geq 3. Mais elle n’est initialisée que pour n=1 et n=2, pas pour n=3 ! Le principe de raisonnement par récurrence ne peut donc pas s’appliquer !

Une réflexion au sujet de « Comment bien mener et rédiger une récurrence en mathématiques ? »

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

CAPTCHA
Change the CAPTCHA codeSpeak the CAPTCHA code