À propos des exercices et quiz

“Practice, note innate talent, is what makes the difference in exceptional human achievment. ”

Malcolm Gladwell

Sur les exercices

Les exercices jouent un rôle central dans l’apprentissage d’une matière, puisqu’ils représentent le moment où on doit résoudre un problème à l’aide de ce qui a été étudié dans le cours.

Face à un nouvel exercice, la première chose à faire est de comprendre son énoncé. Donc il s’agira de lire l’énoncé, plusieurs fois si nécessaire, pour être sûr que vous comprenez tous les termes qu’il contient, et que vous voyiez ce qu’on vous demande. Si nécessaire, reprenez les définitions du cours.

Les exercices ne sont pas juste des “choses à calculer”: beaucoup sont théoriques et demandent de maîtriser les définitions et les résultats du cours. Donc il ne sert à rien de se lancer dans un calcul si on n’a pas compris la moitié des termes utilisés dans l’énoncé.

Vous avez plusieurs moyens d’avancer dans la résolution des problèmes. Il y a les assistant.es à la séance d’exercices bien sûr, il y a l’aide que vous trouvez en discutant avec vos collègues de travail, mais aussi d’autres outils en ligne, faits pour vous aider à avancer individuellement:

Certains exercices sont accompagnés d’indications (vous ne les voyez que si vous accédez aux exercices en ligne, ces indications ne sont pas sur le pdf), en accédant à l’onglet “Indications”; celles-ci fournissent des indices dont le but est d’arriver à faire un premier pas dans la résolution.
Vous avez la possibilité de poser des questions sur cet exercice, que ce soit avant, pendant, ou après la séance d’exercices, en ouvrant l’onglet “Forum”. Avant de poser une question, vérifiez si elle n’a pas déjà été posée par quelqu’un d’autre! Un autre étudiant, un assistant ou moi-même y aura probablement déjà répondu. Vous pouvez aussi commenter ou “liker” les questions/réponses des autres.
Faites bon usage du forum associé à un exercice: s’y rendre trop tôt pour chercher de l’aide risque de vous faire obtenir des informations que vous auriez peut-être obtenu tout-e seul-e en réfléchissant un peu. Un peu comme aller regarder la solution d’un exercice avant d’avoir essayé tout-e seul-e...

“A good course is a course with many stupid questions. ”

Wendelin Werner,Rio de Janeiro, 2008

Ne pensez pas que vous êtes sensés arriver à faire tous les exercices facilement, en compilant directement ce qui a été dans le cours. Il est normal de ne pas arriver à faire un exercice tout de suite sans fautes: ça fait partie intégrante de l’apprentissage!

Les solutions seront disponibles peu après la séance d’exercices. Alors soyons clairs: lire la solution d’un problème sans avoir essayé de le faire avant, c’est comme si on n’avait RIEN fait. Vous pouvez lire et relire la solution d’un exercice, vous dire que vous l’avez “comprise”, peut-être même la reproduire sans faute; ça ne veut pas du tout dire que vous serez capable de résoudre un autre exercice du même genre.

Il faut savoir que le processus d’apprentissage par lequel on passe, lorsqu’on sèche sur un problème, est utile pour une multitude d’autres choses, en plus de l’exercice lui-même...

Sur les quiz

Des quiz apparaissent à la fin de pratiquement toutes les sections du polycopié.

Le but d’un quiz est de vous permettre de voir si vous avez compris la matière qui vient de vous être présentée, en vous posant simplement une suite de questions du type “Vrai ou Faux”? En général, on peut y répondre sans faire aucun calcul.

Il est essentiel de tous les faire. Relisez le cours, lisez les questions qu’on vous pose, réfléchissez, choisissez vos réponses, puis checkez en appuyant sur “Réponses”. Les quiz vous fournissent un moyen de vous auto-évaluer, ne manquez pas cette occasion!

Dans un quiz, répondre “Vrai” signifie que l’on doit pouvoir donner une petite justification à l’aide de ce qui a été présenté dans le cours. Répondre “Faux” doit pouvoir s’accompagner d’un contre-exemple. Par exemple, pour démontrer que l’affirmation “toute fonction continue est dérivable” est fausse, on peut donner le contre-exemple de la fonction

f (x) = ∣ x ∣

, qui est continue partout mais pas dérivable en

x_{0} = 0

Parfois, trouver un contre-exemple peut être plus difficile. L’affirmation “Toute fonction continue est dérivable en au moins un point” est aussi fausse, mais exhiber un contre-exemple requiert un certain travail...

La méthode de preuve par récurrence (appelée aussi preuve par induction) est une technique de démonstration qui, quand elle s’applique, permet de démontrer une infinité d’affirmations en seulement deux étapes.

Supposons que l’on définisse, pour chaque entier

n ⩾ 1

, une certaine propriété

P (n)

. Pour chaque

n

P (n)

est soit vraie, soit fausse.

Exemple II.17.

Soit

P (n) =

“le nombre entier

n

est divisible par

2

”. Alors

P (1)

est fausse,

P (2)

est vraie,

P (3)

est fausse, etc. Donc on peut tout de suite résoudre tous les cas:

P (n)

est vraie si

n

est pair, fausse si

n

est impair.

En mathématiques, on a souvent besoin de montrer qu’une infinité de propriétés sont vraies simultanément:

P (1)

est vraie,

P (2)

est vraie,

P (3)

est vraie, etc.
Si ces propriétés

P (n)

n’ont rien à voir les unes avec les autres, on n’a d’autre alternative que de les vérifier les unes après les autres.

Exemple II.18.

Supposons qu’un certain univers contienne une infinité de galaxies. Soit

P (n)

la propriété “il existe, dans cet univers, une galaxie dans laquelle on peut trouver exactement

n

planètes sur lesquelles on trouve de la vie”.
Si on fixe un

n

et qu’on se pose la question de savoir si

P (n)

est vraie ou fausse, on n’a qu’un seul moyen d’obtenir la réponse: parcourir tout l’univers jusqu’à trouver une galaxie contenant exactement

n

planètes sur lesquelles on trouve la vie.

Si on a de la chance, on peut espérer étudier la véracité de ces propriétés

P (n)

en profitant de certaines relations pouvant exister entre elles, pour des

n

différents.
Dans le cas de la récurrence, on s’intéresse à une relation entre les paires d’entiers consécutifs,

n

n + 1

, et la relation considérée est la suivante: si $P (n)$ est vraie, alors $P (n + 1)$ est vraie aussi.

Exemple II.19.

Dans l’exemple du dessus (galaxies), il n’y a aucune corrélation du genre entre les propriétés

P (n)

pour des

n

différents, puisque savoir que

P (n)

est vraie n’implique pas forcément que

P (n + 1)

soit vraie aussi.

Exemple II.20.

Supposons que l’on ait devant nous une très longue table sur laquelle sont posés une infinité d’ordinateurs, numérotés

1, 2, 3, \dots

. On découvre avec effroi que sur chacun de ces ordinateurs est installé un système opérationnel propriétaire, issu d’une grande compagnie.

On suppose que ces ordinateurs sont tous allumés, et que pour tout

n

, le

n

-ème ordinateur envoie constamment des données non-cryptées vers son voisin

n + 1

. Dans ce cas, il est absolument certain que si l’ordinateur

n

est infecté par un virus, alors l’ordinateur

n + 1

est infecté aussi. En d’autres termes, si on définit la propriété

P (n) =

“le

n

ème ordinateur est infecté par un virus”, on sait que si

P (n)

est vraie, alors

P (n + 1)

est vraie aussi.
Ceci a la conséquence suivante: si un seul de ces ordinateurs est infecté, alors tous les suivants le sont aussi. En particulier, si le premier est infecté, alors tous sont infectés.

La méthode de démonstration par récurrence consiste à donner une démonstration dans laquelle on utilise une structure semblable à celle de ce dernier exemple. On la résume comme suit:
Montrer par récurrence qu’une infinité de propriétés

P (n)

(

n = 1, 2, 3, \dots

) sont vraies, cela consiste

à vérifier que la première propriété $P (1)$ est vraie, (c’est l’initialisation), puis
à vérifier que quel que soit l’indice $n ⩾ 1$ , si $P (n)$ est vraie, alors cela entraîne que $P (n + 1)$ est vraie aussi (c’est le pas d’induction).

Si on peut effectivement vérifier ces deux étapes, alors 1. implique que

P (1)

est vraie, mais alors 2. implique que

P (2)

est vraie aussi, mais alors 2. implique que

P (3)

est vraie aussi, etc. Par ce procédé, on démontre donc bien que

P (n)

est vraie pour tout

n ⩾ 1

Informel II.3.Pour que le pas d’induction ait une chance de fonctionner, il faut évidemment que les propriétés

P (n)

P (n + 1)

puissent être mises en relation, quel que soit

n

! Et là, la difficulté est de travailler avec un

n

quelconque, dont on ne spécifie pas la valeur; dans les situations concrètes, ceci implique en général un calcul littéral, dans lequel on manipule ce

n

inconnu.

Exemple II.21.

Nous allons montrer que pour tout

n \in N^{*}

1 + 2 + 3 + 4 + \dots + n = \frac{n ( n + 1 )}{2}

Commençons par nommer les deux membres de l’identité ci-dessus, en posant

a_{n} := 1 + 2 + 3 + 4 + \dots + n, et b_{n} := \frac{n ( n + 1 )}{2} .

Pour un

n

spécifique pas trop grand, on peut toujours le vérifier en calculant la valeur de

a_{n}

, puis celle de

b_{n}

, puis de voir si elles sont égales. Par exemple,

pour $n = 1$ , on a $a_{1} = 1$ et $b_{1} = \frac{1 \cdot 2}{2} = 1$ , et donc $a_{1} = b_{1}$
pour $n = 2$ , on a $a_{2} = 1 + 2 = 3$ et $b_{2} = \frac{2 \cdot 3}{2} = 3$ , et donc $a_{2} = b_{2}$ .

On voit donc que

a_{1} = b_{1}

a_{2} = b_{2}

.
On pourrait continuer à vérifier la relation “

a_{n} = b_{n}

” pour des

n

toujours plus grands, en calculant séparément les nombres

a_{n}

b_{n}

“à la main”, et en vérifiant qu’ils sont effectivement égaux. Mais ceci n’exclut pas qu’il existe un

n

, éventuellement très grand, pour lequel

a_{n} \neq = b_{n}

!
Définissons donc, pour tout

n ⩾ 1

, la propriété

P (n)

comme étant: “pour l’entier

n

, on a

a_{n} = b_{n}

”. Montrons, par récurrence, que

P (n)

est vraie pour tout

n ⩾ 1

Initialisation: on a déjà vérifié plus haut, “à la main”, que $a_{1} = b_{1}$ , et donc on sait que $P (1)$ est vraie.
Pas d’induction: supposons que pour un $n$ donné (dont on n’a pas besoin de spécifier la valeur), $P (n)$ est vraie , c’est-à-dire que l’on a effectivement
$a_{n} = b_{n} .$
Pour montrer que ceci entraîne que $P (n + 1)$ est vraie, on va faire un calcul, à l’issue duquel on obtiendra que $a_{n + 1} = b_{n + 1}$ . Or la structure du problème fait que $a_{n + 1}$ peut être relié à $a_{n}$ . En effet,
$a_{n + 1} = 1 + 2 + 3 + 4 + \dots + n + (n + 1) = a_{n} + (n + 1) .$
Mais, puisque l’on est en train de supposer que $a_{n} = b_{n}$ , on peut l’utiliser et faire un peu d’arithmétique:
$a_{n + 1} = b_{n} + (n + 1) = \frac{n ( n + 1 )}{2} + (n + 1) = \frac{n ( n + 1 ) + 2 ( n + 1 )}{2} = \frac{( n + 1 ) ( n + 2 )}{2} .$
Mais puisque
$\frac{( n + 1 ) ( n + 2 )}{2} = \frac{( n + 1 ) (( n + 1 ) + 1 )}{2} = b_{n + 1},$
on a bien montré que $a_{n + 1} = b_{n + 1}$ . Ceci montre que si $P (n)$ est vraie, alors $P (n + 1)$ est vraie aussi.

On a donc bien montré que

P (n)

est vraie pour tout

n ⩾ 1

Remarque II.2.

En utilisant la même technique, on peut montrer que pour tout

n \in N

1^{2} + 2^{2} + 3^{2} + 4^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}

En fait il existe des formules semblables pour toute somme du type

1^{k} + 2^{k} + 3^{k} + \dots + n^{k},

où

k ⩾ 1

est un entier. Voir ici (Mathologer) pour plus d’informations.

Exemple II.22.

Posons, pour tout

n ⩾ 1

a_{n} = 1 0^{n} - 1

, et considérons l’affirmation

P (n)

définie par “

a_{n}

est un multiple de

9

”.

Pour $n = 1$ , on a $a_{1} = 1 0^{1} - 1 = 9$ , qui est un multiple de $9$ .
Supposons que $P (n)$ est vraie, c’est-à-dire que $a_{n}$ est un multiple de $9$ . Ceci s’exprime en disant qu’il existe un entier $k$ tel que $a_{n} = 9 k$ . Remarquons alors qu’on peut écrire
$a_{n + 1} = 1 0^{n + 1} - 1 = 10 \cdot 1 0^{n} - 1 = 10 (a_{n} + 1) - 1 = 10 (9 k + 1) - 1 = 9 (=: k^{'} 10 k + 1) .$
Or puisque $k$ est un entier, $k^{'} = 10 k + 1$ est aussi un entier. Donc $a_{n + 1} = 9 k^{'}$ : $a_{n + 1}$ est aussi un multiple de $9$ , et donc $P (n + 1)$ est vraie.

Ceci montre que

P (n)

est vraie pour tout

n ⩾ 1

II.7.1 La formule du binôme de Newton

Rappelons la définition des coefficients binômiaux. Pour un entier

n ⩾ 1

quelconque, et pour tout

1 ⩽ k ⩽ n

(k n) := \frac{n !}{k ! ( n - k )!}

En combinatoire,

(k n)

compte le nombre de façons d’arranger

k

objets indistingables dans

n

boîtes (un objet par boîte).

Lemme II.3.

(formule du binôme de Newton) Soient

x, y \in R

. Alors pour tout entier

n ⩾ 1

(x + y)^{n} = k = 0 \sum n (k n) x^{n - k} y^{k} .

Voir aussi la vidéo de Michael Penn.

Sur les exercices

Sur les quiz

II.7 Preuves par récurrence

II.7.1 La formule du binôme de Newton