Démonstration par récurrence

Choisissez une proposition concernant tout entier naturel n. Chaque domino ci-dessous représente un n, coloré selon que la proposition y est vraie, après vérification directe. La flèche partant d'un domino est l'hérédité de n à n + 1. Seule une initialisation vraie suivie d'une suite ininterrompue de flèches constitue une démonstration, et les dominos atteints par cette suite tombent.

Exemple résolu — Démonstration par récurrence

Étape de 1 à 2	échoue
Prouvé, parmi les n jusqu'à 12	1
Premier n faux, jusqu'à 12	2

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Démonstration par récurrence

La démonstration par récurrence prouve une assertion P(n) pour tout entier naturel n à partir d'un certain n₀, en deux parties : l'initialisation, P(n₀) vérifiée directement, et l'hérédité, un raisonnement selon lequel P(k) entraîne P(k + 1) pour tout k ≥ n₀. Ensemble elles atteignent chaque n, à la manière de chaque domino qui en tombant renverse le suivant.

Ce que signifie chaque symbole

P(n): la proposition concernant n ; pour chaque n, elle est simplement vraie ou fausse
n₀: l'initialisation, point de départ de la preuve, vérifiée à la main
k: un n quelconque au sein de l'étape : le raisonnement suppose P(k) et doit atteindre P(k + 1)

D’où vient la formule

Pourquoi les deux parties suffisent. Supposons que l'initialisation soit vérifiée et que l'étape fonctionne pour tout k ≥ n₀, mais que P soit fausse quelque part à partir de n₀. Parmi les n où elle est fausse, il en existe un plus petit ; appelons-le m. Ce n'est pas n₀, car P(n₀) a été vérifiée, donc m − 1 ≥ n₀, et P(m − 1) est vraie puisque m était le premier échec. L'étape donne alors P(m), ce qui contredit le fait que P(m) soit fausse. Il n'y a donc aucun échec. Les deux parties sont utilisées : sans l'initialisation, m pourrait être n₀ ; sans l'étape pour un unique k, m pourrait être k + 1.
Pourquoi n² + n + 41 devait échouer. À n = 40 les deux premiers termes se combinent, 40² + 40 = 40 × 41, ainsi 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. À n = 41 chaque terme est un multiple de 41, et la valeur est 41 × 43. L'idée va plus loin : aucun polynôme à coefficients entiers qui n'est pas constant ne peut donner uniquement des nombres premiers, quel que soit le nombre qu'il en donne au début (Lehman, Leighton et Meyer le prouvent dans le Problème 1.25). Aucune étape de récurrence n'aurait donc jamais pu exister pour cette proposition.
2ⁿ > n² pour tout n ≥ 5, fait correctement. Initialisation : 2⁵ = 32 > 25 = 5². Hérédité : soit k ≥ 5 et supposons 2ᵏ > k². Alors 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Puisque k ≥ 5, k² ≥ 5k = 2k + 3k > 2k + 1, donc 2k² > k² + 2k + 1 = (k + 1)², et 2ᵏ⁺¹ > (k + 1)², ce qui est P(k + 1). L'étape elle-même nécessite seulement k ≥ 3. L'initialisation devait être 5 car P(2), P(3) et P(4) sont fausses.

Quarante cas vrais, puis 41 × 41 🖖

Cliquez sur n² + n + 41. Les valeurs 41, 43, 47, 53, 61, … sont premières pour tout n de 0 à 39, soit quarante à la suite, et à n = 40 la valeur est 1 681 = 41 × 41. Vous pouvez le voir venir en observant bien : 40² + 40 + 41 = 40 × 41 + 41. Le graphique ne comporte aucune flèche car il n'y a pas d'étape. Savoir que p(39) = 1 601 est premier ne dit rien de p(40), qui vaut p(39) + 80. Sur les mille premières valeurs 581 sont premières, d'où le caractère si convaincant de ce motif.

L'étape pour 2ⁿ > n² fonctionne dès k = 3 ; la proposition seulement à partir de n = 5 🖖

Cliquez sur 2ⁿ > n² depuis 1. L'initialisation est vérifiée, puisque 2 > 1. L'étape affirme que si 2ᵏ > k², alors 2ᵏ⁺¹ > 2k², et 2k² ≥ (k + 1)² exactement lorsque k² ≥ 2k + 1, ce qui est vrai à partir de k = 3. Donc depuis n₀ = 1 les flèches sortant de 1 et 2 sont brisées, et la proposition est fausse en 2, 3 et 4. Les flèches sortant de 3 et 4 fonctionnent alors que P(3) et P(4) sont toutes deux fausses : une étape correcte précédée d'un domino faux ne pousse rien. Cliquez sur 2ⁿ > n² depuis 5 et les mêmes flèches prouvent chaque n à partir de 5.

L'argument des chevaux est juste à chaque étape sauf une 🖖

Cliquez sur Les chevaux. L'étape prend n + 1 chevaux, applique la proposition aux n premiers et aux n derniers, et les réunit via les chevaux que les deux groupes partagent. À partir de n = 2 cela fonctionne, et chaque flèche depuis 2 est pleine. De 1 à 2 les groupes comptent un cheval chacun et n'en partagent aucun, le raisonnement ne prouve donc rien au seul endroit où il est nécessaire. Placez plutôt l'initialisation à 5 et chaque étape fonctionne, mais P(5) est fausse, et la chaîne n'a rien à pousser.

Problème entièrement résolu

À partir de quelle valeur 2ⁿ dépasse-t-il définitivement n³ ? 4 étapes
Prouvez que 2ⁿ > n³ pour tout n suffisamment grand. L'étape est facile à écrire. À partir d'où commence-t-elle à fonctionner, et où doit se situer l'initialisation ?

Ouvrez ce problème dans l'outil
1. Supposons P(k) : 2ᵏ > k³. Doubler est la seule opération possible :
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. L'étape fonctionne donc lorsque 2k³ ≥ (k + 1)³. Divisez les deux côtés par k³ :
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. L'étape fonctionne dès k = 4, et non depuis 3 :
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. Mais la proposition elle-même est fausse de n = 2 à n = 9. L'initialisation est le premier n où elle est de nouveau vérifiée :
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Réponse

2ⁿ > n³ est vérifiée pour tout n ≥ 10, ainsi qu'en n = 0 et 1. L'étape fonctionne à partir de k = 4, donc pour k = 4 jusqu'à 9, une étape correcte se cache derrière une proposition fausse, tout comme 2ⁿ > n² le fait en 3 et 4 sur cette page. Cliquez sur 2ⁿ > n² depuis 5 pour comparer.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Parcours

Méthodes de démonstration

Références (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.