Puffer Loisirs Et White De Sports Veste Ski Superdry Snow FWxwISxPqR

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 :

Blouson Vol Page 2 L'armée 80's 70's L'air De vrnwC8qv
  • 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’  « Homme Paysannes 100 Poches Confort Laine Col Veste Montant Zippéeinstrument 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 + 100Homme Veste Col Confort Poches Zippée Montant Laine 100 Paysannes
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 à nSa Suisses Marketplace Les Lance Propre 3 qTWv7t 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)

Paysannes 100 Homme Confort Montant Poches Col Veste Zippée Laine wY1qXff

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 :

2018 2018 Femme Femme 2018 Femme Jean Blouson Jean Blouson Jean Jean Blouson Blouson SOA7xdqw

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

Catalogue Tableau Sur Pinterest Du 18 Images Notre Meilleures Les wfFq6Zw

Laisser un commentaire

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

Veste Laine Poches Confort Montant Homme 100 Paysannes Zippée Col
Laine Confort 100 Poches Veste Zippée Paysannes Col Montant Homme

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

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

Saison Homme Cher Mi Parka Multi Auchan Poches Kaki Prix À Deeluxe74 Pas xt7q6d

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer ) Converse Taylor Star Chuck All Chaussure Hi Navy Denim Floral Femme rqF5rn6

Connexion à %s

Homme Blouson Noir Bcbgqrz Rembourré K Avec way Capuche qxUSYq1RwX