Table des matières

Raisonnement par récurrence

Principe de récurrence

Le raisonnement par récurrence est une méthode importante en mathématiques. Pour mieux le comprendre, considérons un exemple :

Exemple : On considère la proposition \(P(n)\) dépendant d'un entier \(n\) : “ \(2^n \geq n+1\) ”.

Vérifions cette propriété pour \(n=0, 1, 2, 3, 4\) :

Pour \(n=0\) : \(2^0=1 \geq 0+1=1\)
Pour \(n=1\) : \(2^1=2 \geq 1+1=2\)
Pour \(n=2\) : \(2^2=4 \geq 2+1=3\)
Pour \(n=3\) : \(2^3=8 \geq 3+1=4\)
Pour \(n=4\) : \(2^4=16 \geq 4+1=5\)

On peut continuer à vérifier cette propriété pour d'autres entiers, mais cela ne prouvera jamais qu'elle est vraie pour tout \(n\). Pour démontrer cette proposition, on utilise le raisonnement par récurrence.

Axiome : Soit \(P(n)\) une proposition dépendant d'un entier, et \(n_0\) un entier fixé.

  • Initialisation : Si \(P(n_0)\) est vraie,
  • Hérédité : Si pour tout entier \(n \geq n_0\), \(P(n) \implies P(n+1)\),

alors \(P(n)\) est vraie pour tout entier \(n \geq n_0\).

Preuve : C'est un axiome des mathématiques : une propriété fondamentale qui ne se démontre pas, mais qui semble “logique”. En imaginant une longue rangée de dominos alignés. Si on pousse le premier domino, et que chaque domino qui tombe pousse le suivant, alors tous les dominos tomberont les uns après les autres. De la même manière, le raisonnement par récurrence fonctionne en prouvant que :

1. Le premier domino tombe (c'est l'étape d'initialisation).

2. Chaque domino qui tombe entraîne la chute du suivant (c'est l'étape d'hérédité).

Ainsi, si ces deux conditions sont remplies, on peut être certain que tous les dominos tomberont, c'est-à-dire que la propriété est vraie pour tous les entiers \(n\).

Remarque : Si, pour tout entier \(n \geq n_0\), \(P(n) \implies P(n+1)\), on dit que la propriété \(P\) est héréditaire.

Exemple de démonstration : Démontrons maintenant la propriété \(P(n)\) : “ \(2^n \geq n+1\) ” pour \(n \geq 0\) par récurrence :

  • Initialisation : Pour \(n=0\), on a bien \(2^0 = 1 \geq 0+1=1\).
  • Hérédité : Supposons que la propriété \(P(n)\) soit vraie pour un certain \(n\) fixé. On a donc \(2^n \geq n+1\) (c'est l'hypothèse de récurrence).

On veut démontrer \(P(n+1)\), c'est-à-dire \(2^{n+1} \geq n+2\).

\(2^n \geq n+1 \iff 2 \times 2^n \geq 2(n+1)\) car \(2\) est un nombre positif

\(\iff 2^{n+1} \geq 2n+2 \iff 2^{n+1} - (n+2) \geq 2n+2 - (n+2)\)

\(\iff 2^{n+1} - (n+2) \geq n \geq 0\) car \(n\) est un entier positif ou nul

On a donc bien \(2^{n+1} \geq n+2\) : la proposition \(P(n+1)\) est vérifiée.

On a ainsi démontré l'initialisation et l'hérédité : par récurrence, la propriété \(P(n)\) est vraie pour tout entier \(n\) : \[ \forall~n,~2^n \geq n+1 \]

Exercice

Démontrez par récurrence les propriétés suivantes :

  1. \(\forall~n \geq 1, ~1+\cdots+n=\sum\limits_{k=1}^n k =\frac{n(n+1)}{2}\)
  2. \(\forall~n \geq 1, ~1^2+\cdots+n^2=\sum\limits_{k=1}^n k^2 =\frac{n(n+1)(2n+1)}{6}\)

Solution :

Solution :

1. Soit \(P_n\) la proposition définie pour tout \(n \geq 1\) par \(P_n\) : “ \(1+\cdots + n = \frac{n(n+1)}{2}\) ”.

  • Initialisation : Pour \(n=1\), on a d'une part \(1\), et d'autre part \(\frac{1(1+1)}{2}=1\). Donc \(P_1\) est vraie.
  • Hérédité : Supposons que la proposition \(P_n\) soit vraie pour un certain \(n \geq 1\), et montrons que \(P_{n+1}\) est vraie. Par hypothèse de récurrence, on a donc

\[ 1+2+\cdots + n = \frac{n(n+1)}{2} \] Or, \(1+2+\cdots + (n+1) = (1+2+\cdots n ) + (n+1)\). D'après l'hypothèse de récurrence, on a donc \begin{align} 1+\cdots + n + (n+1) &= \frac{n(n+1)}{2} + (n+1) \\ &= (n+1)\left(\frac{n}{2}+1\right) \\ &= (n+1)\frac{n+2}{2}=\frac{(n+1)(n+2)}{2} \end{align} Ainsi, la proposition \(P_{n+1}\) est vraie, et la propriété \(P\) est donc héréditaire.

D'après le principe de récurrence, la proposition \(P_n\) est donc vraie pour tout entier \(n \geq 1\) : \[ \forall~n \geq 1,~~1+\cdots + n = \frac{n(n+1)}{2} \]

2. Soit \(Q_n\) la proposition définie pour tout \(n \geq 1\) par \(Q_n\) : “ \(1^2+\cdots + n^2 = \frac{n(n+1)(2n+1)}{6}\) ”.

  • Initialisation : Pour \(n=1\), on a d'une part \(1^2=1\), et d'autre part \(\frac{1(1+1)(2\times 1+1)}{6}=\frac{6}{6}=1\). Donc \(Q_1\) est vraie.
  • Hérédité : Supposons que la proposition \(Q_n\) soit vraie pour un certain \(n \geq 1\), et montrons que \(Q_{n+1}\) est vraie. Par hypothèse de récurrence, on a donc

\[ 1^2+2^2+\cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \] Comme précédemment, on a alors \begin{align} 1^2+\cdots + n^2 + (n+1)^2 &= \frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\ &= (n+1) \left( \frac{n(2n+1)}{6} + (n+1)\right) \end{align} soit \begin{align} 1^2+\cdots + n^2 +(n+1)^2 &= (n+1) \frac{2n^2+n+6n+6}{6}\\ &= (n+1) \frac{2n^2+7n+6}{6} \end{align} Or, \(2n^2+7n+6=(n+2)(2n+3)\). Donc, \begin{align} 1^2+\cdots + n^2 + (n+1)^2 &= (n+1) \frac{(n+2)(2n+3)}{6}\\ &=\frac{(n+1)(n+1+1)(2(n+1)+1)}{6} \end{align} Ainsi, la proposition \(Q_{n+1}\) est vraie, et la propriété \(Q\) est donc héréditaire.

D'après le principe de récurrence, la proposition \(Q_n\) est donc vraie pour tout entier \(n \geq 1\) : \[ \forall~n \geq 1,~~1^2+\cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \]