Induction

La preuve par induction est souvent courte et commodément efficace, même économique, mais elle remplace parfois d’autres méthodes généralement plus riches et plus belles. On arrive parfois à se demander comment aurait-on pu « deviner » l’hypothèse d’induction (pensez à certaines preuves en analyse ou en mathématiques discrètes). Cela laisse à l’occasion un goût amer dans la bouche.

Voici donc une jolie preuve par induction, bien courte, d’un résultat qui semble de prime abord intangible et imperméable à nos lignes d’attaque habituelles.

On trace \(n\) droites dans le plan. Les régions ainsi formées par les \(n\) droites peuvent toujours être coloriées avec deux couleurs, de manière à ce qu’aucune région ait la même couleur que sa ou ses régions voisines, c’est-à-dire les régions qui partagent avec elle un segment de droite comme frontière.

thedudeminds_2013012502
L’énoncé fait peur parce qu’il autorise une grande liberté : combien de droites ? De quelles manières sont-elles placées ? Combien de régions ? Où commencer ? Et bien on commence par le cas le plus simple : on peut certainement colorier le plan avec deux couleurs, disons noir et blanc, lorsqu’il n’y a qu’une seule droite.
thedudeminds_2013012504Notre hypothèse d’induction est donc qu’on peut colorier les régions d’un plan contenant \(n\) droites. On considère un plan avec \(n+1\) droites. On enlève une droite parmi les \(n+1\) : il en reste seulement \(n\) et par l’hypothèse, il est possible de colorier les régions du plan formées par les \(n\) droites.thedudeminds_2013012502
On réintroduit la \((n+1)\)­ième droite.thedudeminds_2013012503Cette droite sépare le plan en deux demi-plans. On choisit un de ces deux demi-plans et on change systématiquement les couleurs dans chacune des régions de ce demi-plan : les régions noires deviennent blanches et les régions blanches deviennent noires. On laisse l’autre demi-plan (de l’autre côté de la droite) intact. Le plan est maintenant adéquatement colorié !thedudeminds_2013012501En effet,
  • si deux régions du plan séparé par les \(n+1\) droites ont une frontière composée d’un segment appartenant à une des premières \(n\) droites, alors ces régions avaient déjà des couleurs différentes avant l’introduction de la \((n+1)\)ième droite. En introduisant la \((n+1)\)ième droite, on laisse ces couleurs déjà différentes telles quelles ou on les changes toutes les deux.
  • si deux régions ont une frontière composée d’un segment appartenant à la \((n+1)\)ième droite, alors avant l’introduction de la \((n+1)\)ième droite, elles faisaient partie de la même région et donc étaient coloriées de la même couleur. En introduisant la \((n+1)\)ième droite, on change les couleurs d’une des deux régions, d’un côté de la droite, mais pas de l’autre. Ces régions nouvellement voisines ont donc maintenant des couleurs différentes.

Référence : Akiva Moiseevich Yaglom et Isaak Moiseevich Yaglom (1967), Challenging Mathematical Problems with Elementary Solutions Vol. II

Conjecture

Voici une belle situation de conjecture qu’on pourrait faire en première secondaire, après avoir vu comment trouver le ppcm et le pgcd de deux nombres. Les situations de conjecture sont au programme, et j’ai l’impression qu’on en fait trop peu souvent. C’est malheureux parce que c’est notamment dans ce genre de situations que les élèves mettent vraiment à profit leur créativité, c’est dans ces situations qu’ils font des mathématiques. Il me semble qu’ils ont parfois cruellement besoin d’un peu plus de ça et d’un peu moins de ça.

On choisit deux nombres entiers positifs. On calcule leur plus grand commun diviseur et leur plus petit commun multiple. Que pouvez-vous dire à propos du produit du ppcm et du pgcd de ces deux nombres ?

Par exemple, en choisissant les nombres \(24\) et \(36\), on obtient un pgcd de \(12\) et un ppcm de \(72\). Le produit demandé est donc égal à \(12\times72 = 864\). Hummmmm… C’est peut-être apparent pour vous et moi, mais des élèves de première ou deuxième secondaire auront certainement besoin de plusieurs autres exemples avant de conjecturer. Il serait donc utile de leur en fournir. Les élèves pourraient aussi eux-mêmes créer des exemples additionnels. On pourrait ainsi vérifier quels élèves utilisent des stratégies efficaces telles que prendre des petits nombres et des nombres premiers entre eux. En refaisant l’exercice avec les nombres \(6\) et \(7\), premiers entre eux, on a un pgcd de \(1\), et donc un ppcm de \(6\times 7 = 42\). Le produit du ppcm et du pgcd est donc \(1\times 42 = 42\), c’est-à-dire le produit des deux nombres du départ ! Coïncidence ? Conjecture !

Pour les plus vieux, on peut procéder en deux étapes. On choisit deux nombres \(a\) et \(b\). On pose\[\text{pgcd}(a,b)=k\]c’est-à-dire qu’on a\[a=kr,\ \ b=ks\]pour certains entiers \(r\) et \(s\) premiers entre eux. Incidemment, on a aussi \[\text{ppcm}(a, b) = krs\]c’est-à-dire \(s\) fois le nombre \(a\) et \(r\) fois le nombre \(b\). Comme \(s\) et \(r\) n’ont pas de facteur commun, il est impossible de trouver un plus petit multiple commun aux deux nombres. En outre, on a bien\begin{align*}\text{pgcd}(a,b)\cdot\text{ppcm}(a,b) &= k\cdot krs \\ \\ &=kr \cdot ks \\ \\ &=ab\end{align*}Le produit du ppcm et du pgcd de deux nombres est égal au produit des deux nombres.

Élémentaire mon cher Archimède…

Le nombre π est un nombre irrationnel.

La preuve qui suit est une preuve qu’on dit « élémentaire » et elle possède d’ailleurs l’avantage principal de toutes les preuves élémentaires : elle nécessite peu de résultats préalables. Dans ce cas-ci, on fera appel à quelques résultats de base de calcul différentiel (par exemple, dériver un produit de fonctions [1] ou dériver un certain nombre de fois une fonction polynomiale [2]), au théorème fondamental du calcul différentiel et intégral et à quelques propriétés de la fonction sinus, à savoir en particulier que \[\sin(\pi) = 0\]La preuve possède cependant les désavantages de (presque) toutes les preuves élémentaires de résultats difficiles : elle est plutôt longue, intriquée, et il est essentiellement impossible de justifier ou de donner une motivation pour les prochaines étapes, qui semblent parfois ne maintenir qu’un fil conducteur très ténu (non sans rappeler la preuve “élémentaire” de la valeur de ζ(2)). Dès lors, le lecteur perspicace se sent inévitablement trahi (désolé M. Pólya).

La preuve est essentiellement celle de Y. Iwamoto, parue dans le Journal of Osaka Institute of Science and Technology en 1949. La preuve de M. Iwamoto est une version plus forte de celle, plus célèbre, d’Ivan Niven [3] parue deux ans plus tôt. Dans sa monographie Irrational Numbers, Niven explique que sa preuve reprend et développe des idées basées sur celle de nul autre que Charles Hermite.

Comme cette preuve s’adresse à un public averti, on trouve dans la littérature peu de détails sur les étapes intermédiaires. Et comme mon blogue s’adresse à un public plus large, je vais tenter une approche plus près de celle empruntée par Michael Spivak dans son livre Calculus (4th edition), c’est-à-dire avec un peu plus d’explications. Ainsi, j’espère faire honneur malgré tout à M. Pólya [4] :

The advanced reader who skips parts that appear too elementary may miss more than the less advanced reader who skips parts too complex.

Dans ce qui suit, on notera \[f^{(k)}(x)\]la dérivée \(k\)ième de la fonction \(f\). On a donc en particulier pour les premières valeurs de \(k\) : \[f^{(0)}(x) = f(x), \quad f^{(1)}(x) = f^{\prime}(x), \quad f^{(2)}(x) = f^{\prime \prime}(x)\]On considère d’abord la fonction suivante \[f_{n}(x) = \frac{x^{n}(1-x)^{n}}{n!}\]Il est évident que pour \[0<x<1\]la fonction satisfait \[0<f_{n}(x)<\frac{1}{n!}\]Si on développe le binôme entre parenthèses, et qu’on distribue par la suite \(x^{n}\), on obtient au numérateur un polynôme de degré \(2n\), c’est-à-dire qu’on peut exprimer la fonction \(f_{n}\) comme \[f_{n}(x) = \frac{1}{n!}\sum_{i=n}^{2n}c_{i}x^{i}\]pour certaines valeurs entières de \(c_{i}\) (on pourrait exprimer ces valeurs avec le binôme de Newton mais c’est, dans cette preuve, sans importance). On considère les dérivées \(k\)ième de \(f_{n}\). Il est clair que \[f_{n}^{(k)}(0) = 0\]si \[k<n\]puisque dans ce cas, il ne reste que des termes en \(x\), ou si \[k>2n\]puisque dans ce cas, on dérive un nombre plus grand de fois que le degré du polynôme. Pour \[n\leq k \leq 2n\]on a \begin{align*}f_{n}^{(n)}(x) &= \frac{1}{n!}\left(n!\, c_{n}+\left(\text{des termes en }x\right)\right) \\ \\ f_{n}^{(n+1)}(x) &= \frac{1}{n!}\left(\left(n+1\right)! \, c_{n+1}+\left(\text{des termes en }x\right)\right) \\ \\ &\vdots \\ \\ f_{n}^{(2n)}(x) &=\frac{1}{n!}\left(\left(2n\right)!\, c_{2n}\right)\end{align*}ce qui fait \begin{align*}f_{n}^{(n)}(0) &= \frac{1}{n!}\left(n!\, c_{n}\right) = c_{n} \\ \\ f_{n}^{(n+1)}(0) &= \frac{1}{n!}\left(\left(n+1\right)! \, c_{n+1}\right) = \frac{1}{n!}\cdot n! \cdot \left(n+1\right)c_{n+1} = \left(n+1\right)c_{n+1} \\ \\ &\vdots \\ \\ f_{n}^{(2n)}(0) &= \frac{1}{n!}\left(\left(2n\right)! \, c_{2n}\right) = \frac{1}{n!}\cdot \left(2n\right)\left(2n-1\right) \dots \left(n+1\right) \cdot n! \cdot c_{2n} = \left(2n\right)\left(2n-1\right)\dots \left(n+1\right)c_{2n}\end{align*}Tous les termes à droites sont des nombres entiers. Ainsi, l’expression \[f_{n}^{(k)}(0)\]représente toujours un nombre entier, quelle que soit la valeur de \(k\). Par ailleurs, on a \begin{align*}f_{n}(1-x) &= \frac{\left(1-x\right)^{n}\left(1-\left(1-x\right)\right)^{n}}{n!} \\ \\ &=\frac{x^{n}\left(1-x\right)^{n}}{n!} \\ \\ &=f_{n}(x)\end{align*}ce qui nous permet de trouver en particulier \[f_{n}^{(k)}(x)= \left(-1\right)^{k}f_{n}^{(k)}\left(1-x\right)\]et de conclure que l’expression\[f_{n}^{(k)}(1)\]représente elle aussi toujours un nombre entier. Avant d’introduire d’autres fonctions savamment construites à partir de \(f_{n}\), on s’attarde à une courte remarque. Si \(a\) est un nombre positif, alors pour tout \(\epsilon > 0\), on a, pour un \(n\) suffisamment grand, \[\frac{a^{n}}{n!} < \epsilon\]On peut d’abord observer que si \(n\geq 2a\), on a \begin{align*} \frac{a^{n+1}}{\left(n+1\right)!} &= \frac{a \cdot a^{n}}{\left(n+1\right)n!} \\ \\ &= \frac{a}{n+1}\cdot \frac{a^{n}}{n!} \\ \\ &< \frac{1}{2}\cdot \frac{a^{n}}{n!}\end{align*}
Incidemment, en posant \(n_{0}\) un nombre naturel tel que\[n_{0}\geq 2a\]qu’importe la valeur de \[\frac{a^{n_{0}}}{\left(n_{0}\right)!}\]les valeurs successives seront \begin{align*}\frac{a^{\left(n_{0}+1\right)}}{\left(n_{0}+1\right)!}&< \frac{1}{2}\cdot \frac{a^{n_{0}}}{\left(n_{0}\right)!} \\ \\ \frac{a^{\left(n_{0}+2\right)}}{\left(n_{0}+2\right)!}&<\frac{1}{2}\cdot \frac{a^{\left(n_{0}+1\right)}}{\left(n_{0}+1\right)!}<\frac{1}{2}\cdot \frac{1}{2}\cdot \frac{a^{n_{0}}}{\left(n_{0}\right)!}\\ \\ &\vdots \\ \\ \frac{a^{\left(n_{0}+k\right)}}{\left(n_{0}+k\right)!} &< \frac{1}{2^{k}}\cdot \frac{a^{0}}{\left(n_{0}\right)!}\end{align*}De cela on tire, en choisissant correctement une valeur de \(k\) assez grande, \[\frac{a^{n_{0}}}{\left(n_{0}\right)! \, \epsilon}< 2^{k}\]et donc obtenir\[\frac{a^{\left(n_{0}+k\right)}}{\left(n_{0}+k\right)!}<\epsilon\]soit le résultat attendu. On s’attaque maintenant à l’irrationalité du nombre \(\pi\). On va cependant démontrer un résultat encore plus fort, l’irrationalité de \(\pi^{2}\). En effet, si \(\pi\) était rationnel, alors \(\pi^{2}\) serait certainement lui aussi rationnel. La preuve fonctionne par contradiction. On suppose donc que \(\pi^{2}\) est rationnel et que\[\pi^{2}=\frac{a}{b}\]avec \(a\) et \(b\) des entiers positifs premiers entre eux. On introduit la fonction \(G\) suivante \[G(x) = b^{n}\left(\pi^{2n}f_{n}(x)-\pi^{2n-2}f_{n}^{\prime \prime}(x)+\pi^{2n-4}f_{n}^{\left(4\right)}(x)- \ \dots \ +\left(-1\right)^{n}f_{n}^{\left(2n\right)}(x)\right)\]Lorsqu’on distribue \(b^{n}\) dans la parenthèse, on obtient des coefficients des termes en \(f_{n}^{\left(k\right)}\) de la forme \begin{align*}b^{n}\pi^{2n-2k}&=b^{n}\pi^{2\left(n-k\right)} \\ \\ &=b^{n}\left(\pi^{2}\right)^{n-k} \\ \\ &=b^{n}\left(\frac{a}{b}\right)^{n-k} \\ \\ &=a^{n-k}b^{k}\end{align*}c’est-à-dire tous des nombres entiers. Et puisque \[f_{n}^{\left(k\right)}(0)\]et \[f_{n}^{\left(k\right)}(1)\]sont des entiers, alors\[G(0)\]et\[G(1)\]sont eux aussi des entiers. On dérive la fonction \(G\) deux fois \[G^{\prime \prime}(x) = b^{n}\left(\pi^{2n}f_{n}^{\prime \prime}(x)-\pi^{2n-2}f_{n}^{\left(4\right)}(x)+\pi^{2n-4}f_{n}^{\left(6\right)}(x)- \ \dots \ +\left(-1\right)^{n}f_{n}^{\left(2n+2\right)}(x)\right)\]Le dernier terme, \[\left(-1\right)^{n}f_{n}^{\left(2n+2\right)}(x)\]est bien sûr zéro. Maintenant, on remarque qu’en multipliant \(G\) par \(\pi^{2}\), on obtient \begin{align*}\pi^{2}G(x) &=\pi^{2}\left(b^{n}\left(\pi^{2n}f_{n}(x)-\pi^{2n-2}f_{n}^{\prime \prime}(x)+\pi^{2n-4}f_{n}^{\left(4\right)}(x)- \ \dots \ +\left(-1\right)^{n}f_{n}^{\left(2n\right)}(x)\right)\right) \\ \\ &=b^{n}\left(\pi^{2n+2}f_{n}(x)-\pi^{2n}f_{n}^{\prime \prime}(x)+\pi^{2n-2}f_{n}^{\left(4\right)}(x)-\pi^{2n-4}f_{n}^{\left(6\right)}(x)+ \ \dots \ + \left(-1\right)^{n}\pi^{2}f_{n}^{\left(2n\right)}(x)\right)\end{align*}et qu’il est possible de faire la somme de \(G^{\prime \prime}(x)\) et \(\pi^{2}G(x)\) et d’observer que tous les termes s’annulent sauf un, afin d’obtenir \begin{align*}G^{\prime \prime}(x) + \pi^{2}G(x) &= b^{n}\pi^{2n+2}f_{n}(x) \\ \\ &=b^{n}\left(\frac{a}{b}\right)^{n}\pi^{2}f_{n}(x)\\ \\ &= \pi^{2}a^{n}f_{n}(x)\end{align*}On introduit enfin une dernière fonction \(H\) \[H(x) = G^{\prime}(x)\sin\!\left(\pi x\right)-\pi G(x)\cos\!\left(\pi x \right)\]Lorsqu’on dérive cette fonction, on obtient \[H^{\prime}(x) = G^{\prime \prime}(x)\sin\!\left(\pi x\right) + \pi G^{\prime}(x)\cos\!\left(\pi x\right)-\pi G^{\prime}(x)\cos\!\left(\pi x\right) + \pi^{2}G(x) \sin\!\left(\pi x\right)\]ce qui se simplifie en regroupant les deux termes qui s’annulent et en effectuant la mise en évidence \begin{align*}H^{\prime}(x) &=G^{\prime \prime}(x)\sin\!\left(\pi x\right) + \pi^{2}G(x)\sin\!\left(\pi x\right) \\ \\ &=\left(G^{\prime \prime}(x) + \pi^{2}G(x)\right)\sin\!\left(\pi x\right)\end{align*}En remplaçant l’expression entre parenthèses, on obtient \begin{align*}H^{\prime}(x)&=\left(G^{\prime \prime}(x)+\pi^{2}G(x)\right)\sin\!\left(\pi x \right) \\ \\ &=\pi^{2}a^{n}f_{n}(x)\sin\!\left(\pi x\right)\end{align*}On considère maintenant l’intégrale définie suivante \[\pi^{2}\int_{0}^{1}a^{n}f_{n}(x)\sin\!\left(\pi x\right) \text{d}x\]Le théorème fondamental du calcul différentiel et intégral nous permet d’écrire \begin{align*}\pi^{2}\int_{0}^{1}a^{n}f_{n}(x)\sin\!\left(\pi x\right)\text{d}x &= H(1)-H(0) \\ \\ &=G^{\prime}(1)\sin\!\left(\pi \cdot 1\right)-\pi G(1)\cos\!\left(\pi \cdot 1\right)-\left(G^{\prime}(0)\sin\!\left(\pi \cdot 0\right)-\pi G(0)\cos\!\left(\pi \cdot 0\right)\right) \\ \\ &= 0 + \pi G(1)-0 + \pi G(0) \\ \\ &=\pi \left(G(1)+G(0)\right)\end{align*}On a, à droite, une somme de termes constants multipliée par \(\pi\). De cela, en divisant par \(\pi\), on tire l’intégrale définie \[\pi \int_{0}^{1}a^{n}f_{n}(x)\sin\!\left(\pi x\right) \text{d}x = G(1)+G(0)\]c’est-à-dire un nombre entier ! Or, comme on avait remarqué, on a \[0<f_{n}(x)<\frac{1}{n!}\]pour\[0<x<1\]Conséquemment, en multipliant par \(\pi a^{n}\), un nombre positif, on a\[0<\pi a^{n}f_{n}(x)\sin\!\left(\pi x\right) < \frac{\pi a^{n}}{n!}\]et donc aussi, en inspectant les bornes de l’intégrale,\[0<\pi \int_{0}^{1}a^{n}f_{n}(x)\sin\!\left(\pi x\right)\text{d}x<\frac{\pi a^{n}}{n!}\]Mais comme ce raisonnement est indépendant de la valeur de \(n\), on n’a qu’à choisir un \(n\)  assez grand afin d’obtenir \[0<\pi \int_{0}^{1}a^{n}f_{n}(x)\sin\!\left(\pi x\right)\text{d}x<\frac{\pi a^{n}}{n!}<1\]ce qui est la contradiction recherchée ! L’intégrale est un nombre entier, mais il n’y a évidemment aucun nombre entier strictement supérieur à \(0\) et strictement inférieur à \(1\). Notre prémisse de départ s’avère donc fausse : \(\pi^{2}\) est irrationnel.

[1]  \[\left(f\cdot g\right)^{\prime}=f^{\prime}g+fg^{\prime}\][2] Si \[f(x) = x^{a}\]on a \[f^{\left(k\right)} (x)= a\left(a-1\right)\left(a-2\right) \ \dots \ \left(a-k+1\right)a^{a-k}\]et comme à chaque fois qu’on dérive le degré diminue de \(1\), si on dérive \(a\) fois une fonction polynomiale de degré \(a\), on obtient une constante et si on dérive la fonction polynomiale plus de \(a\) fois, on obtient des termes nuls.

[3] Voici la preuve originale d’Ivan Niven parue dans le Bulletin of American Mathematical Society 53 (1947), 509.

thedudeminds_2013010346

[4] George Pólya (1954) dans Induction and Analogy in Mathematics

Références supplémentaires : Michael Spivak (2008), Calculus (4th edition)

Martin Aigner et Günter M. Ziegler (2010), Proofs from THE BOOK (4th edition)

Ivan Niven (1965), Irrational Numbers