La récurrence et ses variantes

Démarrons aujourd’hui notre étude de raisonnements mathématiques avec une méthode que certains d’entre vous connaissent sans doute déjà : la démonstration par récurrence. Le fondement de cette méthode sera expliqué ici puis nous vous en présenterons ses différentes variantes. Nous vous indiquerons pour quel type de questions utiliser l’une ou l’autre des variantes de la récurrence. De plus, au travers d’exemples, nous vous exposerons également la façon de rédiger correctement une récurrence.
A cette occasion, nous pointerons du doigt les erreurs fréquentes, à ne pas commettre.

La démonstration par récurrence s’applique dans le cadre suivant :
Soit P(n) une propriété dépendant de l’entier naturel n. Supposons que l’on vous demande de montrer que :
 – P(n) est vraie pour tous les entiers naturels n.
 – Ou bien que P(n) est vraie pour tous les entiers n supérieurs à un certain entier naturel fixé : n0.

Le principe de la démonstration par récurrence repose sur le cinquième axiome de Péano, que vous nous avons présenté en début de semaine :
Si un ensemble d’entiers naturels contient 0 et le successeur de chacun de ses éléments, alors cet ensemble est égal à N tout entier.

Expliquons à présent le principe, lequel se décompose en deux étapes.
On commence tout d’abord par montrer que la propriété P(n) est vraie lorsque n vaut 0.
C’est ce que l’on appelle l’initialisation de la récurrence.
Comme nous le verrons dans les exercices, cette première étape correspond généralement à une simple vérification numérique.
Puis l’on transmet cette propriété de proche en proche d’un entier naturel k à son successeur : l’entier k+1. Autrement dit, on prouve que pour tout entier naturel k, P(k) implique P(k+1). Cette seconde étape s’appelle la propagation ou l’hérédité.
Ainsi, de n=0, la propriété se transmet à n=1, puis de n=1 à n=2. Plus généralement , pour un entier k quelconque, la propriété se propage de l’entier n=k-1 à l’entier n=k, puis de n=k à n=k+1, et ce procédé continue indéfiniment. Tous les entiers seront ainsi atteints.

Évoquons ici une légère variante.
Soit n0 un entier naturel fixé. Si l’on vous demande de démontrer que la propriété P(n) est vraie pour tout entier n supérieur à n0, l’initialisation se fait en montrant que P(n0) est vraie.
L’hérédité consistera alors à prouver l’implication P(k) implique P(k+1) pour tout entier k supérieur ou égal à n0.
Passons à un exemple pour voir la méthode en action et apprendre à rédiger correctement la récurrence.
Montrons que pour tout entier naturel n et tout réel x positif, (1+x) puissance n est supérieur ou égal à 1+nx.
Le premier travail consiste à identifier puis à poser la propriété P(n).
Il s’agit ici de « pour tout réel x positif, (1+x) puissance n supérieur à 1+nx. » Noter que l’on ne doit surtout pas inclure le « pour tout n dans N » dans l’expression de P(n) : ce serait une faute majeure de raisonnement, faute que l’on retrouve souvent dans les copies.
Ecrire P(n) signifie que l’on regarde la propriété à un rang n donné.
En revanche, il est indispensable de préciser dans P(n) le domaine de validité des autres variables.
Dans notre exemple, on doit donc inclure dans P(n) : « pour tout x dans R puissance +. » P(n) étant posée, débutons la récurrence proprement dite.
– Première étape : on initialise en vérifiant que la propriété est vraie pour n=0. Pour tout réel x de R puissance +, on calcule (1+x) puissance 0 qui vaut 1 et est donc bien supérieur ou égal à 1+0.x. La propriété P(0) est donc vérifiée.
 – Passons à la seconde étape : l’hérédité.
Supposons la propriété vraie pour un entier naturel k quelconque. Montrons, par implication, que la propriété est alors vraie au rang k+1. Pour tout réel x positif, on écrit (1+x) puissance (k+1) sous la forme (1+x) puissance k fois (1+x).
Or, par hypothèse de récurrence P(k), on sait que (1+x) puissance k est supérieur à 1+kx. En multipliant membre à membre cette inégalité par 1+x qui est positif, on trouve (1+x) puissance (k+1) supérieur à (1+kx).(1+x) autrement dit (1+x) puissance (k+1) supérieur à 1+(k+1).x+k.x puissance 2.
Or, comme kx puissance 2 est positif, cette dernière quantité est supérieure à 1+(k+1)x Ceci prouve la propriété pour l’entier k+1.
 – Par le principe de récurrence, on peut conclure que pour tout n entier naturel et tout x réel positif, (1+x) puissance n est supérieur ou égal à 1+nx.

Par opposition à cette récurrence dite simple, il existe d’autres formes de récurrence dites fortes.
Celle-ci sont employées lorsque la seule hypothèse P(k) ne suffit pas à prouver P(k+1).
Commençons par exposer le principe de récurrence double.
On veut démontrer que pour tout entier naturel n supérieur ou égal à un entier n0, une propriété P(n) est vraie.
Dans l’étape d’initialisation, on montre que P(n0) mais aussi P(n0+1) sont vérifiées.
Puis, dans l’étape d’hérédité, on montre l’implication suivante
 – si la propriété est vraie pour deux entiers consécutifs k et k+1, avec k supérieur à n0, alors elle est vraie pour l’entier suivant : k+2.
 – Par principe de récurrence double, on conclut alors que la propriété est vérifiée pour tout entier n plus grand que n0.

Enchainons tout de suite avec un exemple.
Soit (un) la suite réelle définie par la donnée de u0=1, u1=2 et par la relation suivante : pour tout entier naturel n, u(n+2)= 5u(n+1)-6un.
 – Il s’agit de montrer que pour tout entier n, un=2 puissance n.
Le premier travail est d’identifier la propriété P(n) à démontrer par récurrence.
Ici, c’est facile : il s’agit de un=2 puissance n .
 – On initialise la propriété pour les entiers n=0 et n=1.
D’après l’énoncé, u0=1 ce qui est bien égal à 2 puissance 0 : donc P(0) est vraie.
Toujours, d’après l’énoncé, u1=2 ce qui est bien égal à 2 puissance 1 : donc P(1) est vraie.
 – Passons à l’hérédité. Supposons la propriété vérifiée pour les entiers k et k+1.
 – Démontrons alors que la propriété est vraie pour l’entier k+2. D’après l’énoncé, u(k+2)= 5u(k+1)-6uk. En utilisant les hypothèses de récurrence P(k) et P(k+1), on transforme ceci en u(k+2)=5.2 puissance {k+1}-6.2 puissance {k} Soit 5.2 puissance {k+1}-3.2.2 puissance k. En factorisant, on obtient 2 puissance {k+1}. [5-3] donc 2 puissance {k+1}.2=2 puissance {k+2}. Ceci prouve que P(k+2) est vérifiée.
 – On conclut qu’en vertu du principe de récurrence double, la propriété P(n) est vraie pour tous les entiers naturels n.

Mais comment repérer que l’on doit faire une récurrence double, et non pas simple ? Ici, c’est relativement facile : voyez dans l’expression de la suite donnée dans l’énoncé, qu’un terme s’exprime en fonction des deux précédents.
Autrement dit, u{n+2} s’écrit en fonction de u{n+1} et de u{n} : c’est ce qui doit vous guider vers une récurrence double.
Le principe de récurrence double peut se généraliser de la façon suivante.
On veut montrer que pour tout entier naturel n supérieur ou égal à n0, une propriété
P(n) est vraie.
Dans l’étape d’initialisation, on montre que P(n0) est vraie.
Puis, dans l’étape d’hérédité, on montre l’implication suivante :
 – si la propriété est vraie pour tous les entiers compris entre n0 et k, alors elle est vraie pour l’entier : k+1.
 – Par principe de récurrence dite forte, on conclut alors que la propriété est vérifiée pour tout entier n plus grand que n0.

Illustrons cette méthode par un exemple. On considère la suite réelle (un) définie par la donnée de son premier terme u0=1 et par la relation suivante : pour tout entier naturel n, u{n+1} est la somme des termes précédents, c’est-à-dire u0+u1+…+un.
On peut noter cette somme avec la notation Sigma que certains d’entre vous connaissent sans doute déjà.
L’exercice consiste à montrer que pour tout entier naturel n non nul, un= 2 puissance {n-1}.
Comme ici, un terme de la suite est exprimé en fonction de TOUS les termes qui le précèdent, on s’oriente vers une récurrence forte.
Comme précédemment, le premier travail consiste à poser la propriété P(n) à démontrer : il s’agit ici de un=2 puissance {n-1}.
 – Passons ensuite à l’étape d’initialisation.
Comme l’énoncé nous indique que l’on doit prouver la propriété pour tout entier dans N*, l’initialisation se fait pour n=1. Toujours d’après l’énoncé, u1=u0=1 qui est bien égal à 2 puissance 0 autrement dit 2 puissance {1-1}.
Ceci prouve que P(1) est vraie.
 – Passons à l’hérédité.
Soit k un entier non nul.
Supposons la propriété vraie pour tous les entiers compris entre 1 et k.
D’après l’énoncé, u{k+1} est égal à la somme de u0, u1, u2… jusqu’à uk.
On sait d’ores et déjà que u0 vaut 1.
Par hypothèses de récurrence P(1), P(2) jusqu’à P(k), cela donne 1+2 puissance 0+2 puissance 1+….2 puissance {k-1}, autrement dit 1+ la somme des 2 puissance j, pour j variant de 0 à k-1.

D’après la formule donnant la somme des premiers termes d’une suite géométrique, on obtient 1+(1-2 puissance k)/(1-2). u{k+1} vaut donc 1-(1-2 puissance k), c’est-à-dire : 2 puissance k.
On a donc prouvé P(k+1), ce qui achève l’hérédité, et, par là-même, la récurrence.
Nous venons de vous expliquer comment mettre en œuvre une récurrence pour démontrer qu’une propriété P(n) est vraie pour tous les entiers n de N.
Et si l’on veut prouver une propriété pour tous les entiers n de Z, me direz-vous ? Étudions ce cas de figure sur un exercice.
On considère une fonction f de R puissance +* dans R vérifiant les hypothèses f(1)=0 et pour tout couple de réels x et y strictement positifs, f(x.y)=f(x+y).
On demande de montrer premièrement : que pour tout entier naturel n et pour tout réel x strictement positif, f(x puissance n)=nf(x).
Deuxièmement, on demande de propager la relation de N à Z, c’est-à-dire que montrer pour tout entier n dans Z cette fois et pour tout réel x strictement positif, f(x puissance n)=nf(x).
Vous aurez peut être reconnu ici les propriétés de la fonction logarithme népérien ln…
 – La première question se résout par une récurrence simple, en posant pour P(n) la propriété : « pour tout réel x strictement positif, f(x puissance n)=nf(x).
Je vous laissons rédiger la récurrence.
Passons à la seconde question.
Faisons une disjonction de cas.
 – Si l’entier n est dans N, la première question donne la réponse.
 – Si l’entier n est dans Z privé de N, on pose alors m=-n.
 – L’entier m est donc dans N, ce qui va permettre de se ramener à la première question. Expliquons de quelle manière.
 – Soit x un réel strictement positif.
 – On commence par appliquer la relation donnée par l’énoncé à x et à -x.
 – Comme f(1)=0, cela donne 0=f(1)=f(x .1/x)=f(x)+f(1/x).
 – On en déduit que pour tout réel x>0, f(1/x)=-f(x).
 – Ainsi, pour tout x strictement positif, f(x puissance n)=f(x puissance {-m})=f(1/xpuissance m) =-f(x puissance m), d’après ce que l’on vient de démontrer.
 – Par la question 1, comme m est dans N, -f(x puissance m)=-mf(x)=nf(x) : c’est ce qu’il fallait démontrer.
 – On constate donc que l’on ne fait pas de récurrence sur Z mais que l’on propage la relation de N à Z par le changement de variable m=-n. Cette petite astuce est à retenir.

Ceci achève la séquence consacrée aux méthodes de démonstration par récurrence.
A très bientôt.

Ce cours est extrait du module « Introduction au raisonnement mathématique : préparation à l’entrée dans l’enseignement supérieur » de Henri Lemberg et Magali Rocher tous deux docteurs agrégés en mathématiques.

Quadriques

L’intérêt de ce cours est d’acquérir des notions sur les quadriques.

En mathématiques, et plus précisément en géométrie euclidienne, une quadrique ou surface quadratique est une surface de l’espace euclidien de dimension 3, lieu des points vérifiant une équation cartésienne de degré 2 les coefficients A à J étant réels, avec A, B, C, D, E, F non tous nuls.

Géométriquement, les quadriques sont en quelque sorte à l’espace ce que les coniques sont au plan.

Pourquoi alors ne pas cliquer sur l’image ci-dessous pour en savoir plus.

  • Cours en vidéo :
  • Questions, remarques ou commentaires :

N’hésitez pas à donner votre avis ou à poser une question. Pour poster un commentaire, cliquez sur le titre de l’article. S’il y a toujours des incompréhensions même après avoir visionné la vidéo, si vous ne savez toujours pas faire malgré le temps que vous y avez passé, contactez-moi !

Des précisions sur le nouveau programme de maths du lycée [Baccalauréat 2021]

Deux nouvelles spécialités sont à découvrir et à choisir si vous souhaitez poursuivre vos études en mathématiques en classes de première et terminale :

  • Maths complémentaires ;
  • Maths expertes.

Les objectifs du nouveau programme sont :

Le programme insiste beaucoup plus sur la partie algorithmique des mathématiques. À chaque chapitre, un ou plusieurs algorithmes seront présentés ce qui permettra d’aborder les notions de façon plus concrètes.

Dans le cadre de cette activité algorithmique, les élèves sont entraînés à :
– décrire certains algorithmes en langage naturel ou dans un langage symbolique ;
– en réaliser quelques-uns à l’aide d’un tableur ou d’un programme sur calculatrice ou avec un logiciel adapté ;
– interpréter des algorithmes plus complexes.
Aucun langage, aucun logiciel spécifique n’est imposé.

L’algorithmique a une place naturelle dans tous les champs des mathématiques et les problèmes posés doivent être en relation avec les autres parties du programme (algèbre et analyse, statistiques et probabilités, logique), mais aussi avec les autres disciplines.

De manière générale, le nouveau programme de mathématiques au lycée est bien plus ambitieux que l’ancien programme.

Pour ceux qui souhaitent continuer en prépa, le nouveau programme de mathématiques couvre à présent une certaine partie du programme de première année de classe préparatoire ou de licence. Ainsi la transition Terminale/Prépa ou L1 devrait être moins brutale pour les élèves sérieux et travailleurs.

N’hésitez pas à partager vos propres conseils en commentaire. Pour poster un commentaire, cliquez sur le titre de l’article.

Négation, conjonction et disjonction

En mathématiques, pour relier les propriétés entre elles et en créer de nouvelles, avec des sens nouveaux, on trouve ce qu’on appelle des connecteurs.
Nous allons ici les introduire en faisant référence à chaque fois aux opérations ensemblistes que nous avons étudiées.

Considérons E un ensemble non vide et P(x) une propriété de la variable x, élément de E. Comme nous l’avons expliqué précédemment, cette propriété caractérise un sous-ensemble A de E : celui constitué de tous les éléments x de E pour lesquels P(x) est vraie. Cet ensemble A admet un complémentaire dans E : A barre. On considère alors la propriété Q(x) tel que A barre est l’ensemble des x de E pour lequel Q(x) est vraie. La propriété Q(x) s’appelle la négation de P(x) et se note ainsi. Ceci se lit non P(x) ou non P, en omettant la variable. Prenons par exemple pour E l’ensemble des entiers naturels. Soit P(x) la propriété « x est un nombre pair ». L’ensemble A des éléments de E vérifiant la propriété P est l’ensemble des entiers pairs. Le complémentaire de A dans E est donc l’ensemble A barre, des entiers impairs. La négation de la propriété P(x) est donc la propriété : « x est un nombre impair ». Nous avons vu que pour une propriété, la valeur de vérité dépend des valeurs prises par la variable. Comparons les valeurs de vérité de P(x) et de sa négation non P(x). Reprenons notre exemple précédent avec la propriété P(x) « x est pair ». Dans le tableau, on remarque que P(5) est fausse et (non)(P)(5) est vraie tandis que P(4) est vraie et (non) (P)(4) est fausse.
On peut à présent écrire la table de vérité de la négation d’une propriété P. Dans la colonne de gauche, on écrit les valeurs de vérité de P. Dans la colonne de droite, on écrit, dans chaque cas, les valeurs de vérité de sa négation.
On remarque que P est vraie lorsque sa négation est fausse et qu’à l’inverse, P est fausse lorsque sa négation est vraie. Ce tableau de vérité de la négation est calqué sur celui indiquant le lien entre un ensemble et son complémentaire.
Ainsi, si x est dans A, x n’appartient pas à A barre. Et si x n’est pas dans A, x appartient à A barre. Ce que nous vous expliquons là est une construction de la négation à partir de la théorie des ensembles.

Dans la pratique, vous n’aurez pas besoin de repasser à chaque fois par le sous ensemble correspondant pour écrire la négation d’une propriété. Il vous suffira de nier la propriété comme on le fait en français en passant de la forme affirmative à la forme négative. Ainsi, la négation de la propriété « M est une matrice inversible » est « M n’est pas une matrice inversible ». La négation de la propriété «f est une fonction continue sur l’intervalle I » est « f n’est pas une fonction continue sur I», autrement dit f est discontinue sur I.

Mais, attention aux erreurs classiques : la négation de la propriété « f est une fonction croissante sur I » est « f n’est pas une fonction croissante sur I », et surtout pas « f est une fonction décroissante sur I ».

Passons à un deuxième connecteur : la conjonction.

Nous allons définir celui-ci à partir de l’intersection des sous ensembles. Soit E un ensemble non vide. Soit P(x) et Q(x) deux propriétés de la variable x de E. Soit A l’ensemble des x de E tels que P(x) est vraie et B l’ensemble des x de E tels que Q(x) est vraie.
L’intersection de A et de B est donc l’ensemble des éléments x de E pour lesquels les propriétés P(x) et Q(x) sont vraies. Notons R(x) la propriété telle que A inter B soit égal à l’ensemble des éléments x de E pour lesquels R(x) est vraie.
La propriété R(x) est appelée la conjonction des propriétés P(x) et Q(x) et notée ainsi, ce qui se lit P(x) et Q(x), souvent abrégé en P et Q, en omettant la variable. Écrivons à présent la table de vérité de la conjonction. La conjonction de P et de Q est vérifiée lorsque les propriétés P et Q le sont. Si l’une ou l’autre est fausse, comme ceci, ou comme cela, ou si les deux sont fausses, alors la conjonction est fausse.
Cette table de vérité est à mettre en regard avec le tableau suivant qui indique selon
l’appartenance de l’élément x à A et à B, son appartenance à A inter B. En remarquant que les vrais correspondent à des symboles « appartient » et les faux à des symboles
« n’appartient pas », on voit l’analogie des situations : sur la dernière ligne, les deux précédentes ou encore la première. Passons à un exemple.
Plaçons-nous dans E l’ensemble des entiers naturels. Soit P(x) la propriété « x est un entier pair » et Q(x) la propriété « x est un multiple de 3 ». Cherchons la conjonction de P et de Q en passant par les ensembles associés. Chacune de ces propriétés définit un ensemble Pour P, il s’agit de l’ensemble A des entiers x de N tel qu’il existe un entier n tel que x=2n et pour Q, il s’agit de l’ensemble B des entiers x de N tel qu’il existe un entier m tel que x=3m.
Montrons que l’intersection des ensembles A et de B est égal à l’ensemble, noté C, des entiers multiples de 6. Pour cela, procédons par double inclusion. Supposons d’abord que l’entier x est dans l’ensemble C : x est donc un multiple de 6. Il s’écrit alors sous la forme x=6k, où k est un entier. Cette écriture montre que x est un multiple de 2 et de 3. L’entier x est donc dans A inter B.
Supposons à présent que x est dans A inter B. Il existe donc un entier n tel que x=2n et un entier m tel que x=3m. Ainsi, 2n=3m. Comme 2 divise 2k, 2 divise 3m. Puisque 2 et 3 sont deux entiers premiers entre eux, le lemme de Gauss implique que 2 divise m.
Il existe ainsi un entier p tel m=2p. On en déduit que x=3m=6p. Donc x est un multiple de 6. Ainsi, l’élément x est dans C. On conclut par double inclusion que A inter B est égal à C, l’ensemble des entiers multiples de 6. En revenant aux propriétés, on en déduit que la conjonction de P(x) et de Q(x) est la propriété « x est un multiple de 6 »

Passons à un troisième et dernier connecteur : la disjonction, connecteur lié à l’union ensembliste. Soit E un ensemble non vide.
Soit P(x) et Q(x) deux propriétés de la variable x. On considère à nouveau A : l’ensemble des x de E tels que P(x) est vraie et B : l’ensemble des x de E tels que Q(x) est vraie. L’union de A et de B est donc l’ensemble des éléments x de E pour lesquels P(x) ou Q(x) est vraie. Notons R(x) la propriété telle que A union B soit égal à l’ensemble des éléments x de E pour lesquels R(x) est vraie. La propriété R(x) est appelée la disjonction des propriétés P(x) et Q(x) et notée ainsi ce qui se lit P(x) ou Q(x), souvent abrégé en P ou Q, en omettant la variable x.
Écrivons la table de vérité de la disjonction. Si l’une ou l’autre des propriétés P et Q sont vraies, leur disjonction est vraie. La disjonction est fausse que si P et Q sont toutes les deux fausses. Bien sûr, la disjonction P ou Q est vraie si P et Q sont toutes les deux vraies : le « ou » n’est donc pas exclusif. Cette table de vérité est à mettre en regard avec le tableau suivant qui indique selon l’appartenance d’un élément x à A et à B, son appartenance à A union B.

Comme on l’a déjà constaté dans le cas de la conjonction, on note l’analogie entre
les lignes des tableaux : la dernière, les deux du milieu et la première. Passons à un exemple. Soit E l’ensemble des réels. Soit P(x) la propriété « x^2 est supérieur ou égal à 1 », et Q(x) la propriété « exponentielle (x) est inférieur ou égal à 1 ».

Cherchons la disjonction des propriétés P(x) et Q(x) en passant par les ensembles associés. A l’ensemble des réels x vérifiant la propriété P est égal à ]-infini, -1]union [1, +infini[. B l’ensemble des réels x vérifiant la propriété Q est quant à lui égal à ]-infini, 0]. L’union de A et de B correspond à l’union des trois intervalles ]-infini, -1] union [1, +infini[ union ]-infini, 0], ce qui donne la réunion des intervalles ]-infini,0] et [1,+infini[ .
La disjonction de P(x) et Q(x) est donc la propriété « x est négatif ou supérieur ou égal à 1». Terminons par une petite devinette. Soit P(x) une propriété de la variable x de E. Soit Q(x) sa négation. Que dire de la disjonction des propriétés P(x) et Q(x) ? Et que dire de leur conjonction ? Vous avez trouvé ? Passons par les ensembles. Soit A l’ensemble des éléments qui vérifient P. Soit B l’ensemble des éléments qui vérifient Q. Alors, B est le complémentaire de A. Il suit que A union B est égal à E tout entier. Ainsi, la disjonction de P(x) et de Q(x) est toujours vraie : on dit que c’est une tautologie. Toujours par caractérisation du complémentaire, A inter B est égal l’ensemble vide.
La conjonction de P et de Q n’est donc jamais vérifiée : c’est une propriété toujours fausse. Ceci porte le nom de contradiction. Nous verrons dans un prochain cours que tautologies et contradictions jouent un rôle assez important dans les raisonnements mathématiques.


Nous venons de vous présenter les trois principaux connecteurs logiques : la négation, la conjonction et la disjonction que nous avons défini à partir des opérations ensemblistes : la négation correspond au complémentaire, la conjonction à l’intersection et la disjonction à l’union.


Dans la pratique, on pourra écrire ces connecteurs sans revenir systématiquement aux opérations ensemblistes sous-jacentes la négation consistant, comme son nom l’indique, à prendre la négation de la propriété considérée, la conjonction consistant à relier les propriétés par la conjonction de coordination « et » et la disjonction à les relier par la conjonction de coordination « ou ».

Ce cours est extrait du module « Introduction au raisonnement mathématique : préparation à l’entrée dans l’enseignement supérieur » de Henri Lemberg et Magali Rocher tous deux docteurs agrégés en mathématiques.