Annale – Suite et fonction ln

Raisonnement par récurrence

Raisonnement par récurrence

 

Principe

 

bf8e2989fba472800b9033b22798f33f3dbe1abd.png


Considérons une chaîne de dominos, faire tomber un domino entraîne son plus proche voisin dans sa chute et ainsi de suite. 

Le raisonnement par récurrence utilise ce principe. Il existe des conditions pour que l’ensemble des dominos tombe.

Il faut, dans un premier temps, pousser le premier domino et dans un second temps, il faut être certain que la chute de n’importe quel domino entraîne le suivant

 

Mathématiquement, $P_n$ désigne une proposition qui dépend d’un entier naturel $n$ et on souhaite démontrer que $P_n$ est vraie.

Le raisonnement par récurrence se divise en deux parties.

 

I. Initialisation

 

La première est l’initialisation : il faut vérifier que $P_0$ ou $P_1$ est vraie c’est-à-dire que la propriété est vraie pour $n=0$ ou $n=1$ (et par analogie, il faut pousser le premier domino).

 

II. Hérédité

 

La deuxième est l’hérédité : on suppose que $P_n$ est vraie pour un certain $n$ et on démontre que $P_{n + 1}$ est vraie (par analogie, on considère que le $n^text{ème}$ domino tombe et on cherche à savoir si le domino suivant, le $(n + 1)^text{ème}$, tombe également). 

 

En ayant prouvé ces deux parties, cela prouve l’ensemble de la propriété pour tout entier $n$ (tous les dominos tombent). 

La boucle Tant que

La boucle Tant que

 

Lors de certains algorithmes, il est possible d’utiliser des boucles dont on ignore le nombre de répétitions : ce sont les boucles Tant que.

 

Exemple :

on dispose d’une population d’individus de 3000 habitants qui augmente chaque année de 2%.

On se demande au bout de combien d’années la population aura dépassé 4000 habitants mais on ignore le nombre d’années : on utilise donc une boucle Tant que.

On écrit donc un algorithme qui permettra de trouver le nombre d’années $N$ pour que la population $P$ dépasse 4000. 

 

  • Variables :  $N, P$
  • Entrée :     $3000 \to P$

                 $0 \to N$

  • Traitement : (on traduit la question avec un boucle)

                 Tant que $P < 4000$ (on souhaite connaitre l’année où la population dépasse 4000 habitants donc tant qu’elle est inférieure à 4000 on continue les calculs et on arrête la première fois qu’elle dépasse 4000). 

                       $ P + 0,02P \to P$

                        $N + 1 \to N$

                  Fin Tant que

  • Sortie :       Afficher $N$

 

Sans les commentaires, l’algorithme est : 

 

Variables :    $N, P$

Entrée :        $3000 \to P$

                    $0 \to N$

Traitement : Tant que $P < 4000$  

                         $P + 0,02P \to P$

                         $N + 1 \to N$

                    Fin Tant que

Sortie :         Afficher $N$

 

 

On peut regarder les différentes valeurs que prennent $N$ et $P$ au début et à la fin de l’algorithme.

Ainsi, au bout d’un an, la population atteint 3060 habitants, $P = 3060$ et $N=1$.

Or $P < 4000$, on continue donc les calculs.

Au bout de 14 années, la population vaut environ $P \approx 3958$.

Mais un an plus tard, au bout de 15 ans, la population vaut $P \approx 4037 > 4000$.

On \ne rentre donc plus dans la boucle Tant que et on affiche la valeur de $N$ c’est à dire 15.

Ainsi, il aura fallu 15 ans pour que la population dépasse 4000 habitants.

 

Le tableau d’avancement du programme est le suivant : 

$P$ $N$
3000 0
3060 1
$vdots$ $vdots$
$approx 3958$ 14
$approx 4037$ 15