• Accueil
  • À propos
  • Accrom\(\alpha\)th en PDF
  • Commanditaires
  • Contact et Abonnements
  • Sites amis

Logo

Preuves par récurrence

Par André Ross
Volume 3.1 - hiver-printemps 2008

Annick veut savoir ce qu’est une preuve par récurrence.

Annick
Bonjour Alexandra. J’ai lu qu’il y a une méthode de preuve qui s’appelle preuve par récurrence. De quoi s’agit-il?

Alexandra
Bonjour vous deux. Le raisonnement par récurrence est un outil très puissant que l’on attribue à Blaise Pascal. À l’aide de cette méthode, on peut démontrer des propriétés relatives aux nombres entiers positifs.

Yannick
Peux-tu nous donner un exemple?

Alexandra
D’accord! Considérons les expressions suivantes :
\[1 = 1^2\]
La somme des deux premiers entiers impairs donne :
\[1 + 3 = 4 = 2^2\]
On peut donner une représentation visuelle de cette somme en disposant des billes de la
façon suivante :
\[1 + 3 =2^2\]recurrence_img1
Si on ajoute cinq billes à cette configuration, on obtient :
\[1+3+5=3^2\]recurrence_img2
On constate que le nombre \(5\) que l’on vient d’ajouter forme la ligne extérieure. De la même façon, en ajoutant \(7\) billes, on a :
\[1+3+5+7=4^2\]recurrence_img3
Puis, en ajoutant neuf autres billes :
\[1+3+5+7+9=5^2\]recurrence_img4
Qu’est-ce que vous remarquez d’intéressant?

Annick
La somme des \(n\) premiers entiers impairs est égale à \((n+1)^2.\)

Alexandra
En effet, c’est une conjecture que nous pouvons formuler, mais dont nous ne sommes pas encore en mesure de démontrer qu’elle est toujours vraie. Supposons maintenant que cette propriété est vraie pour les \(k\) premiers entiers impairs. Cela signifie que :
\[1+3+5+7+\dotsb+(2k+1)=(k+1)^2\]

Yannick
Cela signifie aussi qu’on peut former un carré de côté \(k+1\) de la façon suivante :
\[1+3+5+7+\dotsb+(2k+1)=(k+1)^2\]recurrence_img5
La ligne extérieure est \(2k+1,\) le dernier terme de notre somme.

Alexandra
En effet! Maintenant que se passe-t-il si on ajoute à la somme l’entier impair qui suit \(2k+1\)?

Yannick
L’entier impair suivant est \(2k+3.\) On peut alors ajouter une ligne de \(k+1\) billes et une colonne de \(k+1\) billes et une autre bille pour compléter le carré.recurrence_img6

On a donc ajouté :
\[2(k+1)+1=2k+3\]
et on a formé un autre carré.

Alexandra
Cela signifie que si ;
\[1+3+5+7+\dotsb+(2k+1)=(k+1)^2\]
alors :
\begin{align*}
1+3+5+7+\dotsb+(2k+1)+(2k+3)&=(k+1)^2+(2k+3) \\
&=k^2+2k+1+(2k+3) \\
&=k^2+4k+4 \\
&=(k+2)^2
\end{align*}
Qu’est-ce que cela nous permet de conclure?

Annick
On peut conclure que la propriété est toujours vraie.

Yannick
Je suis d’accord! On a montré que si c’est vrai pour la somme des \(k\) premiers entiers impairs, alors c’est vrai pour la somme des \(k+1\) premiers entiers impairs. Or, on a vérifié que c’est vrai pour \(1,\) pour \(2,\) pour \(3,\) pour \(4\) et pour \(5.\) Puisque c’est vrai pour \(k=5,\) c’est vrai pour \(k+1=6.\) Puisque c’est vrai pour \(k=6,\) alors c’est vrai pour \(k+1=7\) et ainsi de suite. C’est donc vrai pour tout \(n.\)

Alexandra
Nous venons de faire une démonstration par récurrence. Ce type de démonstration comporte deux étapes :

  1. Vérifier d’abord que la propriété est vraie pour une première valeur.
  2. Montrer ensuite que si la propriété est vraie pour un \(k\) quelconque, alors elle est vraie pour \(k+1.\)

Lorsque ces deux conditions sont satisfaites, on peut conclure que la propriété est vraie pour tout \(n\) supérieur ou égal à la première valeur considérée.

Yannick
Pourquoi on ne pouvait faire cela avec la conjecture de Polignac1?

Alexandra
Dans la conjecture de Polignac, on ne peut démontrer la deuxième partie. Si on pose comme hypothèse que la proposition est vraie pour un entier impair \(k,\) cela signifie que \(k\) peut s’exprimer comme la somme d’une puissance de \(2\) et d’un nombre premier, mais on ne sait pas quelle est cette puissance ni quel est ce nombre premier. On n’est pas plus avancé.

Annick
Puisque la deuxième condition est indémontrable, on ne peut rien conclure par cette méthode, mais le contre-exemple indique que la conjecture de Polignac est fausse.

Alexandra
Pour illustrer le principe de la preuve par récurrence, on utilise souvent une analogie avec des dominos ou avec une échelle.

Pour faire tomber une suite de dominos aussi longue que l’on veut (voire de longueur
infinie2), il faut :

  1. Faire tomber le premier domino.
  2. Qu’en tombant, le domino \(k\) entraîne dans sa chute le domino \(k+1.\)

Alors, le premier domino, en tombant, entraîne en séquence tous les autres dominos dans sa chute.

Yannick
Je comprends. C’est la même chose pour l’échelle. Pour monter jusqu’au sommet d’une échelle, de longueur infinie, il faut :

  1. Prendre pied sur le premier barreau.
  2. Qu’à partir du barreau \(k\) on puisse accéder au barreau \(k+1.\)

Annick
C’est quand même assez astucieux comme méthode de preuve.

PDF

  1. Voir l’article Pourquoi démontrer ce qui est évident?, dans ce numéro. ↩
  2. Voir l’article de Frédéric Gourdeau L’infini, c’est gros comment?, vol. 2, hiver-printemps 2007. ↩
  • ● Version PDF
Partagez
  • tweet

Etiquettes : Logique mathématique

Articles récents

  • Se rendre invisible, est-ce possible ?

    Christiane Rousseau
  • Points, droites et plans

    André Ross
  • Le jeu de Nim

    Christiane Rousseau

Sur le même sujet

  • Dessine-moi un graphe

    Alain Hertz
  • Les tours de Hanoï et la base trois

    Benoît Rittaud
  • Des fonctions… déroutantes

    Laurent Pelletier

Volumes

  • Volume 19.1 – hiver-printemps 2024
  • Volume 19.2 – été-automne 2024
  • Volume 20.1 – hiver-printemps 2025
  • Volume 18.2 – été-automne 2023
  • Volume 18.1 – hiver-printemps 2023
  • Volume 17.2 – été-automne 2022
  • Volume 17.1 – hiver-printemps 2022
  • Journée internationale des mathématiques: Accromath multilingue
  • Volume 16.2 – été-automne 2021
  • Volume 16.1 – hiver-printemps 2021
  • Volume 15.2 – été-automne 2020
  • Thème spécial: Les mathématiques sont partout
  • Volume 15.1 – hiver-printemps 2020
  • Volume 14.2 – été-automne 2019
  • Volume 14.1 – hiver-printemps 2019
  • Volume 13.2 – été-automne 2018
  • Volume 13.1 – hiver-printemps 2018
  • Volume 12.2 – été-automne 2017
  • Volume 12.1 – hiver-printemps 2017
  • Volume 11.2 – été-automne 2016
  • Volume 11.1 – hiver-printemps 2016
  • Volume 10.2 – été-automne 2015
  • Volume 10.1 – hiver-printemps 2015
  • Volume 9.2 – été-automne 2014
  • Volume 9.1 – hiver-printemps 2014
  • Volume 8.2 – été-automne 2013
  • Volume 8.1 – hiver-printemps 2013
  • Volume 7.2 – été-automne 2012
  • Volume 7.1 – hiver-printemps 2012
  • Volume 6.2 – été-automne 2011
  • Volume 6.1 – hiver-printemps 2011
  • Volume 5.2 – été-automne 2010
  • Volume 5.1 – hiver-printemps 2010
  • Volume 4.2 – été-automne 2009
  • Volume 4.1 – hiver-printemps 2009
  • Volume 3.2 – été-automne 2008
  • Volume 3.1 – hiver-printemps 2008
  • Volume 2.2 – été-automne 2007
  • Volume 2.1 – hiver-printemps 2007
  • Volume 1 – été-automne 2006
  • Article vedette

    Auteurs

    • Michel Adès
    • Antoine Allard
    • Jean Aubin
    • Marie Beaulieu
    • Rosalie Bélanger-Rioux
    • Claude Bélisle
    • Léo Belzile
    • Marc Bergeron
    • Pierre Bernier
    • André Boileau
    • Véronique Boutet
    • Pietro-Luciano Buono
    • Jean-Philippe Burelle
    • Massimo Caccia
    • Jérôme Camiré-Bernier
    • France Caron
    • Philippe Carphin
    • Kévin Cazelles
    • Laurent Charlin
    • Pierre Chastenay
    • Noémie Chenail
    • Christian Côté
    • Jocelyn Dagenais
    • Marie-France Dallaire
    • Jean-Lou de Carufel
    • Jean-Marie De Koninck
    • Lambert De Monte
    • Jean-Paul Delahaye
    • Marc-André Desautels
    • Florin Diacu
    • Jimmy Dillies
    • Nicolas Doyon
    • Philippe Drobinski
    • Hugo Drouin-Vaillancourt
    • Louis J. Dubé
    • Thierry Duchesne
    • Matthieu Dufour
    • Stéphane Durand
    • Thomas Erneux
    • Philippe Etchécopar
    • Julien Fageot
    • Charles Fleurent
    • Serge Fontaine
    • Jérôme Fortier
    • Marlène Frigon
    • Jean-François Gagnon
    • André Garon
    • Christian Genest
    • Denis Gilbert
    • Jonathan Godin
    • Frédéric Gourdeau
    • Samuel Goyette
    • Andrew Granville
    • Jean Guérin
    • Hervé Guillard
    • Abba B. Gumel
    • James A. Hanley
    • Alain Hertz
    • Bernard R. Hodgson
    • Isabelle Jalliffier-Verne
    • Guillaume Jouvet
    • Tomasz Kaczynski
    • Patrick Labelle
    • Marc Laforest
    • Nadia Lafrenière
    • Josiane Lajoie
    • Alexis Langlois-Rémillard
    • Simon-Olivier Laperrière
    • René Laprise
    • Steffen Lauritzen
    • Denis Lavigne
    • Adrien Lessard
    • Steven Lu
    • Jean Meunier
    • Erica Moodie
    • Normand Mousseau
    • Johanna G. Nešlehová
    • Pierre-André Noël
    • Dmitry Novikov
    • Ostap Okhrin
    • Laurent Pelletier
    • Jean-François Plante
    • Serge B. Provost
    • Annie Claude Prud'Homme
    • Benoît Rittaud
    • Louis-Paul Rivest
    • Serge Robert
    • André Ross
    • Guillaume Roy-Fortin
    • Yvan Saint-Aubin
    • Maria Vittoria Salvetti
    • Charles Senécal
    • Vasilisa Shramchenko
    • Robert Smith?
    • Dylan Spicker
    • Anik Trahan
    • Shophika Vaithyanathasarma
    • William Verreault
    • Redouane Zazoun

Sujets

Accro-flashs (18) Algèbre (2) Applications (3) Applications des mathématiques (74) Changements climatiques (3) Climat (1) Construction des mathématiques (4) COVID-19 (10) Cristallographie (2) cryptographie (2) GPS (2) Gravité (2) Géométrie (12) Histoire des mathématiques (27) Imagerie (2) Infini (2) Informatique (2) Informatique théorique (3) Jeux mathématiques (2) Logique mathématique (18) Lumière (5) Mathématiques de la planète Terre (18) Mathématiques et architecture (1) Mathématiques et arts (8) Mathématiques et astronomie (6) Mathématiques et biologie (7) Mathématiques et développement durable (9) Mathématiques et littérature (9) Mathématiques et musique (1) Mathématiques et médecine (11) Mathématiques et physique (3) Mathématiques et transport (5) Modélisation (1) Nombres (4) Pavages (5) Portrait d'un mathématicien (20) Portrait d'un physicien (3) Probabilités (8) Probabilités et statistique (19) Racines (2) Rubrique des Paradoxes (71) Section problèmes (41) Théorie des groupes (1) Éditorial (38) Épidémiologie (2)
    • Instagram
    • Facebook

    © 2025 Accromath