1.8 Récurrence: Le principe d’induction

Le dernier principe que nous allons étudier dans ce chapitre est le principe d’induction, ainsi que l’une de ses versions généralisés (il en existe en fait plusieurs autres…). Ce dernier est en fait un peu différent des précédents, car contrairement aux autres principes, il ne permet pas de répondre directement à une question de combinatoire. Il s’agit en fait d’un principe permettant de version un hypothèse. L’idée est que pour plusieurs problèmes il nous est possible de deviner la solution. Le principe d’induction nous permet alors de démontrer que notre solution est bel et bien correcte.

Théorème 1.8.1:

Principe d’induction. Si P\displaystyle P est une propriété satisfaisant les deux conditions suivantes:

  1. 1.
    ​

    La propriété P\displaystyle P est vraie pour un entier a\displaystyle a.

  2. 2.
    ​

    En faisant l’hypothèse que la propriété P\displaystyle P est vraie pour un entier k\displaystyle k (avec k≥a\displaystyle k\geq a), on peut démontrer qu’elle est aussi vraie pour l’entier k+1\displaystyle k+1.

Alors on peut conclure que la propriété P\displaystyle P est vraie pour tous les entiers plus grand ou égal à a\displaystyle a.

Notez que nous ne fourniront pas de démonstration du principe d’induction. Le difficulté vient du fait que dépendant du contexte, il peut s’agir soit d’un axiome, ou d’un théorème. Les nombres naturels sont fréquemment définie à partir des axiomes de Peano. Dans ce contexte, le principe d’induction est le 5e axiome. Dans les cours de calcul et d’analyse, le point de départ choisi est habituellement les nombres réels. Dans ce contexte, on accepte habituellement l’axiome de complétude (Tout ensemble non vide de nombre réel borné supérieurement admet une plus petite borne supérieure). Dans ce contexte, le principe d’induction devient une conséquence de l’axiome de complétude. Étant donné le contexte discret de la combinatoire, le supposer comme un axiome semble donc plus raisonnable.

À partir du théorème, on remarque donc qu’une démonstration par induction doit se faire en 3 étapes:

  1. 1.
    ​

    On commence par choisir l’entier de départ a\displaystyle a. Il s’agit du premier entier pour lequel on veut montrer que la propriété est vraie. On doit alors démontrer que la propriété est vraie pour l’entier a\displaystyle a.

  2. 2.
    ​

    On fait l’hypothèse que la propriété est vraie pour un entier n∈ℤ\displaystyle n\in\mathbb{Z}

  3. 3.
    ​

    On démontre que la propriété est encore vraie pour n+1\displaystyle n+1.

Si on parvient à compléter les trois étapes, on peut alors conclure que la propriété est vraie pour tout entier plus grand ou égal à a\displaystyle a. Nous allons maintenant voir quelques exemples d’application du principe d’induction.

Exemple 1.8.1.

On veut démontrer que pour tout nombre naturel n\displaystyle n, on a:

1+2+3+4+…+n=n⁢(n+1)2\displaystyle 1+2+3+4+...+n=\frac{n(n+1)}{2}

Ou écrit de manière symbolique, on veut démontrer que:

∑i=1ni=n⁢(n+1)2\displaystyle\sum_{i=1}^{n}i=\frac{n(n+1)}{2}

Pour ce faire, nous allons appliquer le principe d’induction.

  1. 1.
    ​

    On doit démontrer que la propriété est vraie lorsque n=1\displaystyle n=1. Pour ce faire, on remarque que:

    ∑i=11i=1⁢ et ⁢1⁢(1+1)2=1\displaystyle\sum_{i=1}^{1}i=1\textrm{\leavevmode\nobreak\ \leavevmode\nobreak% \ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ et % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ }\frac{1(1+1)}{2}=1

    donc la propriété est vraie lorsque n=1\displaystyle n=1.

  2. 2.
    ​

    Supposons maintenant que la propriété est vraie lorsque n=k\displaystyle n=k, où k\displaystyle k est un entier plus grand ou égal à 1\displaystyle 1. C’est à dire, on suppose que

    ∑i=1ki=k⁢(k+1)2\displaystyle\sum_{i=1}^{k}i=\frac{k(k+1)}{2}
  3. 3.
    ​

    On veut maintenant vérifier que la propriété est vraie pour n=k+1\displaystyle n=k+1. On a donc:

    ∑i=1k+1i=(∑i=1ki)+(k+1)=k⁢(k+1)2+(k+1)=k2+k+2⁢k+22=(k+1)⁢(k+2)2\displaystyle\sum_{i=1}^{k+1}i=\Big{(}\sum_{i=1}^{k}i\Big{)}+(k+1)=\frac{k(k+1% )}{2}+(k+1)=\frac{k^{2}+k+2k+2}{2}=\frac{(k+1)(k+2)}{2}

    Donc à partir de notre hypothèse, on a bien que la propriété est vraie pour n=k+1\displaystyle n=k+1.

Par le principe d’induction, on peut donc conclure que la propriété est vraie pour tout n∈ℕ\displaystyle n\in\mathbb{N}.

Exemple 1.8.2.

Démontrer que xn=3⋅5n+1\displaystyle x_{n}=3\cdot 5^{n}+1 pour tout n≥0\displaystyle n\geq 0 est la solution explicite de la récurrence suivante:

{xn+1=5⁢xn−4,∀n≥1x0=4\displaystyle\left\{\begin{array}[]{l}x_{n+1}=5x_{n}-4,\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \forall n\geq 1\\ x_{0}=4\end{array}\right.

Pour ce faire, appliquons les 3 étapes de l’induction.

  1. 1.
    ​

    Si n=0\displaystyle n=0, la récurrence nous donne x0=4\displaystyle x_{0}=4 et la solution explicite nous donne x0=3⁢(50)+1=4\displaystyle x_{0}=3(5^{0})+1=4. L’égalité est donc satisfaite pour n=0\displaystyle n=0.

  2. 2.
    ​

    Supposons que l’égalité est satisfaite pour n=k\displaystyle n=k. C’est à dire supposons que xk=3⋅5k+1\displaystyle x_{k}=3\cdot 5^{k}+1.

  3. 3.
    ​

    Si n=k+1\displaystyle n=k+1, on a donc:

    xk+1=5⁢xk−4=5⁢(3⋅5k+1)−4=15⋅5k+5−4=3⋅5k+1+1\displaystyle x_{k+1}=5x_{k}-4=5(3\cdot 5^{k}+1)-4=15\cdot 5^{k}+5-4=3\cdot 5^% {k+1}+1

    Ce qui est exactement ce que nous voulions.

Comme les trois étapes de l’induction sont satisfaite, on peut donc conclure que xn=3⋅5n+1\displaystyle x_{n}=3\cdot 5^{n}+1 pour tout n≥0\displaystyle n\geq 0.

Dans certain cas, le principe d’induction, tel que nous l’avons énoncé, n’est pas suffisant pour démontrer un résultat. Lorsqu’on applique de manière stricte le principe d’induction, on utilise uniquement la valeur précédente pour démontrer qu’une propriété est vraie pour une certaine valeur. Nous allons maintenant énoncer une version généralisée du principe d’induction qui nous permettra d’utiliser plusieurs valeurs précédentes pour démontrer un énoncé.

Théorème 1.8.2:

Principe d’induction généralisé. Si P\displaystyle P est une propriété satisfaisant les deux conditions suivantes:

  1. 1.
    ​

    La propriété est vraie pour tous les entiers entre a\displaystyle a et b\displaystyle b (avec a≤b\displaystyle a\leq b).

  2. 2.
    ​

    En faisant l’hypothèse que la propriété est vraie pour tous les entiers entre a\displaystyle a et k\displaystyle k (avec k≥b\displaystyle k\geq b), on peut démontrer qu’elle est aussi vraie pour l’entier k+1\displaystyle k+1.

Alors on peut conclure que la propriété P\displaystyle P est vraie pour tous les entiers plus grand ou égal à a\displaystyle a.

Exemple 1.8.3.

Considérons la suite de nombres naturels définie par la relation

xn=7⁢xn−1−10⁢xn−2⁢ avec ⁢x0=1⁢ et ⁢x1=2\displaystyle x_{n}=7x_{n-1}-10x_{n-2}\textrm{ avec }x_{0}=1\textrm{ et }x_{1}=2

Utilisez l’induction pour démontrer que xn=2n\displaystyle x_{n}=2^{n} pour tout n≥0\displaystyle n\geq 0.

  1. 1.
    ​

    Pour n=0\displaystyle n=0 et n=1\displaystyle n=1, on a bien l’égalité. Remarquez que l’on doit vérifier les deux premières valeurs car nous utilisons les deux valeurs précédentes dans notre troisième étape.

  2. 2.
    ​

    Supposons que xn=2n\displaystyle x_{n}=2^{n} pour tout n≤k\displaystyle n\leq k

  3. 3.
    ​

    On veut maintenant montrer que l’équation est vrai pour n=k+1\displaystyle n=k+1:

    xk+1\displaystyle\displaystyle x_{k+1} =\displaystyle\displaystyle= 7⁢xk−10⁢xk−1\displaystyle\displaystyle 7x_{k}-10x_{k-1}
    =\displaystyle\displaystyle= 7⁢(2k)−10⁢(2k−1)\displaystyle\displaystyle 7(2^{k})-10(2^{k-1})
    =\displaystyle\displaystyle= 2k−1⁢(7⋅2−10)\displaystyle\displaystyle 2^{k-1}(7\cdot 2-10)
    =\displaystyle\displaystyle= 2k−1⁢(22)\displaystyle\displaystyle 2^{k-1}(2^{2})
    =\displaystyle\displaystyle= 2k+1\displaystyle\displaystyle 2^{k+1}

    Ce qui complète la démonstration.