Partie 1 : Raisonnement par récurrence

1/ Le principe

{width="0.7222222222222222in" height="0.9326388888888889in"}

C'est au mathématicien italien Giuseppe Peano (1858 ; 1932), ci-contre, que l'on attribue le principe du raisonnement par récurrence. Le nom a probablement été donné par Henri Poincaré (1854 ; 1912).

{width="1.5833333333333333in" height="1.1854166666666666in"}

On considère une file illimitée de dominos placés côte à côte. La règle veut que lorsqu'un domino tombe, alors il fait tomber le domino suivant et ceci à n'importe quel niveau de la file.

Alors, si le premier domino tombe, on est assuré que tous les dominos de la file tombent.

{width="6.288888888888889in" height="2.433333333333333in"}

Si on suppose qu'un domino $n{^\circ}\ (k)$ tombe alors le domino suivant $n{^\circ}\ (k + 1)$ tombe également. C'est ce qu'on appelle le principe d'hérédité.

I.1/ Définition :

On dit qu'une propriété est héréditaire à partir d'un certain rang :

Si la propriété est vraie pour un entier $k$, alors elle est vraie pour l'entier $k + 1$.

I.2/ Principe du raisonnement par récurrence :

Si la propriété $P$ est :

• vraie au rang $n_{0}$ (Initialisation),

• héréditaire à partir du rang $n_{0}$ (Hérédité),

• alors la propriété $P$ est vraie pour tout entier ${n \geq n}_{0}$.

Dans l'exemple, le premier domino tombe (initialisation). Ici $n_{0} = 1$.

L'hérédité est vérifiée (voir plus haut). On en déduit que tous les dominos tombent.

Remarque : On tente d'utiliser une démonstration par récurrence, lorsqu'une démonstration classique n'est pas possible ou est trop difficile..

Exemples : Démontrer une propriété par récurrence

Vidéo https://youtu.be/udGGlHdSAgc

Démontrer par récurrence que pour tout entier naturel $n$ non nul, on a : $\boxed{ 2^{n} > n }$.

Correction

• Initialisation pour n=1 :
  $2^{1} = 2 > 1$. La propriété est donc vraie pour $n = 1$.

• Hérédité :

  • Hypothèse de récurrence : Supposons que la propriété soit vraie pour un certain entier $k$ non nul : $2^{k} > k$.

  • Démontrons que : La propriété est vraie au rang $k + 1$, soit :$\ 2^{k + 1} > k + 1$ ???
    $ 2^{k} > k$, par hypothèse de récurrence
    $2 \times 2^{k} > 2 \times k$
    $2^{k + 1} > 2k$
    $2^{k + 1} > k + k$
    $2^{k + 1} > k + k \geq k + 1$, car $k \geq 1$
    ${2}^{k + 1} > k + 1$ .

• Conclusion :
  La propriété est vraie pour $n = 1$ et héréditaire à partir de ce rang. D'après le principe de récurrence, elle est vraie pour tout entier naturel $n$ non nul, soit : $2^{n} > n$.

Exemples avec les suites

[Méthode :]{.underline} Démontrer par récurrence l'expression générale d'une suite

{width="0.17777777777777778in" height="0.17777777777777778in"} Vidéo https://youtu.be/OIUi3MG8efY

On considère la suite $(u_{n})\ $définie pour tout entier naturel $n$ par $u_{n + 1} = u_{n} + 2n + 3$ et $u_{0} = 1$.

Démontrer par récurrence que : $\boxed{ u_{n} = (n + 1)^{2} }$.

Correction

• [Initialisation pour]{.underline} $\mathbf{n}$ [= 0 :]{.underline} Le premier domino tombe.

${(0 + 1)^{2} = 1 = u}_{0}$.

La propriété est donc vraie pour $n = 0$.

• [Hérédité :]{.underline}

- [Hypothèse de récurrence :]{.underline} On suppose que le domino n° (k) tombe.

Supposons que la propriété soit vraie pour un certain entier $k$ : $u_{k} = (k + 1)^{2}$.

- [Démontrons que :]{.underline} Prouvons que le domino n° (k+1) tombe.

La propriété est vraie au rang $k + 1$, soit : $u_{k + 1} = (k + 1 + 1)^{2}$, soit encore :

$u_{k + 1} = (k + 2)^{2}$ ???

$u_{k + 1} = u_{k} + 2k + 3$, par définition

$= (k + 1)^{2} + 2k + 3$, par hypothèse de récurrence

$= k^{2} + 2k + 1 + 2k + 3$

$= k^{2} + 4k + 4$

$= (k + 2)^{2}$ Le domino n° (k+1) tombe.

• [Conclusion :]{.underline} Tous les dominos tombent.

La propriété est vraie pour $n = 0$ et héréditaire à partir de ce rang. D'après le principe de récurrence, elle est vraie pour tout entier naturel $n$, soit : $u_{n} = (n + 1)^{2}$.

[Méthode :]{.underline} Démontrer la monotonie par récurrence

{width="0.17777777777777778in" height="0.17777777777777778in"} Vidéo https://youtu.be/nMnLaE2RAGk

On considère la suite $(u_{n})\ $définie pour tout entier naturel $n$ par $u_{n + 1} =$ $\frac{1}{3}$ $u_{n} + 2$ et $u_{0} = 2$.

Démontrer par récurrence que la suite $(u_{n})\ $est croissante.

Correction

On va démontrer que pour tout entier naturel $n$, on a : $u_{n + 1} \geq u_{n}$

• [Initialisation :]{.underline} $u_{0} = 2$ et $u_{1} =$ $\frac{1}{3}$ $u_{0} + 2 =$ $\frac{1}{3}$ $\times 2 + 2 =$ $\frac{8}{3}$ $> 2$

donc $u_{1} \geq u_{0}$.

La propriété est donc vraie pour $n = 0$.

• [Hérédité :]{.underline}

- [Hypothèse de récurrence :]{.underline}

Supposons que la propriété soit vraie pour un certain entier $k$ : $u_{k + 1} \geq u_{k}$.

- [Démontrons que :]{.underline} La propriété est vraie au rang $k + 1$, soit : $u_{k + 2} \geq u_{k + 1}$.

On a $u_{k + 1} \geq u_{k}$ donc :

$\frac{1}{3}u_{k + 1} \geq \frac{1}{3}u_{k}$

$\frac{1}{3}u_{k + 1} + 2 \geq \frac{1}{3}u_{k} + 2$

$u_{k + 2} \geq u_{k + 1}$.

• [Conclusion :]{.underline}

La propriété est vraie pour $n = 0$ et héréditaire à partir de ce rang. D'après le principe de récurrence, elle est vraie pour tout entier naturel $n$, soit : $u_{n + 1} \geq u_{n}$ et donc la suite $(u_{n})$ est croissante.

3) [Inégalité de Bernoulli]{.underline}

[Propriété :]{.underline} Soit un nombre réel $a$ positif.

Pour tout entier naturel $n$, on a : $(1 + a)^{n} \geq 1 + na$.

[Démonstration au programme :]{.underline}

{width="0.17777777777777778in" height="0.17777777777777778in"} Vidéo https://youtu.be/H6XJ2tB1_fg

• [Initialisation :]{.underline}

$(1 + a)^{0} = 1$ et $1 + 0 \times a = 1$.

La propriété est vraie pour $n = 0$.

• [Hérédité :]{.underline}

- [Hypothèse de récurrence :]{.underline}

Supposons que la propriété soit vraie pour un certain entier $k$ : $(1 + a)^{k} \geq 1 + ka$

- [Démontrons que :]{.underline} La propriété est vraie au rang $k + 1$, soit :

$(1 + a)^{k + 1} \geq 1 + (k + 1)a$

On a : $(1 + a)^{k} \geq 1 + ka$, d'après l'hypothèse de récurrence.

Donc : ${(1 + a)(1 + a)}^{k} \geq (1 + a)(1 + ka)$, car $1 + a > 0.$

$(1 + a)^{k + 1} \geq 1 + ka + a + ka^{2}$

$(1 + a)^{k + 1} \geq 1 + (k + 1)a + ka^{2} \geq 1 + (k + 1)a$, car $ka^{2} \geq 0$.

Donc : $(1 + a)^{k + 1} \geq 1 + (k + 1)a$.

• [Conclusion :]{.underline}

La propriété est vraie pour $n = 0\ $et héréditaire à partir de ce rang. D'après le principe de récurrence, elle est vraie pour tout entier naturel $n$ soit : $(1 + a)^{n} \geq 1 + na$.

4) [Le rôle de l'initialisation dans une démonstration par récurrence]{.underline}

L'initialisation (le 1^er^ domino tombe) est indispensable dans une démonstration par récurrence, sinon on peut démontrer des propriétés fausses !

En effet, démontrons par exemple que la propriété « $2^{n}$ est divisible par $3$ » est héréditaire sans vérifier l'initialisation.

Supposons que pour un certain entier $k$ : « $2^{k}$ est divisible par $3$ ». Donc il existe un entier $p$ tel que : $2^{k} = 3p.$

$$2^{k + 1}\ = \ 2^{k} \times 2\ $$

$\ \ \ \ \ \ \ \ \ \ \ = \ 3p \times 2$ (d'après l'hypothèse de récurrence).

$= \ 6p$

$\ \ \ \ \ \ \ \ \ \ = 3 \times 2p$, avec $2p$ entier

Donc $2^{k + 1}$ est divisible par $3$. L'hérédité est vérifiée et pourtant la propriété n'est jamais vraie.