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

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

                    Ils  m'ont rendue chèvre ! ! !

 

 

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 ? Nous étions si différents !

 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 En ligne S.V.P !

PROPRIETE (P)
n points quelconques du plan sont toujours alignés... Nous sommes aspirés dans ce tube !  

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 A1
    A2      A3     ... Ap+1.
Par hypothèse de réurrence les p premiers points A1    A2      A3     ... Ap
sont alignés sur une droite que nous appellerons (d1).
Et toujours avec cette hypothèse de récurrence
les p derniers points A2
     A3     ... Ap+1
sont alignés sur une droite que nous nommerons (d2).
Maintenant les deux droites (d1) et (d2) ont en commun les deux points A2   et A3 .
C
es deux droites sont forcément confondues. On a (d1) = (d2) = (A2
  A3)
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 Et la lumière fut...  

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.

Ah ! Nous sommes bien différents !

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 (d1) et (d2) ont en commun les deux points A2   et A3  

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.

              Vive la liberté !

                        Je me sens mieux ainsi ! ! !   OUF !

 

  
     

        Menu Paradoxes  Accueil