NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 07/03/2015

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

LOGIQUE

 

Débutants

Logique

RAISONNEMENT

 

Glossaire

Démonstrations

 

Glossaire

Logique

 

 

 

 

INDEX

 

Logique

 

Itérations

 

Raisonnements

Démonstrations

Récurrence

Automatisation

 

Sommaire de cette page

>>> Approche comparée

>>> Somme des nombres entiers

>>> Formalisation

>>> Exemples de démonstrations

 

 

 

Démonstration par induction

ou

Raisonnement par récurrence

ou, plus précisément

Démonstration par induction sur une formule de récurrence

 

Le raisonnement par récurrence est une forme particulière

du raisonnement par induction

 

Comment facilement prouver une affirmation

sans la prouver dans le cas général

mais en montrant que la propriété se transmet de proche en proche.

Français: récurrence ou induction.

Anglais: induction; to apply induction to the recursion formula.

 

 

Analogies à titre d'introduction

 

1.    Sachant qu'un domino tombant fait tomber le suivant;

2.   Si je pousse le premier domino:

 

Alors,  tous les dominos tombent.

 

1.    Si on sait monter d'une marche à la suivante;

2.   Et mettre le pied sur une marche:

 

Alors, on sait monter tout l’escalier.

 

 

 

Approche comparée

Escalier

Formule de récurrence

*    Soit un robot qui doit monter un escalier de N marches.

*    Soit à trouver la somme de N entiers (par exemple).

*    Je dispose du robot :

il bouge les pieds alternativement.

*    On me donne une formule :

½ N (N+1)

*    On me dit qu’il sait monter l’escalier.

*    On me dit qu’elle permet de calculer rapidement la somme des entiers.

*    Il me faut le tester et être sûr qu’il monte toutes les marches.

*    Il me faut démontrer que cette formule fonctionne pour toute les valeurs de N

*    Je m’y prends de la manière suivante.

*    Je procède en deux temps.

1) – Je vérifie que,

1) – Je vérifie que,

*    Supposant le robot sur une marche quelconque,

*    Supposant la formule vraie pour N,

*    Le mouvement des pieds correspond bien à l’action de gravir une marche

*    Elle est alors vraie pour N + 1

Voir démonstration

 2) – Je teste que

2)  – Je teste que

*    En posant le robot sur une des marches, c’est bon.

*    La formule est bonne dans UN cas.

3) En résumé

 

*    Si le robot sait monter d’une marche à l'autre.

*    Si je sais passer du calcul de N à N+1.

*    En le posant sur une marche.

*    En connaissant une valeur de la formule.

*    Il sait monter tout l’escalier.

*    La formule est vraie dans tous les cas.

 

 

 

 

 
 

Somme des nombres entiers

1) – Je vérifie que,

1) – Je vérifie que,

Supposant la formule vraie pour N,

 

On suppose que la somme des entiers jusqu’à N est 

 

Tn = ½ N (N+1)

 

C’est notre formule de récurrence pour N

 

On a noté la somme T, car il s'agit en fait du calcul des nombres triangulaires

Elle est alors vraie

pour N + 1

 

La somme des entiers jusqu’à N+1 est égale à la somme jusqu’à N, à laquelle on ajoute N+1.

 

Tn+1 = Tn + N+1

 

Développons cette relation

 

 

Tn+1 = ½ N (N+1) + N+1

Tn+1 = ½ (N² +N + 2N+2)

Tn+1 = ½ (N +1) (N + 2)

 

 

Or c’est justement la formule de récurrence pour N+1

Formule initiale dans laquelle n devient n+1

2) – Je teste que

2) – Je teste que

La formule est bonne

 dans UN cas

 

Prenons N = 1, alors S1 = 1

On vérifie que

T1 = ½ x 1 x (1+1)

T1 = 1

C’est bon

 

3) En résumé

 

Si je sais passer du calcul de N à N+1

La formule reste vraie pour N+1, si je suppose qu’elle est vraie pour N.

En connaissant une valeur de la formule.

La formule est vraie pour N = 1.

La formule est vraie dans tous les cas.

Elle sera vraie pour 1 + 1 = 2,

Et ensuite pour 2 + 1 = 3

Etc. pour tous les nombres jusqu’à l’infini.

 

Voir  Somme des entiers, carrés cubes … Démonstration par récurrence

 

 

FORMALISATION

RAISONNEMENT par INDUCTION

MATHEMATICAL INDUCTION

Objet 

*    Soit une affirmation P(n) relative au nombre entier n.

*    Il s'agit de prouver que cette affirmation est vraie pour tout nombre entier.

Subject

*    Let P(n) be a statement involving the natural number n.

*    To prove that P(n) is true for all natural numbers n, we proceed as follows:

Premier principe d'induction

1.   Vérifiez que P(1) est vraie;

2.   Supposez que P(k) est vraie; et

3.   Dans ces conditions, démontrez que P(k+1) est vraie.

First principle of mathematical induction

1.   Prove that P(1) is true;

2.   Assume that P(k) is true; and

3.   Using steps 1 and 2, prove that P(k+1) is true.

Second principe d'induction
(forte)

1.   Vérifiez que P(1) est vraie;

2.   Supposez que P(k) est vraie
pour 1 ≤ n ≤ k; et

3.   Dans ces conditions, démontrez que P(k+1) est vraie.

Second principle of mathematical induction
 (strong)

1.   Prove that P(1) is true;

2.   Assume that P(n) is true
for all 1 ≤ n ≤ k; and

3.   Using steps 1 and 2, prove that P(k+1) is true.

 

 

Principe général
pour aborder
la démonstration de l'étape 3.

*    Écrivez l'expression en changeant k par k+1:

*    m = P(k)

*    m' = P(k+1)

*    Dans cette nouvelle expression, isolez l'expression en k, ou une fonction de celle-ci:

*    m' = f(m) + H

*    Montrez que H à les propriétés requises

*    de divisibilité, par exemple.

 

 

 

 

Exemples de démonstrations

*  100…01n = ligne n du triangle de Pascal

>>>

*  Autres démonstrations de divisibilité

>>>

*  Consécutifs en division

>>>

*  Divisibilité par 11 de formes polynomiales

>>>

*  Divisibilité par 5 de formes polynomiales

>>>

*  Divisibilité par 8 de formes polynomiales

>>>

*  Entiers   et formes polynomiales

*  Inverses et formes polynomiales

>>>

>>>

*  Factorielle moins un = un produit

>>>

*  La somme des cubes de trois nombres consécutifs est divisible par 9

>>>

*  Les deux couleurs

>>>

*  Montrez que   3 divise l'expression suivante m =  n (2n² + 7)

>>>

*  Montrez que 24 divise l'expression suivante m = 2 . 7n + 3 . 5n – 5

>>>

*  Nombre de Fermat – Unité en 7

>>>

*  Nombre de Fermat = produit des précédents + 2

>>>

*  Paires divisibles dans un ensemble de nombres

>>>

*  Pesée avec des 4 et des 7

>>>

*  Puissance de 2 et 2n (simple) / idem avec cubes

>>>

*  Quantité de partitions

>>>

*  Somme des entiers, carrés, cubes …

>>>

*  Somme des inverses des proniques

>>>

*  Tour de Hanoï

>>>

 

 

 

 

 

Voir d'autres démonstrations faciles en 

*         Théorie des nombres pour débutants

Retour

*         Types de démonstrations dont récurrence

Voir aussi

*         Bon ordre

*         Boucle infernale

*         Calcul mental

*         Divisibilité par 6 de n3 - n

*         Divisibilité par 7

*         Divisibilités diverses

*         GéométrieIndex

*         Inventaire des outils mathématiques

*         Méthode de Newton

*         Récursivité

*         Somme des cubes des entiers

*         Somme des entiers, carrés, cubes …

*         Somme des puissances de 2

*         Suite de Fibonacci

*         Suite itératives

*         Théorie des nombres

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Iteration/Recurren.htm