Raisonnement par récurrence

Le raisonnement par récurrence est l’un des raisonnements les plus utiles en Terminale de spécialité Mathématiques en France.

Le raisonnement par récurrence en image

Ce raisonnement peut-être visualisé par des dominos qui tombent tous quand:

• le premier tombe,
• la chute d’un domino quelconque entraîne inévitablement la chute du suivant.

C’est exactement comme cela que se passe la démonstration. Il faut nécessairement deux conditions : une condition initiale, et une implication.

Le raisonnement par récurrence formellement

Je ne vais ici parler que de la récurrence simple (autrement appelée récurrence faible, et qui est donc abordée en Terminale Mathématiques de spécialité). Il existe en effet une récurrence forte (voir cette page), mais c’est une autre histoire, bien que variant très peu de la récurrence faible.

Considérons une propriété P(n) dépendant d’un entier n ≥ 0. Le principe de récurrence faible stipule que si:

• [initialisation] P(0) est vraie;
• [hérédité] pour tout entier k > 0, si P(k) est vraie alors P(k+1) est vraie.

Bien entendu, si P(0) n’existe pas, on prend P(1) et non P(0).

Le raisonnement par récurrence par les exemples

C’est bien connu, rien ne vaut des exemples pour comprendre la théorie…

Le raisonnement par récurrence : propriété d’égalité

Nous allons considérer la propriété suivante:

P(n) : \(1^2+2^2+3^2+\cdots+(n-1)^2 + n^2 = \frac{n(n+1)(2n+1)}{6}\).

Somme des n carrés des premiers entiers naturels.

Nous allons la démontrer par récurrence.

Initialisation

La première étape est de constater que cette propriété est vraie pour le premier entier n possible. Ici, c’est n = 1.

Quand il s’agit de démontrer une égalité, il faut calculer les deux membres séparément et constater qu’ils sont égaux. Pour n = 1:

• le membre de gauche est: 1² = 1;
• le membre de droite est: \(\frac{n(n+1)(2n+1)}{6}=\frac{1(1+1)(2\times1+1)}{6}=\frac{1\times2\times3}{6}=1\).

On constate alors que les deux membres sont égaux. Par conséquent, l’égalité est vraie pour n = 1. P(1) est donc vraie.

On dit alors que l’initialisation est réalisée.

Hérédité

Une fois l’initialisation réalisée, on va démontrer que, pour k>1, si P(k) est vraie, alors P(k+1) est aussi vraie.

On suppose donc que, pour un entier k > 1, P(k) est vraie: c’est l’hypothèse de récurrence. On suppose donc que l’égalité suivante est vraie:$$1^2+2^2+3^2+\cdots+(k-1)^2 + k^2 = \frac{k(k+1)(2k+1)}{6}.$$

En s’appuyant sur cette hypothèse, on souhaite démontrer que P(k+1) est vraie, c’est-à-dire que:$$1^2+2^2+3^2+\cdots+k^2 + (k+1)^2 = \frac{(k+1)(k+1+1)(2(k+1)+1)}{6}$$c’est-à-dire, après simplification du membre de droite:$$1^2+2^2+3^2+\cdots+k^2 + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}.$$

Si on développe (k+2)(2k+3) dans le membre de droite, on obtient:$$1^2+2^2+3^2+\cdots+k^2 + (k+1)^2 = \frac{(k+1)(2k^2+7k+6)}{6}.$$

On va donc partir du membre de gauche et tenter d’arriver à l’expression de droite. D’après l’hypothèse de récurrence (HR), on a :$$\underbrace{1^2+2^2+3^2+\cdots+k^2}_{(HR)} + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$$et si on factorise par (k + 1) le membre de droite, on obtient : $$\begin{align}1^2+2^2+3^2+\cdots+k^2 + (k+1)^2 & = (k+1)\left[ \frac{k(2k+1)}{6} + (k+1)\right]\\ & = (k+1)\left[ \frac{k(2k+1)}{6} + \frac{6(k+1)}{6}\right]\\&=(k+1)\left[ \frac{k(2k+1)+6(k+1)}{6}\right]\\&=(k+1)\left[ \frac{2k^2+7k+6}{6} \right]. \end{align}$$

Nous avons bien obtenu l’expression désirée. Ainsi, l’hérédité est vérifiée.

Par conséquent, d’après le principe de récurrence, P(n) est vraie pour tout entier naturel n strictement positif.

Propriété d’inégalité

Les inégalités sont légèrement plus compliquées à démontrer par récurrence car, vous allez le voir, on n’obtient pas toujours immédiatement ce que l’on veut dans l’hérédité.

Considérons l’inégalité suivante:

Pour x > 0, pour tout entier naturel n > 1: \((1+x)^n > 1+nx.\)

Inégalité de Bernoulli.

Démontrons par récurrence sur n cette inégalité (cela signifie que le “x” sera considéré comme une constante et que seul “n” sera variable).

Initialisation

Le premier possible est n = 2. On regarde donc les deux membres de l’inégalité séparément pour n = 2:

• le membre de gauche est : \((1+x)^2 = 1+2x+x^2\)
• le membre de droite est : \(1+2x\)

x étant strictement positif, on a bien : 1+2x+x² > 1+2x. L’initialisation est alors réalisée.

Hérédité

Supposons que pour un entier k > 2, la propriété soit vraie, c’est-à-dire que:$$(1+x)^k > 1+kx.\quad(HR)$$Démontrons alors qu’elle est vraie pour k + 1.

Pour cela, regardons le membre de gauche au rang k + 1 : $$(1+x)^{k+1} = (1+x)^k \times (1+x).$$Si je l’écris ainsi, c’est pour faire apparaître le membre de gauche de la propriété au rang k. Comme ça, je peux me servir de l’hypothèse de récurrence (HR). En effet,$$\begin{align}(1+x)^k > 1+kx & \Rightarrow (1+x)^k\times(1+x) > (1+kx)(1+x)\\& \Rightarrow (1+x)^{k+1}>1+(k+1)x+kx^2\\&\Rightarrow (1+x)^{k+1} > 1+(k+1)x.\end{align}$$

La dernière inégalité est possible car 1 +(k+1)x + kx² > 1 + (k+1)x; en effet, k>0 et x²>0.

Nous avons alors démontré l’hérédité. La propriété est donc vraie pour tout n>1.

Le raisonnement par récurrence : étude de suites

On retrouve très souvent le raisonnement par récurrence dans les études des suites de la forme \(u_{n+1} = f(u_n)\).

Prenons l’exemple de \(f(x)=\frac{5-4x}{1-x}\), que l’on va définir sur [2;4]. On définit alors la suite \((u_n)\) par son premier terme \(u_0=2\) et par la relation \(u_{n+1}=f(u_n)\), c’est-à-dire:$$u_{n+1}=\frac{5-4u_n}{1-u_n}.$$Pour obtenir l’expression de \(u_{n+1}\), on a juste remplacé x par \(u_n\) dans f(x).

La dérivée de f est :$$f'(x)=\frac{1}{(1-x)^2}>0$$ donc f est strictement croissante sur [2;4].

Démontrons par récurrence que pour tout entier naturel n, \(2 \leqslant u_n \leqslant 4\).

• L’initialisation est réalisée car \(u_0=2\), donc bien compris entre 2 et 4.
• Supposons que pour un k > 0, \(2 \leqslant u_k \leqslant 4\). Alors, comme f est croissante, les images de chaque membre de ce dernier encadrement par la fonction f seront rangées dans le même ordre:$$f(2) \leqslant f(u_n) \leqslant f(4)$$c’est-à-dire:$$3 \leqslant u_{n+1}\leqslant \frac{11}{3}$$et comme \(\frac{11}{3}<4\) et 2 < 3, on a bien:$$2 \leqslant u_{n+1} \leqslant 4.$$L’hérédité est alors vérifiée.

Ainsi, d’après le principe de récurrence, la propriété est vraie pour tout entier naturel n.

L’importance de l’initialisation

Il arrive que des propriétés soient héréditaires sans pour autant qu’elles soient vraies. C’est notamment le cas de la propriété suivante:

Pour tout entier naturel n, \(10^n+1\) est divisible par 9.

Propriété fausse.

En effet, supposons que pour un entier naturel k quelconque, P(k) soit vraie, c’est-à-dire que \(10^k+1\) est divisible par 9. Alors, si p désigne un entier, on a:$$\begin{align}10^k+1=9p & \Rightarrow 10(10^k+1)=90p\\&\Rightarrow 10^{k+1}+10=90p\\&\Rightarrow 10^{k+1}+10-9=90p-9\\&\Rightarrow 10^{k+1}+1=9(10p-1)\end{align}$$

On peut ainsi conclure que \(10^{k+1}+1\) est divisible par 9. On a alors démontré que P(k) ⇒ P(k + 1). La propriété est donc héréditaire.

Or, pour n = 0, \(10^n+1=10^0+1=1+1=2\), qui n’est pas divisible par 9. Pour n=1, \(10^n+1=10+1=11\) n’est pas non plus divisible par 9…

Nous avons donc ici la preuve que ce n’est pas parce qu’une propriété est héréditaire qu’elle est vraie. Il faut nécessairement qu’elle soit vraie pour le premier n possible.

L’initialisation est donc très importante dans un raisonnement par récurrence.

Pour en savoir plus sur le raisonnement par récurrence, vous pouvez jeter un coup d’œil sur la page wikipedia.

Retrouvez plus d’exercices corrigés sur la récurrence sur cette page.

Retrouvez un QCM sur le raisonnement par récurrence sur la page des Quiz de Terminale.