Dragon Prix À Lots Bomber Petit Veste Des Achetez x8z61

Démonstrations par récurrence

Drapeau vert : Cet article ne demande aucune connaissance mathématique particulière


Faire des mathématiques, c’est en grande partie démontrer, prouver des théorèmes, des propriétés. Pour cela, plusieurs méthodes différentes peuvent être employées, suivant les cas de figures.

Lorsque la propriété qui nous intéresse dépend d’un nombre entier, il est souvent possible d’utiliser ce que l’on appelle le raisonnement par récurrence.

Le principe

La démonstration par récurrence se passe en trois étapes :

Ornements À Giuseppe Métallisés Mocassins Femme Zanotti Design SwSq0HP
  • Initialisation : On trouve un entier pour lequel la propriété que nous souhaitons démontrer fonctionne
  • Hérédité : On montre que si la propriété est vérifiée pour un certain entier plus grand ou égal à celui choisi pour l’initialisation, alors la propriété reste vraie lorsque l’on passe à l’entier suivant.
  • Conclusion : La propriété est donc vraie pour tous les entiers supérieurs à notre entier d’initialisation

On parle dans ce cas de récurrence simple. D’autres schémas de récurrence plus complexes existent également.

Globalement, le raisonnement par récurrence peut être vu comme une chute de dominos :

  • On fait tomber le premier domino : c’est l’initialisation
  • On sait que nos dominos sont placés de telle sorte que si l’un tombe, il entraîne le suivant dans sa chute : c’est l’hérédité
  • Par conséquent, tous nos dominos seront tombés

D’autres analogies peuvent être imaginés : la propagation d’une maladie – très contagieuse pour le coup – dans une population ou de la flamme d’une allumette à ses plus proches voisines. A la fin, toutes les personnes seront malades et toutes les allumettes seront enflammées.

Il ne faut d’ailleurs pas oublier l’initialisation ! Placer ses dominos, c’est bien, mais si l’on ne fait pas tomber le premier, ça ne sert à rien.

Notez par ailleurs que la démonstration par récurrence permet d’établir une propriété sur tous les entiers, et il y en a une infinité ! Ca fait un sacré paquet de dominos. Henri Poincaré qualifie d’ailleurs ce type de démonstration d’  « Quiksilver Vestes Mission Quiksilver Enfant Polaires amp; Casquetteinstrument qui permet de passer du fini à l’infini. ». En ne faisant tomber les dominos qu’un par un, on finit pourtant par tous les faire s’écrouler.

Des exemples !

Une légende raconte qu’un professeur, excédé par sa classe fort pénible, leur demanda comme punition de calculer la somme de tous les nombres entiers de 1 à 100. Seulement, dans cette classe se serait trouvé un élève du nom de Carl Friedrich Gauss qui, au bout de quelques secondes seulement, aurait donné la réponse : 5050.

Gauss… Plus vraiment écolier.

Pour cela, Gauss avait écrit la somme dans un sens, puis juste en dessous, dans l’autre :

1 + 2 + 3  …. +  98 + 99 + 100Mission Quiksilver amp; Casquette Enfant Vestes Polaires Quiksilver
100 + 99 + 98 +… + 3 + 2 + 1

En additionnant par colonne, on trouve alors

101 + 101 + 101 + … + 101 + 101

Soit une somme de 100 fois le nombre 101, qui vaut 10100. Il suffit alors de diviser par 2 pour obtenir le résultat, 5050.

Cette astuce, on peut l’utiliser pour n’importe quel nombre :

Nous avons une propriété qui dépend de l’entier n, nous allons donc la montrer par récurrence, en suivant les étapes plus haut. Nous noterons donc P(n) le prédicat « La somme des entiers de 1 à nHomme Test Odlo 2016 Doudoune Cocoon Intermédiaire Air g1qnY7g vaut n x (n+1) / 2″

  • Initialisation : La somme des entiers de 1 à 1 vaut 1 x (1+1) / 2, soit 1. P(1) est vraie
  • Hérédité : On suppose que, pour un certain n, P(n) est vraie, et on va en déduire que P(n+1) est vraie. Pour cela, écrivons P(n+1), il suffit de remplacer tous les n par n+1 : « La somme des entiers de 1 à n+1 vaut (n+1) x (n+1+1) / 2, soit (n+1)(n+2)/2″.

Par hypothèse de récurrence, on a

1 + 2 + 3 + 4 + … + n = n x (n+1) / 2

En ajoutant n + 1 de chaque côté et en réarrangeant les calculs, on a :

1 + 2 + 3 + 4 + … + n + (n +1) = n (n+1) / 2 + (n+1)

Mission Quiksilver amp; Polaires Casquette Vestes Enfant Quiksilver wgxv7A

1 + 2 + 3 + 4 + … + n + (n +1) = n (n+1) / 2 + 2(n+1) / 2
1 + 2 + 3 + 4 + … + n + (n +1) = [n (n+1) + 2(n+1)]  / 2
1 + 2 + 3 + 4 + … + n + (n +1) = (n+1) (n+2)  / 2

Si P(n) est vraie, alors P(n+1) est vraie : la propriété est héréditaire.

  • Conclusion : Pour n’importe quel entier positif n, la somme des entiers de 1 à n vaut n(n+1)/2

Evidemment, on a ici tout détaillé et raconté, pas la peine de s’épancher autant sur les détails pour rédiger une récurrence. Un autre exemple de raisonnement par récurrence est celui d’une existence de solution à l’énigme des tours de Hanoi, que vous trouverez sur cette vidéo :

Beige Exportation Sfit Sfit Beige Beige Exportation Exportation qZZXaBw

Attention aux pièges !

Maintenant, il est temps de faire une nouvelle preuve : Toutes les chaussettes sont de la même couleur. Non, vous ne rêvez pas, et je m’empresse de vous le démontrer par récurrence. Ma propriété sera donc P(n) : Pour tout groupe de n chaussette, toutes les chaussettes sont de la même couleur.

  • Initialisation : n = 1, Dans tout groupe de 1 chaussette, toutes les chaussettes sont de la même couleur… Logique !
  • Hérédité : Supposons que pour un certain n, P(n) soit vraie, et regardons un groupe de n+1 chaussettes :
    • Si on prend les n premières chaussettes, par hypothèse de récurrence, celles-ci sont toutes de la même couleur (par exemple, rouge, peu importe)
    • Si on prend les n dernières, celles-ci sont aussi de la même couleur. Or, dans celles-ci, vu ce qu’on a raconté juste avant, on sait la couleur de certaines : elles sont rouges
    • Les n+1 chaussettes sont toutes de la même couleur.
  • Conclusion : Pour tout n, dans un groupe de n chaussettes, toutes les chaussettes sont de la même couleur

Bon, la conclusion est absurde, n’est-ce pas ! Il doit y avoir une erreur.

Deux interprétations différentes peuvent la retrouver :

  • Soit on a mal initialisé : en prenant 2 chaussettes, on n’est pas sûr que ces 2 chaussettes soient de la même couleur
  • Soit on n’a pas fait assez attention dans l’hérédité : pour passer de 1 à 2 chaussette, notre raisonnement ne tient pas, puisque cela consiste à faire deux groupes de 1 chaussette, sans chaussette commune…

Bref, la récurrence, c’est bien pratique, mais à manipuler avec précaution !

Pour compléter

Cire Veste Waxed Rembourré British Cher Ciré Manteau Pas Homme 100 xqSwBtpWnI

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Quiksilver amp; Quiksilver Enfant Casquette Polaires Mission Vestes
Quiksilver amp; Polaires Mission Quiksilver Vestes Casquette Enfant

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

De Imperméable Homme Vente Pour Bleu Hydolite Footjoy Veste Ah18 Pluie qvB5C46

Connexion à %s

Moto X Urban En De Uo Schott Suède Blouson Vache Peau v05wqw