Récurrences trompeuses (Lycée... )
 

Les couples d'entiers Les points tous alignés Les failles

 

Les couples d'entiers naturels

PROPRIETE (P)
Tout couple d'entiers naturels est constitué d'entiers égaux.
comme (1,1) puis (2,2) etc...

Et (2,3 ) ... que devient-il ?

 DEMONSTRATION
Le résultat est obtenu par récurrence.

La récurrence se fait sur le maximum des deux nombres a et b que nous allons noter max(a,b).

Rang 0
Si max(a,b) = 0, alors il est clair que a = b = 0

Hypothèse de récurrence
    Rang  p
Supposons la propriété (P) vraie quand le maximum de a et b est p, c'est-à-dire que
               si max(a,b)=p alors a = b = p
 Montrons alors que la propriété est vraie quand le maximum est (p+1).

Rang  p+1
Prenons donc un couple (a,b) tel que max (a,b)=p+1.
Le maximum de (a-1) et de (b-1) est donc p.
Par hypothèse de récurrence, nous avons : a -1 = b -1 = p
d'où a - 1 + 1 = b - 1 + 1 = p + 1
et finalement a = b = p + 1.

RECAPITULONS
Nous avons vérifié la propriété (P) au rang 0,
Quand la propriété est supposée vraie au rang p, nous avons montré qu'elle était vraie au rang p+1 sans autre condition.
Il semble donc que nous ayions montré par récurrence que quel que soit le couple d'entiers naturels a et b nous obtenions a = b

Trouvez l'erreur...

 

 

 

 

 

Les points tous alignés

PROPRIETE (P)
n points quelconques du plan sont toujours alignés...  

DEMONSTRATION
Le résultat est obtenu par récurrence.

La récurrence se fait simplement sur le nombre n.

Rang  2
Pour n=2 c'est vrai :
2 points sont toujours alignés.

Hypothèse de récurrence
    Rang  p>=2
Supposons la propriété (P) vraie pour p points :
               p points sont alignés...
Montrons qu'alors (p+1) points sont alignés.

Rang  p+1
Prenons (p+1) points nommés A₁    A₂      A₃     ... A_p+1.
Par hypothèse de réurrence les p premiers points A₁    A₂      A₃     ... A_p
sont alignés sur une droite que nous appellerons (d₁).
Et toujours avec cette hypothèse de récurrence
les p derniers points A₂      A₃     ... A_p+1
sont alignés sur une droite que nous nommerons (d₂).
Maintenant les deux droites (d₁) et (d₂) ont en commun les deux points A₂   et A₃ .
Ces deux droites sont forcément confondues. On a (d₁) = (d₂) = (A₂  A₃)
Les (p+1) points sont donc alignés.

RECAPITULONS
Nous avons vérifié la propriété (P) avec 2 points.
Quand la propriété est supposée vraie avec p points, nous avons montré qu'elle était vraie avec p+1 points.
Il semble donc que nous ayions montré par récurrence que quel que soit le nombre de points n alors les n points sont alignés.

Trouvez la faille...

   

 

 Les failles  

COUPLE D'ENTIERS La ligne : Si max(a,b) = 0, alors il est clair que a = b = 0 impose comme dit au départ que les nombres sur lesquels on travaille soient bien des entiers positifs. La faille provient donc de la ligne suivante qui ne respecte pas l'hypothèse de récurrence avec p>=0. Le maximum de (a-1) et de (b-1) est donc p.

En effet cette ligne peut produire des nombres négatifs (si a ou b est nul) et nous ne sommes plus dans le cadre de la propriété (P) qui porte sur les entiers naturels.

Prenons les nombres a = 0 et b = 1 .
Alors a -1 = -1 et b - 1 = 0
et le max de -1 et 0 est nul.

Cela n'implique pas que les deux nombres soient nuls car ils ne sont pas positifs ou nuls.

 

POINTS ALIGNES
L'erreur est dans la ligne suivante
Maintenant les deux droites (d₁) et (d₂) ont en commun les deux points A₂   et A₃  

Pour être vraie, elle impose p>= 3 pour pouvoir parler de A2    A3 et du point suivant qui serait A4   . Or l'hypothèse de récurrence doit démarrer avec p>=2. Pour p = 2, la droite (d1) est (A1  A2) et (d2) est (A2  A3). (d1) et (d2) n'ont en commun que le point A2.

                           OUF !