Exercice 1
Exercice 2

Introduction

Allons-y, mes amis, nous allons voir comment démontrer une petite formule simple en utilisant l'outil puissant qu'est la récurrence. Ce qui est déroutant dans ces exercices, c'est que vous avez l'habitude d'utiliser la récurrence sur des suites pour démontrer des propriétés liées à ces suites. Cependant, nous pouvons aussi utiliser la récurrence pour démontrer des propriétés qui ne sont pas liées à une suite. Comment fait-on cela ? De la même manière que nous l'avons fait avec les suites. Nous allons d'abord analyser l'énoncé. Une fois que nous avons fini d'analyser l'énoncé, nous appliquons la récurrence. Pour analyser l'énoncé, nous nous posons trois questions : Qu'est-ce que je vais démontrer ? Pour quelle valeur vais-je le démontrer ? Et comment vais-je m'y prendre ?

Analyse de l'énoncé

Alors, qu'est-ce que je vais démontrer ici ? C'est assez simple. Je vais démontrer que \(n! > 2^n\). Pour quelles valeurs de \(n\) ? C'est très clairement pour tout \(n\) plus grand que quatre. Comment vais-je m'y prendre ? L'énoncé n'est pas très explicite. Il ne donne pas de formule de récurrence qui vous donne le terme \(P_{R}\) en fonction du terme précédent. Donc, nous devrons nous débrouiller sans cela, notamment en utilisant les propriétés de la factorielle.

Rédaction de la démonstration

Nous commençons la rédaction. Donc \(P_n\) est la propriété que nous voulons démontrer. Ici, votre \(P_n\) sera simplement de dire que \(n! > 2^n\). Aucun problème là-dessus. L'initialisation se fera de manière très simple aussi. Je vous rappelle que l'initialisation consiste à vérifier que ce que vous voulez démontrer, c'est-à-dire \(P_n\), est vrai pour la plus petite valeur de \(n\), en l'occurrence ici pour \(n = 4\). Donc, nous allons montrer que \(P_4\) est vrai. Et nous allons expliquer pourquoi. Tout simplement parce que lorsque je prends \(4!\), cela donne \(4 \times 3 \times 2 \times 1 = 24\). Et lorsque je prends \(2^4\), cela donne \(2 \times 2 \times 2 \times 2 = 16\). J'ai donc bien \(4! > 2^4\). Ma propriété est donc initialisée. Nous continuons avec l'hérédité. Pour l'hérédité, nous avons la petite phrase habituelle : "Supposons qu'il existe un entier \(n\) tel que \(P_n\) soit vrai. Montrons que \(P_{n+1}\) est aussi vrai." La force de cette formule, c'est qu'elle vous donne déjà le point de départ. Votre point de départ, c'est \(P_n\), c'est-à-dire que \(n! > 2^n\). Vous pouvez considérer que c'est vrai. Montrons maintenant que \(P_{n+1}\) est aussi vrai. Donc, vous savez que vous arrivez à \(P_{n+1}\), qui est de dire la même chose, mais en remplaçant \(n\) par \(n+1\), c'est-à-dire que \((n+1)! > 2^{n+1}\). Et vous savez qu'il ne vous reste plus qu'à passer de l'un à l'autre. Comment allons-nous nous y prendre ? Nous avons une petite astuce qui aurait pu vous sauver la vie, qui aurait pu rendre toute ma scolarité beaucoup plus efficace. Mais je l'ai oubliée, donc peut-être que ça reviendra, peut-être que non, c'est le jeu de la vie. Comment allons-nous passer de \(n!\) à \((n+1)!\) ? Eh bien, nous allons d'abord nous demander ce qu'est \(n!\). Donc, je vais prendre cette ligne. Je veux juste remplacer \(n!\) par \(1 \times 2 \times 3 \times \ldots \times n > 2^n\). Et je vais faire la même chose ici, \(1 \times 2 \times 3 \times \ldots \times n \times (n+1) > 2^{n+1}\). Et là, il sera peut-être plus clair de voir comment je passe de là à là. Vous voyez que là, j'ai \(1 \times 2 \times 3 \times \ldots \times n\). Là, j'ai \(1 \times 2 \times 3 \times \ldots \times n\), puis j'ai \((n+1)\). Donc, qu'est-ce qui s'est passé entre là et là ? J'ai juste multiplié par \((n+1)\), donc je vais prendre cette ligne là et je vais la multiplier des deux côtés par \((n+1)\). Et juste en faisant ça, j'ai directement \(1 \times 2 \times 3 \times \ldots \times n \times (n+1)\), donc j'ai directement \((n+1)!\). Donc, il ne me reste plus qu'à régler ce côté là. Une petite parenthèse avant de régler le côté droit. Vous voyez ce que j'ai fait ? C'est une technique classique. Vous savez que vous devez partir de là et vous devez arriver jusqu'à là. Sauf que si je supprime ces deux lignes, aucun moyen de le savoir. Donc, ce que je fais, c'est que je réécris légèrement, j'avance un peu et là, je recule un peu pour voir. Où est-ce que j'ai été ? Comment est-ce que je peux joindre ces deux bouts ? Et vous vous rendez compte que la jonction entre ces deux bouts, c'était juste de multiplier par \((n+1)\). Un revenu en mouton plus ? Plus exactement, au fait qu'on a \(2^n\) une fois de plus, alors que nous voudrions \(2^{n+1}\), c'est-à-dire ? Nous voudrions en fait \(2^n \times 2\). Je veux \(2^n\) une fois de plus. Un. Oui, sauf que quoi de plus en vue que je bosse pour un plus grand que quatre, une puissance est plus grand que deux, c'est au moins plus grand que cinq, donc c'est plus grand que deux. Et du coup, \(2^n \times (n+1)\) est plus grand que \(2^n \times 2\). Et hop, j'ai terminé et j'ai mon égalité. Toujours regarder le côté gauche, toujours se dire je descends un peu, je monte. Gardez bien en tête. Quel est votre point de départ ? Quel est votre point d'arrivée ? C'est vraiment ça. C'est ça qui va faire que vous arrivez à faire une récurrence ou pas ? Si vous êtes bien clair sur douze pas. Et oui, j'avais une petite conclusion. \(P_n\) est héréditaire, \(P_n\) est initialisé donc \(P_n\) est vrai pour tout \(n\) appartenant à \(\mathbb{N}\). Nous vous avons mis des petits exercices en dessous. Entraînez-vous autant que vous le souhaitez, vous êtes les champions !